PAT 2019冬季满分题解

7-1 good in c

#include<iostream> #include<string> #include<vector> using namespace std; string letter[26][7]; void outPut(string a) { for(int j = 0; j < 7; j++) { for(int i = 0; i < a.size(); i++) { cout << letter[a[i]-'A'][j]; if(i < a.size()-1) cout << " "; } cout << endl; } } int main() { for(int i = 0; i < 26; i++) { for(int j = 0; j < 7; j++) getline(cin, letter[i][j]); } string print; getline(cin, print); vector<string> world; int index = 0; string w = ""; while(index < print.size()) { while(print[index] >= 'A' && print[index] <= 'Z' && index < print.size()) w += (print[index++]); if(w != "") { world.push_back(w); w.clear(); } index++; } for(int i = 0; i < world.size(); i++) { outPut(world[i]); if(i < world.size()-1) cout << endl; } return 0; }

7-2 Block Reversing

#include<cstdio> #include<vector> using namespace std; const int maxn = 1e5+10; struct node{ int data, address, next; }m[maxn]; vector<int> res[maxn]; int main() { int head, n, num; scanf("%d%d%d", &head, &n, &num); for(int i = 0; i < n; i++) { int ad; scanf("%d", &ad); scanf("%d%d", &m[ad].data, &m[ad].next); m[ad].address = ad; } int p = head, index = 0; while(p != -1) { if(res[index].size() < num) res[index].push_back(p); else { index ++; res[index].push_back(p); } p = m[p].next; } for(int i = index; i >= 0; i--) { for(int j = 0; j < res[i].size()-1; j++) printf("%05d %d %05d\n", res[i][j], m[res[i][j]].data, res[i][j+1]); int las = res[i].size()-1; printf("%05d %d ", res[i][las], m[res[i][las]].data); if(i > 0) printf("%05d\n", res[i-1][0]); else printf("-1\n"); } }

7-3 Summit

#include<cstdio> #include<vector> using namespace std; const int maxn = 210; bool e[maxn][maxn], vis[maxn]; int n, m; bool isClique(vector<int> &a) { for(int i = 0; i < a.size(); i++) { for(int j = i+1; j < a.size(); j++) if(e[a[i]][a[j]] == false) return false; } return true; } bool isMax(vector<int> &a, int &h) { for(int i = 1; i <= n; i++) { if(vis[i] == true) continue; bool flag = true; for(int j = 0; j < a.size(); j++) { if(e[i][a[j]] == false) flag = false; } if(flag == true) { h = i; return false; } } return true; } int main() { scanf("%d%d", &n, &m); for(int i = 0; i < m; i++) { int a, b; scanf("%d%d", &a, &b); e[a][b] = e[b][a] = true; } int k; scanf("%d", &k); for(int i = 1; i <= k; i++) { int num, x, h; scanf("%d", &num); vector<int> temp; fill(vis, vis+maxn, false); for(int j = 0; j < num; j++) { scanf("%d", &x); temp.push_back(x); vis[x] = true; } if(!isClique(temp)) printf("Area %d needs help.\n", i); else if(!isMax(temp, h)) printf("Area %d may invite more people, such as %d.\n", i, h); else printf("Area %d is OK.\n", i); } }

7-4 Cartesian Tree

#include<vector> #include<cstdio> #include<unordered_map> #include<algorithm> #include<queue> using namespace std; vector<int> in; unordered_map<int, int> pos; int n; struct node{ int data; node * left, * right; }; void BuildTree(node * &root, int x) { if(root == NULL) { root = new node; root->data = x; root->left = root->right = NULL; return; } if(x > root->data) { if(pos[x] < pos[root->data]) BuildTree(root->left, x); else BuildTree(root->right, x); } } int cnt = 0; void print(int x) { printf("%d", x); cnt++; if(cnt < n) printf(" "); else printf("\n"); } void BFS(node * root) { queue<node *> q; q.push(root); while(!q.empty()) { node * front = q.front(); q.pop(); print(front->data); if(front->left != NULL) q.push(front->left); if(front->right != NULL) q.push(front->right); } } int main() { scanf("%d", &n); in.resize(n); for(int i = 0; i < n; i++) { scanf("%d", &in[i]); pos[in[i]] = i+1; } sort(in.begin(), in.end()); node * root = NULL; for(int i = 0; i < n; i++) BuildTree(root, in[i]); BFS(root); }