模考

马上要考PAT甲级了。所以后面的题目就当模考了。
第一次模考成绩 成绩 用时 79 2小时55分钟 最后一道图题好复杂，而且我没学好图。所以最后一道题只拿了第一个测试点的9分。

解析

1108 Finding Average

这是乙级的一道题。当时做的时候强行把实现了stod。当时记得花了很长时间。现在是模考，时间要紧，所以STL有stod，就用了STL的。
其实只是判断字符串是不是纯数字组成。有没有多个’.’，因为只能有0个或1个小数点嘛。还要字符串长度：-999.99极限也就是7.
通过上面测试的字符串：肯定能使用stod了。在使用stod转换成double。判断是否小于1000，大于-1000即可。
Code： #include #include #include #include using namespace std; bool islegal(const string& a) { auto it = a.cbegin(); if (*it == '-') it++; while (it != a.cend()) { if (isalpha(*it)) return false; it++; } bool flag = false; for (int i = 0; i < a.size(); i++) { if (a[i] == '.') { if (flag == false) { flag = true; if (a.size() - i-1 > 2) return false; } else return false; } } if (a.size() > 7) return false; double result = stod(a); if (result > 1000 || result < -1000) return false; return true; } int main() { int N,K = 0; scanf("%d", &N); double result=0.0; string input; for (int i = 0; i < N; i++) { cin >> input; if (islegal(input)) { result += stod(input); K++; } else cout << "ERROR: " << input << " is not a legal number "; } if (K == 0) cout << "The average of 0 numbers is Undefined "; else if (K == 1) printf("The average of 1 number is %.2f ", result); else printf("The average of %d numbers is %.2f", K, result / K); }

1109Group Photo

这也是乙级的一道题QAQ。
一开始把题意读错了，所以出现了段错误。浪费了一点时间
把题意读清楚了后。就OK了。其实这题和螺旋矩阵是一个思路。都是把数据按规律放在数组里。最后输出。
先对站最最后一行的人赋值。再对其他行循环赋值。
怎么赋值呢？就按题目的要求来：先赋值中间的人m/2+1,在赋值m/2+1-i,m/2+1+i。控制i变量即可。
Code: #include #include #include #include #include using namespace std; struct Stu{ string name; int tall; }; int main() { int N, K; // K hang scanf("%d %d", &N, &K); vector<Stu> data(N); for (int i = 0; i < N; i++) { cin >> data[i].name >> data[i].tall; } sort(data.begin(), data.end(), [](const Stu& a, const Stu& b) { if (a.tall == b.tall) return a.name < b.name; else return a.tall > b.tall; }); int row = N / K; auto it = data.cbegin(); vector<vector<Stu>> photo(K); photo[0].resize(row + N % K); int m = (row + N % K)/2; //one row; photo[0][m] = *it++; for (int i = 0; i < m; i++) { photo[0][m - i-1] = *it++; if(m+i+1 < (row+N%K)) photo[0][m + i+1] = *it++; } m = row/ 2; for (int i = 1; i < K; i++) { photo[i].resize(row); photo[i][m] = *it++; for (int j = 0; j < m; j++) { photo[i][m - j - 1] = *it++; if (m + j + 1 < row) photo[i][m + j + 1] = *it++; } } for (int i = 0; i <K; i++) { for (int j = 0; j < photo[i].size(); j++) cout << photo[i][j].name << (j + 1 == photo[i].size() ? ' ' : ' '); } } /* 10 3 Tom 188 Mike 170 Eva 168 Tim 160 Joe 190 Ann 168 Bob 175 Nick 186 Amy 160 John 159 */

1110 Complete Binary Tree

问是不是一颗完全二叉树。
第一个问题是怎么找到根：其实不难：输入给出的是每个结点的儿子情况：设置一个isroot数组。如果输入中出现了数字i，就证明i是儿子，isroot[i]=false。经过一轮输入，根结点就出来了。
最后怎么判断是不是完全二叉树：一开始我打算用BFS做，但是发现很麻烦。所以思考了一下：想起来堆就是完全二叉树，所以就Build_heap。如果这棵树能Build成一个堆：就是一个完全二叉树，否则不是。Build_heap可以看代码
这题我又犯了一个错误：还是以前犯过的PAT 1064 Complete Binary Search Tree （30 分）.题目输入的儿子是一个数字或者’-’。所以如果用char去读就会出错，因为数字的范围是1~20。应该用字符串去读。浪费了我好长时间QAQ。
Code: #include #include #include #include #include #include #include using namespace std; struct Node { int lchild, rchild; Node() :lchild(-1), rchild(-1){} }; vector<Node> Tree; vector<bool> isroot; vector<int> Heap; int Build_Heap(int root,int position) { if (root == -1) return true; if (position > Tree.size()) return false; Heap[position] = root; return Build_Heap(Tree[root].lchild, position * 2) && Build_Heap(Tree[root].rchild, position * 2 + 1); } int main() { int N; scanf("%d", &N); Tree.resize(N), isroot.resize(N,true); string child1, child2; getchar(); for (int i = 0; i < N; i++) { cin >> child1 >> child2; if (child1[0] != '-') { isroot[stoi(child1)] = false; Tree[i].lchild = stoi(child1); } if (child2[0] != '-'){ isroot[stoi(child2)] = false; Tree[i].rchild = stoi(child2); } } int root; for (int i = 0; i < N; i++) { if (isroot[i] == true) { root = i; break; } } Heap.resize(Tree.size() + 1); if (Build_Heap(root, 1)) printf("YES %d ", Heap[Tree.size()]); else printf("NO %d ", root); } /* 9 7 8 - - - - - - 0 1 2 3 4 5 - - - - */

1111 Online Map

没想到最短路径能出的怎么复杂。而且我又犯了一个错误：题目读到一般就开始敲模板了。所以又双叒叕浪费了好长时间QAQ。
还没写出来：马上补充
Code #include #include #include #include #include #include #include using namespace std; const int INF = 0x3fffffff; struct Node { int v, length, time; Node(int _v, int _length, int _time) :v(_v), length(_length), time(_time) {} }; vector<vector<Node>> G; vector<vector<int>> pre1, pre2; vector<int> Short, fast; void Dijkstra(int s, vector<int>& d,vector<int>& f,vector<int>& num1,vector<int>& num2) { vector<bool> vis1(G.size(), false),vis2(G.size(),false); d.resize(G.size(), INF); f.resize(G.size(), INF); num1.resize(G.size(), 0); num2.resize(G.size(), 0); pre1.resize(G.size()); pre2.resize(G.size()); d[s] = 0; f[s] = 0; num1[s] = 1; num2[s] = 1; for (int i = 0; i < G.size(); i++) { int ud=-1, mind=INF, uf=-1, minf=INF; for (int j = 0; j < G.size(); j++) { if (vis1[j]==false &&mind > d[j]) { ud = j; mind = d[j]; } if (vis2[j] == false &&minf > f[j]) { uf = j; minf = f[j]; } } vis1[ud] = true; vis2[uf] = true; for (auto x : G[ud]) { int v = x.v; if (d[v] > d[ud] + x.length) { d[v] = d[ud] + x.length; pre1[v].clear(); pre1[v].push_back(ud); } else if (d[v] ==d[ud] + x.length) { pre1[v].push_back(ud); } } for (auto x : G[uf]) { int v = x.v; if (f[v] > f[uf] + x.time) { f[v] = f[uf] + x.time; pre2[v].clear(); pre2[v].push_back(uf); } else if (f[v] == f[uf] + x.time) { pre2[v].push_back(uf); } } } } void DFS1(int s, int v) { if (s == v) Short.push_back(s); else { DFS1(s, pre1[v][0]); Short.push_back(v); } } void DFS2(int s, int v) { if (s == v) fast.push_back(s); else { DFS2(s, pre2[v][0]); fast.push_back(v); } } int main() { int N, M; scanf("%d %d", &N, &M); G.resize(N); int V1, V2, one_way, length, time; for (int i = 0; i < M; i++) { scanf("%d %d %d %d %d", &V1, &V2, &one_way, &length, &time); G[V1].push_back(Node(V2,length,time)); if (one_way == 0) G[V2].push_back(Node(V1, length, time)); } int position, destination; scanf("%d %d", &position,&destination); vector<int> d, f,num1,num2; Dijkstra(position,d,f,num1,num2); DFS1(position,destination); DFS2(position, destination); bool flag1 = count(num1.begin(), num2.end(), 1)-G.