算法笔记_第六章

第六章书上的题目+Codeup+上机训练

6(书)

6.3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <vector>
#include <set>

using namespace std;

//PAT A1060
string deal(string s,int &e,int n)
{
    int k=0;
    while(s.length()>0&&s[0]=='0') s.erase(s.begin());
    if(s[0]=='.'){
        s.erase(s.begin());
        while(s.length()>0&&s[0]=='0'){
            s.erase(s.begin());
            e--;
        }
    }
    else{
        while(k<s.length()&&s[k]!='.'){
            k++;
            e++;
        }
        if(k<s.length()) s.erase(s.begin()+k);
    }
    if(s.length()==0) e=0;
    int num=0;
    k=0;
    string ans;
    while(num<n){
        if(k<s.length()) ans+=s[k++];
        else ans+='0';
        num++;
    }
    return ans;
}

int main()
{
    string str1,str2,str3,str4;
    int n;
    cin>>n>>str1>>str2;
    int e1=0,e2=0;
    str3=deal(str1,e1,n);
    str4=deal(str2,e2,n);
    if(str3==str4&&e1==e2) cout<<"YES 0."<<str3<<"*10^"<<e1<<endl;
    else cout<<"NO 0."<<str3<<"*10^"<<e1<<" 0."<<str4<<"*10^"<<e2<<endl;
    return 0;
}

6(上机)

6.1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <vector>

using namespace std;

//PAT A1047
const int N=40001;
const int M=2501;
vector<int> course[M];
char name[N][5];

bool cmp(int a,int b)
{
    return strcmp(name[a],name[b])<0;
}

int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    int num,courseID;
    for(int i=0;i<n;i++){
        scanf("%s%d",name[i],&num);
        for(int j=0;j<num;j++){
            scanf("%d",&courseID);
            course[courseID].push_back(i);
        }
    }
    for(int i=1;i<=k;i++){
        printf("%d %d\n",i,course[i].size());
        sort(course[i].begin(),course[i].end(),cmp);
        for(int j=0;j<course[i].size();j++)
            printf("%s\n",name[course[i][j]]);
    }
    return 0;
}

/*
//PAT A1039
const int N=26*26*26*10+1;
vector<int> selectCoures[N];

int getID(char name[])
{
    int id=0;
    for(int i=0;i<3;i++){
        id=id*26+(name[i]-'A');
    }
    id=id*10+name[3]-'0';
    return id;
}

int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    char name[5];
    for(int i=0;i<k;i++){
        int course,num;
        scanf("%d%d",&course,&num);
        for(int j=0;j<num;j++){
            scanf("%s",name);
            int id=getID(name);
            selectCoures[id].push_back(course);
        }
    }
    //query
    for(int i=0;i<n;i++){
        scanf("%s",name);
        int id=getID(name);
        sort(selectCoures[id].begin(),selectCoures[id].end());
        printf("%s %d",name,selectCoures[id].size());
        for(int j=0;j<selectCoures[id].size();j++){
            printf(" %d",selectCoures[id][j]);
        }
        printf("\n");
    }
    return 0;
}
*/

6.2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <vector>
#include <set>

using namespace std;

//PAT A1063
const int MAX=51;
set<int> st[MAX];

void compare(int a,int b)
{
    double all=st[b].size();
    double same=0;
    for(set<int>::iterator it=st[a].begin();it!=st[a].end();it++){
        if(st[b].find(*it)!=st[b].end()) same++;
        else all++;
    }
    printf("%.1f%%\n",same*100.0/all);
    return;
}

int main()
{
    int N;
    scanf("%d",&N);
    int num;
    int temp;
    for(int i=1;i<=N;i++){
        scanf("%d",&num);
        for(int j=0;j<num;j++){
            scanf("%d",&temp);
            st[i].insert(temp);
        }
    }
    int q;
    scanf("%d",&q);
    int a,b;
    for(int i=0;i<q;i++){
        scanf("%d%d",&a,&b);
        compare(a,b);
    }
    return 0;
}

6.4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>

using namespace std;

//PAT A1071
map<string,int> count1;

bool check(char c)
{
    if(c>='0'&&c<='9') return true;
    if(c>='a'&&c<='z') return true;
    if(c>='A'&&c<='Z') return true;
    return false;
}

int main()
{
    string str;
    getline(cin,str);
    int i=0;
    while(i<str.length()){
        string temp;
        while(i<str.length()&&check(str[i])==true){
            if(str[i]>='A'&&str[i]<='Z') str[i]+=32;
            temp+=str[i];
            i++;
        }
        if(temp!=""){
            if(count1.find(temp)!=count1.end()) count1[temp]++;
            else count1[temp]=1;
        }
        while(i<str.length()&&check(str[i])==false) i++;
    }
    string ans;
    int MAX=0;
    for(map<string,int>::iterator it=count1.begin();it!=count1.end();it++){
        if(it->second>MAX){
            ans=it->first;
            MAX=it->second;
        }
    }
    cout<<ans<<" "<<MAX<<endl;
    return 0;
}

/*
//PAT A1054
map<string,int> color;

int main()
{
    int m,n;
    string temp;
    scanf("%d%d",&m,&n);
    while(n--){
        for(int i=0;i<m;i++){
            cin>>temp;
            if(color.find(temp)!=color.end())
                color[temp]++;
            else color[temp]=1;
        }
    }
    int MAX=0;
    string ans;
    for(map<string,int>::iterator it=color.begin();it!=color.end();it++){
        if(it->second>MAX){
            ans=it->first;
            MAX=it->second;
        }
    }
    cout<<ans;
    return 0;
}
*/

/*
//PAT B1044
string low[13]={"tret","jan", "feb", "mar", "apr", "may", "jun", "jly", "aug", "sep", "oct", "nov", "dec"};
string high[13]={"tret","tam", "hel", "maa", "huh", "tou", "kes", "hei", "elo", "syy", "lok", "mer", "jou"};
map<string,int> number;
string str[200];
void init()
{
    for(int i=0;i<13;i++){
        number[low[i]]=i;
        str[i]=low[i];
        number[high[i]]=i*13;
        str[13*i]=high[i];
    }
    for(int i=1;i<13;i++){
        for(int j=1;j<13;j++){
            string temp=high[i]+" "+low[j];
            number[temp]=i*13+j;
            str[i*13+j]=temp;
        }
    }
    return;
}

int main()
{
    init();
    int num;
    string temp;
    scanf("%d%*c",&num);
    while(num--){
        getline(cin,temp);
        if(temp[0]>='0'&&temp[0]<='9'){
            int ans=0;
            for(int i=0;i<temp.length();i++){
                ans=ans*10+temp[i]-'0';
            }
            cout<<str[ans]<<endl;
        }
        else{
            cout<<number[temp]<<endl;
        }
    }
    //system("pause");
    return 0;
}
*/

这题答案用了map，我第一反应还是用结构体做的，万幸没超时

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>

using namespace std;

//PAT A1022
const int N=10001;
string ans[N];
struct book
{
    string id;
    string title;
    string author;
    vector<string> key;
    string publisher;
    string year;
}now[N];

int main()
{
    int n;
    scanf("%d",&n);
    getchar();
    for(int i=0;i<n;i++){
        //scanf("%d",&now[i].id);
        //getchar();
        getline(cin,now[i].id);
        getline(cin,now[i].title);
        getline(cin,now[i].author);
        string temp;
        //int num=0;
        while(cin>>temp){
            now[i].key.push_back(temp);
            char c=getchar();
            if(c=='\n') break;
        }
        getline(cin,now[i].publisher);
        getline(cin,now[i].year);
    }
    //check your input
    /*
    for(int i=0;i<n;i++){
        cout<<now[i].id<<" "<<now[i].title<<" "<<now[i].author;
        //for(int j=0;j<now[i].key.size();j++) cout<<now[i].key[j]<<" ";
        cout<<endl<<endl;
    }
    */
    //query
    int m;
    int cat;  //query type
    string temp;
    scanf("%d",&m);
    while(m--){
        scanf("%d: ",&cat);
        //getchar();
        getline(cin,temp);
        if(cat==1){
            int num=0;
            cout<<cat<<": "<<temp<<endl;
            for(int i=0;i<n;i++){
                if(now[i].title==temp){
                    ans[num]=now[i].id;
                    num++;
                }
            }
            if(num==0) printf("Not Found\n");
            else{
                sort(ans,ans+num);
                for(int k=0;k<num;k++){
                    cout<<ans[k]<<endl;
                }
            }
        }
        else if(cat==2){
            int num=0;
            cout<<cat<<": "<<temp<<endl;
            for(int i=0;i<n;i++){
                if(now[i].author==temp){
                    ans[num]=now[i].id;
                    num++;
                }
            }
            if(num==0) printf("Not Found\n");
            else{
                sort(ans,ans+num);
                for(int k=0;k<num;k++){
                    cout<<ans[k]<<endl;
                }
            }
        }
        else if(cat==4){
            int num=0;
            cout<<cat<<": "<<temp<<endl;
            for(int i=0;i<n;i++){
                if(now[i].publisher==temp){
                    ans[num]=now[i].id;
                    num++;
                }
            }
            if(num==0) printf("Not Found\n");
            else{
                sort(ans,ans+num);
                for(int k=0;k<num;k++){
                    cout<<ans[k]<<endl;
                }
            }
        }
        else if(cat==5){
            int num=0;
            cout<<cat<<": "<<temp<<endl;
            for(int i=0;i<n;i++){
                if(now[i].year==temp){
                    ans[num]=now[i].id;
                    num++;
                }
            }
            if(num==0) printf("Not Found\n");
            else{
                sort(ans,ans+num);
                for(int k=0;k<num;k++){
                    cout<<ans[k]<<endl;
                }
            }
        }
        else if(cat==3){
            int num=0;
            cout<<cat<<": "<<temp<<endl;
            for(int i=0;i<n;i++){
                for(int j=0;j<now[i].key.size();j++){
                    if(now[i].key[j]==temp){
                        ans[num]=now[i].id;
                        num++;
                    }
                }
            }
            if(num==0) printf("Not Found\n");
            else{
                sort(ans,ans+num);
                for(int k=0;k<num;k++){
                    cout<<ans[k]<<endl;
                }
            }
        }
    }
    //system("pause");
    return 0;
}

本文作者： xiaoyuyu
本文链接： http://woaixiaoyuyu.github.io/2020/02/06/%E7%AE%97%E6%B3%95%E7%AC%94%E8%AE%B0-%E7%AC%AC%E5%85%AD%E7%AB%A0/
版权声明： 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处！
赏

谢谢你请我吃糖果

扫一扫，分享到微信

微信分享二维码
本站总访问量次 本站访客数人

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

记录成长的点滴<br><br>涉猎颇广的信息技术爱好者<br>希望未来的xiaoyuyu<br>可以成为优秀的工程师