PAT 甲级真题题解（121-155）

1121 Damn Single

模拟

 1 // 1121 Damn Single
 2 #include <map>
 3 #include <vector>
 4 #include <cstdio>
 5 #include <iostream>
 6 #include <algorithm>
 7 using namespace std;
 8 
 9 map<int, int> m, vis;
10 vector<int> p;
11 const int N = 1e4 + 10;
12 int a[N];
13 
14 int main() {
15     int n, x, y;
16     scanf("%d", &n);
17     while (n--) {
18         scanf("%d %d", &x, &y);
19         x++; y++;
20         m[x] = y;
21         m[y] = x;
22     }
23     scanf("%d", &n);
24     for (int i = 1; i <= n; i++) {
25         scanf("%d", &a[i]);
26         a[i]++;
27         vis[a[i]] = 1;
28     }
29     for (int i = 1; i <= n; i++) {
30         if (vis[ m[a[i]] ]) continue;
31         p.push_back(a[i]);
32     }
33     sort(p.begin(), p.end());
34     printf("%d
", p.size());
35     for (int i = 0; i < p.size(); i++) {
36         if (i != 0) printf(" ");
37         printf("%05d", p[i] - 1);
38     }
39     return 0;
40 }

View Code

1122 Hamiltonian Cycle

模拟

 1 // 1122 Hamiltonian Cycle
 2 #include <set>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <iostream>
 6 #include <algorithm>
 7 using namespace std;
 8 
 9 const int N = 205;
10 int MAP[N][N];
11 set<int> s;
12 
13 int main() {
14     memset(MAP, -1, sizeof(MAP));
15     int n, m, k;
16     scanf("%d %d", &n, &m);
17     for (int i = 1; i <= m; i++) {
18         int u, v;
19         scanf("%d %d", &u, &v);
20         MAP[u][v] = 1; MAP[v][u] = 1;
21     }
22     scanf("%d", &k);
23     while (k--) {
24         bool f = 1;
25         int u, v, root;
26         scanf("%d", &m);
27         scanf("%d", &root);
28         s.insert(root);
29         u = root;
30         for (int i = 1; i < m; i++) {
31             scanf("%d", &v);
32             s.insert(v);
33             if (MAP[u][v] == -1) f = 0;
34             u = v;
35         }
36         if (root != u || s.size() != n || m != n + 1) f = 0;
37         if (!f) printf("NO
");
38         else printf("YES
");
39         s.clear();
40     }
41     return 0;
42 }

View Code

1124 Raffle for Weibo Followers

MAP标记

 1 // 1124 Raffle for Weibo Followers
 2 #include <map>
 3 #include <cstdio>
 4 #include <vector>
 5 #include <iostream>
 6 #include <algorithm>
 7 using namespace std;
 8 
 9 map<string, int> vis;
10 string str;
11 
12 int main() {
13     bool f = 0;
14     int n, m, s, cnt;
15     cin >> n >> m >> s;
16     cnt = m;
17     for (int i = 1; i < s; i++) cin >> str;
18     for (int i = s; i <= n; i++) {
19         cin >> str;
20         if (cnt == m && !vis[str]) {
21             f = 1;
22             cout << str << endl;
23             cnt = 1;
24             vis[str] = 1;
25         }
26         if (!vis[str]) cnt++;
27     }
28     if (!f) cout << "Keep going..." << endl;
29     return 0;
30 }

View Code

1125 Chain the Ropes

思维

 1 // 1125 Chain the Ropes
 2 #include <cstdio>
 3 #include <iostream>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 const int N = 1e4 + 10;
 8 int a[N];
 9 
10 int main() {
11     int n, ans = 0;
12     cin >> n;
13     for (int i = 1; i <= n; i++) cin >> a[i];
14     sort(a + 1, a + 1 + n);
15     ans = a[1];
16     for (int i = 2; i <= n; i++) {
17         ans += a[i];
18         ans /= 2;
19     }
20     cout << ans << endl;
21     return 0;
22 }

View Code

1126 Eulerian Path

给定m条边关系，判断是欧拉回路还是半欧拉回路或者不是欧拉回路。

如果一个连通图，具有0个奇度顶点为欧拉回路，具有2个奇度顶点为半欧拉，其他均不为欧拉图。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int N = 1e5 + 5;
 5 int cnt[N], fa[N];
 6 
 7 void init() {
 8     for (int i = 0; i < N; i++) fa[i] = i;
 9 }
10 
11 int fi(int x) {
12     return fa[x] == x ? fa[x] : fa[x] = fi(fa[x]);
13 }
14 
15 void Union(int x, int y) {
16     int fx = fi(x), fy = fi(y);
17     if (fx != fy) {
18         fa[fx] = fy;
19     }
20 }
21 
22 int main() {
23     init();
24     int n, m, ans = 0, s = 0;
25     scanf("%d %d", &n, &m);
26     for (int i = 1; i <= m; i++) {
27         int u, v;
28         scanf("%d %d", &u, &v);
29         Union(u, v);
30         cnt[u]++; cnt[v]++;
31     }
32     for (int i = 1; i <= n; i++) {
33         if (cnt[i] % 2) ans++;
34         if (fa[i] == i) s++;
35         if (i != 1) printf(" ");
36         printf("%d", cnt[i]);
37     }
38     printf("
");
39     if (s == 1 && ans <= 2) {
40         if (ans == 0) printf("Eulerian
");
41         else if (ans == 2) printf("Semi-Eulerian
");
42         else printf("Non-Eulerian
");
43     } else printf("Non-Eulerian
");
44     return 0;
45 }

View Code

1127 ZigZagging on a Tree

中序后序建树，层次遍历。（参考了柳神的做法，简洁多了。）

 1 #include <queue>
 2 #include <vector>
 3 #include <iostream>
 4 using namespace std;
 5 
 6 vector<int> in, post, result[35];
 7 int n, tree[35][2], root;
 8 
 9 struct node {
10     int index, depth;
11 };
12 
13 void dfs(int &index, int inLeft, int inRight, int postLeft, int postRight) {
14     if (inLeft > inRight) return;
15     index = postRight;
16     int i = 0;
17     while (in[i] != post[postRight]) i++;
18     dfs(tree[index][0], inLeft, i - 1, postLeft, postLeft + (i - inLeft) - 1);
19     dfs(tree[index][1], i + 1, inRight, postLeft + (i - inLeft), postRight - 1);
20 }
21 
22 void bfs() {
23     queue<node> q;
24     q.push(node{root, 0});
25     while (!q.empty()) {
26         node temp = q.front();
27         q.pop();
28         result[temp.depth].push_back(post[temp.index]);
29         if (tree[temp.index][0] != 0)
30             q.push(node{tree[temp.index][0], temp.depth + 1});
31         if (tree[temp.index][1] != 0)
32             q.push(node{tree[temp.index][1], temp.depth + 1});
33     }
34 }
35 
36 int main() {
37     cin >> n;
38     in.resize(n + 1), post.resize(n + 1);
39     for (int i = 1; i <= n; i++) cin >> in[i];
40     for (int i = 1; i <= n; i++) cin >> post[i];
41     dfs(root, 1, n, 1, n);
42     bfs();
43     printf("%d", result[0][0]);
44     for (int i = 1; i < 35; i++) {
45         if (i % 2 == 1) {
46             for (int j = 0; j < result[i].size(); j++)
47                 printf(" %d", result[i][j]);
48         } else {
49             for (int j = result[i].size() - 1; j >= 0; j--)
50                 printf(" %d", result[i][j]);
51         }
52     }
53     return 0;
54 }

View Code

1128 N Queens Puzzle

同行，同列，同斜判断下即可。

 1 // 1128 N Queens Puzzle
 2 #include <cstdio>
 3 #include <iostream>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 const int N = 1e5 + 10;
 8 bool vis1[N], vis2[N];
 9 
10 int main() {
11     int t, n, x;
12     cin >> t;
13     while (t--) {
14         bool ok = 1;
15         cin >> n;
16         for (int i = 0; i <= 3 * n; i++) vis1[i] = vis2[i] = 0;
17         for (int i = 1; i <= n; i++) {
18             cin >> x;
19             if (vis1[x] || vis2[x + i]) {
20                 ok = 0;
21             }
22             vis1[x] = 1;
23             vis2[x + i] = 1;
24         }
25         if (ok) cout << "YES" << endl;
26         else cout << "NO" << endl;
27     }
28     return 0;
29 }

View Code

1129 Recommendation System

STL set应用

 1 // 1129 Recommendation System
 2 #include <set>
 3 #include <cstdio>
 4 #include <iostream>
 5 #include <algorithm>
 6 using namespace std;
 7 
 8 const int N = 5e4 + 10;
 9 struct node {
10     int id, time;
11     friend bool operator < (node x,node y){
12         if(x.time == y.time) return x.id < y.id;
13         return x.time > y.time;
14     }
15 };
16 
17 int cnt[N];
18 set<node> se;
19 set<node> ::iterator it;
20 
21 int main() {
22     int n, k, x;
23     cin >> n >> k;
24     for (int i = 1; i <= n; i++) {
25         cin >> x;
26         if(i == 1) {
27             cnt[x]++;
28             se.insert({x, cnt[x]});
29             continue;
30         }
31         else {
32             cout << x << ":";
33             int c = 0;
34             for (auto y : se) {
35                 c++;
36                 if(c > k) break;
37                 cout << " " << y.id;
38             }
39             cout << endl;
40         }
41         if (se.find({x, cnt[x]}) != se.end()) {
42             it = se.find({x, cnt[x]});
43             se.erase(it);
44         }
45         cnt[x]++;
46         se.insert({x, cnt[x]});
47     }
48     return 0;
49 }

View Code

1130 Infix Expression

给定中缀表达式二叉树，输出中缀表达式。（记得CSP也考过，当时是直接暴力A的。）

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define N 21
 5 int n, Root;
 6 int vis[N];
 7 
 8 struct Node {
 9     string s;
10     int l, r;
11 } node[N];
12 
13 
14 void dfs(int root) {
15     if (root == -1) return ;
16     if (root != Root && (node[root].l != -1 || node[root].r != -1)) cout << "(";
17     dfs(node[root].l);
18     cout << node[root].s;
19     dfs(node[root].r);
20     if ( root != Root && (node[root].l != -1 || node[root].r != -1)) cout<<")";
21 }
22 
23 int main() {
24     scanf("%d", &n);
25     memset(vis, 0, sizeof(vis));
26     for (int i = 1; i <= n; i++) {
27         cin >> node[i].s >> node[i].l >> node[i].r;
28         vis[node[i].l] = vis[node[i].r] = 1;
29     }
30     Root = 1;
31     while (vis[Root]) Root++;
32     dfs(Root);
33     return 0;
34 }

View Code

1131 Subway Map

DFS暴力找最短路。同时保证题目中的那些要求。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define MAX 10005
 5 #define INF 0x3f3f3f3f
 6 
 7 int N, M, K;
 8 int S, E;
 9 
10 struct Stop {
11     int line;
12     int id;
13 } stops[MAX];
14 
15 vector<Stop> stopVec[MAX];
16 int flag[MAX];
17 int cntMax = INF;
18 vector<Stop> stopAns, stopsVec;
19 int subMin = 0;
20 
21 void dfs(int x, int cnt) {
22     if(x == E) {
23         int sub = 0;
24         if(cntMax > cnt) {
25             stopAns = stopsVec;
26             cntMax = cnt;
27             for(int i = 1; i < stopsVec.size(); i++) {
28                 if(stopsVec[i].line != stopsVec[i-1].line) {
29                     sub++;
30                 }
31             }
32             subMin = sub;
33         }
34         if(cntMax == cnt) {
35             for(int i = 1; i < stopsVec.size(); i++) {
36                 if(stopsVec[i].line != stopsVec[i-1].line) {
37                     sub++;
38                 }
39             }
40             if(sub < subMin) {
41                 stopAns = stopsVec;
42                 subMin = sub;
43             }
44         }
45         return;
46     }
47     for(int i = 0; i < stopVec[x].size(); i++) {
48         if(flag[stopVec[x][i].id] == 0) {
49             flag[stopVec[x][i].id] = 1;
50             stopsVec.push_back(stopVec[x][i]);
51             dfs(stopVec[x][i].id, cnt+1);
52             stopsVec.pop_back();
53             flag[stopVec[x][i].id] = 0;
54         }
55     }
56 }
57 
58 int main()
59 {
60     cin>>N;
61     for(int i = 1; i <= N; i++) {
62         scanf("%d", &M);
63         for(int j = 0; j < M; j++) {
64             scanf("%d", &stops[j].id);
65             stops[j].line = i;
66             if(j != 0) {
67                 stopVec[stops[j].id].push_back(stops[j-1]);
68                 stopVec[stops[j-1].id].push_back(stops[j]);
69             }
70         }
71     }
72     cin>>K;
73     for(int i = 0; i < K; i++) {
74         scanf("%d%d", &S, &E);
75         cntMax = INF;
76         dfs(S, 0);
77         printf("%d
", cntMax);
78         int line = stopAns[0].line;
79         int id = S;
80         for(int i = 0; i < stopAns.size(); i++) {
81             if(line != stopAns[i].line) {
82                 printf("Take Line#%d from %04d to %04d.
", line, id, stopAns[i-1].id);
83                 line = stopAns[i].line;
84                 id = stopAns[i-1].id;
85             }
86         }
87         printf("Take Line#%d from %04d to %04d.
", line, id, E);
88     }
89     return 0;
90 }

View Code

1132 Cut Integer

注意判断拆开后是否有0。

 1 #include <iostream>
 2 using namespace std;
 3 
 4 int cal(string s) {
 5     int res = 0;
 6     for (int i = 0; i < s.size(); i++) {
 7         res = res * 10 + (s[i] - '0');
 8     }
 9     return res;
10 }
11 
12 int main() {
13     int n;
14     cin >> n;
15     while (n--) {
16         string m;
17         int a, b, c;
18         cin >> m;
19         c = cal(m);
20         a = cal(m.substr(0, m.size() / 2));
21         b = cal(m.substr(m.size() / 2, m.size() / 2));
22         if (a * b != 0 && c % (a * b) == 0) cout << "Yes" << endl;
23         else cout << "No" << endl;
24     }
25     return 0;
26 }

View Code

1133 Splitting A Linked List

从root开始，保存小于0的，大于等于0小于等于K的和大于K的链表，最后按顺序输出结果即可。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int INF = 0x3f3f3f3f;
 5 
 6 struct Node {
 7     int data, next;
 8 } node[100005];
 9 
10 int root, a, N, K;
11 vector<int> v[3];
12 
13 int main() {
14     scanf("%d%d%d", &root, &N, &K);
15     for (int i = 0; i < N; i++) {
16         scanf("%d", &a);
17         scanf("%d %d", &node[a].data, &node[a].next);
18     }
19     while (root != -1) {
20         if (node[root].data < 0) v[0].push_back(root);
21         else if (node[root].data <= K) v[1].push_back(root);
22         else v[2].push_back(root);
23         root = node[root].next;
24     }
25     int f = 0;
26     for (int i = 0; i < 3; i++) {
27         for (int j = 0; j < v[i].size(); j++) {
28             if (!f) printf("%05d %d",v[i][j],node[v[i][j]].data), f = 1;
29             else printf(" %05d
%05d %d",v[i][j],v[i][j],node[v[i][j]].data), f = 1;
30         }
31     }
32     printf(" -1
");
33     return 0;
34 }

View Code