- 博客(282)
- 资源 (5)
- 问答 (1)
- 收藏
- 关注
RSS订阅原创 2020 PAT 甲级秋季题解
第一题#include<iostream>#include<cstdio>#include<algorithm>#include<vector>using namespace std;const int N = 10010;const int INF = 0x3f3f3f3f;int n;vector<int> milk, w;int main() { scanf("%d", &n); milk.resize(n +
2021-03-03 14:30:46
418
3
原创 2020 PAT 甲级春季题解
第一题#include<iostream>#include<string>#include<algorithm>#include<cstdio>using namespace std;bool isPrime(int x) { if(x < 2) return false; for(int i = 2; i <= sqrt(x); ++i) if(x % i == 0) return false; return true; }
2021-03-02 17:04:37
189
原创 2020 PAT 甲级冬季题解
第一题#include<iostream>using namespace std;int n;int a = 0, b = 1, c;int main() { scanf("%d", &n); while(true) { if(a <= n && b >= n) { printf("%d\n", (n - a) <= (b - n) ? a : b); break; } c = b; b += a; a =
2021-03-02 13:56:33
366
原创 2. Add Two Numbers
题解本题属于链表的简单题目，注意的点在于两个节点相加之后可能超过10，需要进位。ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { int add = 0; ListNode *root, *t; root = t = new ListNode(0); while(l1 && l2) { add += (l1->val + l2->.
2020-06-12 17:15:31
163
原创 1. Two Sum
1. 两数之和题解解法一使用顺序查找target - nums[i]在nums数组中是否存在。 vector<int> twoSum(vector<int>& nums, int target) { vector<int> res; for(int i = 0; i < nums.size(); ++i) { int t = target - nums[i]; v
2020-06-12 17:11:49
125
原创 Mongoose findOneAndUpdate and runValidators not working
Mongoose findOneAndUpdate and runValidators not workingJdruwe:I am having issues trying to get the ‘runValidators’ option to work. My user schema has an email field that has required set to true but...
2020-03-25 01:25:51
344
原创 1147 Heaps （30 point(s)）
题解堆的判定。#include<cstdio>using namespace std;const int MAXN = 1e3 + 10;int n, m;int t[MAXN];void getpost(int root) { if(root > n) return; getpost(root<<1); getpost(root<&l...
2019-02-20 18:32:39
394
2
原创 1146 Topological Order （25 point(s)）
题解拓扑排序。#include<iostream>#include<cstring>#include<vector>using namespace std;const int MAXN = 1e3 + 10;vector<int> e[MAXN];int in[MAXN], t[MAXN];int n, m, a, b, ...
2019-02-20 17:57:09
181
原创 1145 Hashing - Average Search Time （25 point(s)）
题解解决冲突应该msize / 2就可以了。没有必要msize。 #include<iostream>#include<cstdio>#include<vector>#include<cmath>using namespace std;bool isPrime(int x) { if(x < 2) return fal...
2019-02-20 17:38:24
211
原创 1144 The Missing Number （20 point(s)）
#include<cstdio>#include<iostream>#include<unordered_map>using namespace std;unordered_map<int, bool> have;int n, x;int main() { scanf("%d", &n); for(int i = 0; ...
2019-02-19 12:23:02
190
原创 1143 Lowest Common Ancestor （30 point(s)）
题解利用BST的性质即可。#include<iostream>#include<cstdio>#include<vector>#include<unordered_map>using namespace std;int w, u, v, n, m;unordered_map<int, bool> have;in...
2019-02-18 18:54:06
234
原创 1142 Maximal Clique （25 point(s)）
题解最大点集判断。 #include<iostream>#include<cstdio>#include<cstring>using namespace std;const int MAXN = 210;int e[MAXN][MAXN];int nv, ne, m, k, a, b;int have[MAXN], v[MAXN];...
2019-02-18 18:51:56
163
原创 1141 PAT Ranking of Institutions （25 point(s)）
题解unordered_map #include<iostream>#include<cstdio>#include<unordered_map>#include<algorithm>#include<vector>using namespace std;struct node { string school; ...
2019-02-18 18:49:58
194
原创 1140 Look-and-say Sequence （20 point(s)）
#include<iostream>#include<cstdio>#include<string>using namespace std;string res;int n;int main() { cin >> res >> n; for(int i = 0; i < n - 1; ++i) { char...
2019-02-18 18:45:56
180
原创 1139 First Contact （30 point(s)）
题解技巧性在于交际网络中，只录入同性关系。#include<iostream>#include<cstdio>#include<map>#include<algorithm>#include<vector>using namespace std;const int MAXN = 1e4;struct node ...
2019-02-17 17:42:59
288
原创 1138 Postorder Traversal （25 point(s)）
题解树的遍历。#include<cstdio>#include<iostream>#include<vector>using namespace std;vector<int> pre, in, post;void getpost(int l, int r, int root) { if(l > r) return;...
2019-02-17 17:09:18
241
原创 1137 Final Grading （25 point(s)）
题解STL应用。#include<iostream>#include<cstdio>#include<cmath>#include<algorithm>#include<map>using namespace std;const int MAXN = 1e4 + 10;struct node { string...
2019-02-17 17:07:37
168
原创 1136 A Delayed Palindrome （20 point(s)）
题解回文串简单判断。#include<iostream>#include<string>#include<cstdio>#include<algorithm>using namespace std;bool isPalin(string a) { string b = a; reverse(a.begin(), a.end(...
2019-02-17 13:01:09
309
原创 1135 Is It A Red-Black Tree （30 point(s)）
题解红黑树性质的判断。#include<iostream>#include<cstdio>#include<vector>#include<algorithm>using namespace std;vector<int> pre;int n, k;struct node { node *l, *r; int ...
2019-02-17 12:56:00
272
原创 1131 Subway Map （30 point(s)）
题解spfa可以解，但是比较麻烦。最好还是暴力dfs.以下题解少考虑了情况，Pat给的测试数据还是太少了，所以过了。#include<iostream>#include<cstdio>#include<vector>#include<algorithm>#include<queue>using namespac...
2019-02-16 21:39:09
338
原创 1134 Vertex Cover （25 point(s)）
#include<iostream>#include<cstdio>#include<algorithm>#include<vector>using namespace std;int n, m, k, a, b, nv;vector<vector<int>> e;int main() { scanf("...
2019-02-16 18:36:21
178
原创 1133 Splitting A Linked List （25 point(s)）
#include<iostream>#include<cstdio>#include<vector>using namespace std;const int MAXN = 1e5;struct node { int data, nex;}t[MAXN]; vector<int> res[3];int n, k, x, fir...
2019-02-16 18:35:14
181
原创 1132 Cut Integer （20 point(s)）
#include<cstdio>#include<iostream> #include<string>#include<algorithm>using namespace std; typedef long long ll;ll n, a, b, c;string s;int main() { scanf("%lld", &a...
2019-02-16 18:34:05
183
原创 1130 Infix Expression （25 point(s)）
题解树的遍历，输出树的中序序列。#include<iostream>#include<cstdio>#include<string>#include<algorithm>#include<vector> using namespace std;const int MAXN = 22;int root, n; ...
2019-02-16 13:17:16
173
原创 1129 Recommendation System （25 point(s)）
题解set中erase函数的使用。#include<iostream>#include<set>#include<cstdio>using namespace std;const int MAXN = 5e4 + 10;struct node { int item, cnt; bool operator < (const nod...
2019-02-16 13:10:17
186
原创 1128 N Queens Puzzle （20 point(s)）
题解八皇后问题。#include<iostream>#include<cstdio>using namespace std;const int MAXN = 1e3 + 10;int a[MAXN];int k, n;int main() { scanf("%d", &k); for(int i = 0; i < k; ++i) ...
2019-02-16 12:36:03
177
原创 1126 Eulerian Path （25 point(s)）
#include<iostream>#include<cstdio>#include<queue>#include<vector>using namespace std;const int MAXN = 510;bool vis[MAXN];vector<vector<int>> e; int n, ev...
2019-02-15 19:12:24
171
原创 1127 ZigZagging on a Tree （30 point(s)）
题解树的遍历变形。#include<iostream>#include<cstdio>#include<vector>using namespace std;int n;vector<int> in, post;vector<vector<int>> level;void getlevel(int ...
2019-02-15 18:06:55
182
1
原创 1125 Chain the Ropes （25 point(s)）
#include<cstdio>#include<iostream>#include<vector>#include<algorithm>using namespace std;vector<int> t;int n, res;int main() { scanf("%d", &n); t.resize(n)..
2019-02-15 18:05:21
175
1
原创 1124 Raffle for Weibo Followers （20 point(s)）
#include<iostream>#include<cstdio>#include<string>#include<map>using namespace std;int m, n, s, flag;string name;map<string, bool> have;int main() { scanf("%d...
2019-02-15 18:04:11
220
1
原创 1122 Hamiltonian Cycle （25 point(s)）
题解哈密顿回路。由指定的起点前往指定的终点，途中经过所有其他节点且只经过一次。在图论中是指含有哈密顿回路的图，闭合的哈密顿路径称作哈密顿回路，含有图中所有顶点的路径称作哈密顿路径。判断给出方案的连通性与环路判断。#include<cstdio>#include<iostream>#include<vector>using namespac...
2019-02-15 16:20:01
176
原创 1123 Is It a Complete AVL Tree （30 point(s)）
题解完全AVL树。考察AVL树的建树与完全性判断。 #include<cstdio>#include<iostream>#include<algorithm>#include<queue>using namespace std;struct node { node *l, *r; int v;};node* rot...
2019-02-15 16:17:39
174
1
原创 1121 Damn Single （25 point(s)）
#include<iostream>#include<set>#include<vector>using namespace std;int main(){ int n, a, b, m; scanf("%d", &n); vector<int> couple(100000, -1); for(int i = 0; i ...
2019-02-15 10:25:03
174
原创 1120 Friend Numbers （20 point(s)）
题解模拟题。#include<iostream>#include<cstdio>#include<set>using namespace std;set<int> res;int getsum(int x) { int ret = 0; while(x) ret += x % 10, x /= 10; return r...
2019-02-15 10:22:54
152
原创 1119 Pre- and Post-order Traversals （30 point(s)）
题解怎么确定是否有唯一的树， 其实就是看除了叶子以外的每个节点是否都有两个儿子， 因为有一个儿子的话，它既可以是左儿子也可以是右儿子。当不唯一时，全部当右儿子看待。#include<iostream>#include<cstdio>#include<vector>using namespace std;vector<int>...
2019-02-12 18:24:41
258
原创 1118 Birds in Forest （25 point(s)）
题解并查集。#include<cstdio>#include<iostream>#include<algorithm>using namespace std;const int MAXN = 1e4 + 10;int father[MAXN], book[MAXN], cnt[MAXN];int find(int x) { retur...
2019-02-12 17:40:59
171
原创 1117 Eddington Number （25 point(s)）
题解题意比较难理解。假设骑车E天，则这E天内每天所骑行距离必须大于E。（E是动态变化的）#include<iostream>#include<cstdio>#include<vector>#include<algorithm>using namespace std;int n;int main() { scanf("%...
2019-02-12 17:39:16
208
原创 1116 Come on! Let's C （20 point(s)）
#include<iostream>#include<map>#include<cstdio>#include<cmath>using namespace std;const int MAXN = 1e5;int ran[MAXN];map<int, bool> have;int n, k, x;bool ispr...
2019-02-12 17:35:59
143
原创 1115 Counting Nodes in a BST （30 point(s)）
题解BST建树。#include<iostream>#include<cstdio>using namespace std;const int MAXN = 1e3 + 10;int level[MAXN];int maxdepth, n;struct node { node *l, *r; int v;}; node* build(int...
2019-02-11 18:03:25
167
原创 1114 Family Property （25 point(s)）
题解模拟题。#include<iostream>#include<cstdio>#include<algorithm>using namespace std;const int MAXN = 1e5;struct node { int id, fat, mot, num, people; int child[8]; double a...
2019-02-11 17:48:22
214
ACM常用模板
2018-04-21
pat乙级1070代码有测试点过不了，求教
2017-03-04
TA创建的收藏夹 TA关注的收藏夹
TA关注的人