刷题列表课程来源AcWing
其中AcWing中的题目为翻译好的中文题目
- PAT甲级刷题记录-(AcWing)-Day17(基础算法 8题)
- 1091 Acute Stroke
- 1148 Werewolf - Simple Version
- 1051 Pop Sequence
- 1055 The World's Richest
- !!!1057 Stack
- 1117 Eddington Number
- 1044 Shopping in Mars
- 1040 Longest Symmetric String
AcWing链接
PAT链接
英语单词
解析
使用宽度优先来搜索
得到连通块的数量
注意点
#include1148 Werewolf - Simple Version#include using namespace std; int edge[60][1286][128]; int m, n, l, t; struct Node { int x, y, z; }; queue q; int d[][3] = { {0, 0, 1}, {0, 0, -1}, {0, 1, 0}, {0, -1, 0}, {1, 0, 0}, {-1, 0, 0}, }; int bfs(int x, int y, int z) { q.push({x, y, z}); edge[x][y][z] = 0; int res = 1; while (!q.empty()) { auto node = q.front(); q.pop(); for (int i = 0; i < 6; ++i) { int a = node.x, b = node.y, c = node.z; a += d[i][0], b += d[i][1], c += d[i][2]; if (a >= 0 && b >= 0 && c >= 0 && a < l && b < m && c < n && edge[a][b][c]) { q.push({a, b, c}); edge[a][b][c] = 0; res++; } } } return res; } int main() { cin >> m >> n >> l >> t; for (int i = 0; i < l; ++i) { for (int j = 0; j < m; ++j) { for (int k = 0; k < n; ++k) { cin >> edge[i][j][k]; } } } int res = 0; for (int i = 0; i < l; ++i) { for (int j = 0; j < m; ++j) { for (int k = 0; k < n; ++k) { if (edge[i][j][k]) { int cnt = bfs(i, j, k); if (cnt >= t) res += cnt; } } } } cout << res; return 0; }
AcWing链接
PAT链接
英语单词
解析
因为N很小只有100的数量级, 所以可以枚举,
O
(
n
3
)
O(n^3)
O(n3)
注意点
#include1051 Pop Sequenceusing namespace std; const int N = 110; int n; int sf[N]; int main() { cin >> n; for (int i = 1; i <= n; ++i)cin >> sf[i]; for (int i = 1; i <= n; ++i) { for (int j = i + 1; j <= n; ++j) { int liars = 0, wolves = 0; // 枚举真正的狼人, 此时狼人为 i和j for (int k = 1; k <= n; ++k) { //查看有几个人在说谎, 狼人里面有几个在说谎 // printf("i = %d, j = %d k = %d sf = %dn", i, j, k, sf[k]); if (sf[k] < 0) { // k说某个人是狼人 // 判断k有没有说谎 if (sf[k] != -i && sf[k] != -j) { // k说的人里面没有狼人,他说谎了 // printf("k = %d, sf = %d k is a liarn", k, sf[k]); liars++; // 如果k是狼人,那么增加狼人中说谎的人数 if (k == i || k == j) wolves++; // printf("liars = %d, wolves = %dn", liars, wolves); } } else { // k说的对象是好人 if (sf[k] == i || sf[k] == j) { // k说的好人其实是狼人, k说谎了 // printf("k = %d, sf = %d k is a liarn", k, sf[k]); liars++; if (k == i || k == j) wolves++; // printf("liars = %d, wolves = %dn", liars, wolves); } } } // printf("liars = %d, wolves = %dn", liars, wolves); if (liars == 2 && wolves == 1) { cout << i << " " << j; return 0; } } } puts("No Solution"); return 0; }
AcWing链接
PAT链接
英语单词
解析
注意点
插入的序列为1到n, 使用一个栈s来模拟push和pop的过程
先将元素入栈, 然后检查栈头元素和给定的序列头是否相同,一直相同的话就出队 重复
结束后如果栈为空则序列合法,否则不合法
#include1055 The World’s Richest#include const int N = 1010; using namespace std; int m, n, k; int seq[N]; bool check() { stack s; for (int i = 1, j = 1; i <= n; ++i) { s.push(i); if (s.size() > m) return false; while (!s.empty() && s.top() == seq[j] ) { s.pop(); j++; } } return s.empty(); } int main() { cin >> m >> n >> k; while (k--) { for (int i = 1; i <= n; ++i) { cin >> seq[i]; } if (check()) puts("YES"); else puts("NO"); } return 0; }
AcWing链接
PAT链接
英语单词
解析
创建一个时间数组,记录每个age的人物链表,分别排序,最后按要求取最大值即可
注意点
#include!!!1057 Stack#include #include #include using namespace std; const int N = 210; int n, k, m; struct Person { string name; int age, wealth; bool operator<(const Person &p) const { if (wealth != p.wealth) return wealth > p.wealth; if (age != p.age) return age < p.age; return name < p.name; } }; vector year[N]; int main() { cin >> n >> k; while (n--) { string name; int age, wealth; cin >> name >> age >> wealth; year[age].push_back({name, age, wealth}); } for (auto &item:year) { sort(item.begin(), item.end()); } for (int j = 1; j <= k; ++j) { cin >> m; int start, end; cin >> start >> end; printf("Case #%d:n", j); int cnt[N]; memset(cnt, 0, sizeof cnt); bool suc = false; while (m--) { int t = -1; for (int i = start; i <= end; ++i) { if (cnt[i] < year[i].size()) { if (t == -1 || year[i][cnt[i]] < year[t][cnt[t]]) { t = i; } } } if (t == -1) break; auto &p = year[t][cnt[t]]; cnt[t]++; printf("%s %d %dn", p.name.c_str(), p.age, p.wealth); suc = true; } if(!suc) puts("None"); } return 0; }
AcWing链接
PAT链接
英语单词
解析
用两个堆来模拟
注意点
1117 Eddington NumberAcWing链接
PAT链接
英语单词
解析
注意点
这边是超过E, 第一遍写成大于等于E了
#include1044 Shopping in Mars#include using namespace std; const int N = 100010; int day[N]; int n; int main() { cin >> n; int res = 0; for (int i = 1; i <= n; ++i) { cin >> day[i]; } sort(day + 1, day + n + 1, greater ()); for (int i = n; i >= 1; i--) { if (day[i] > i) { cout << i; return 0; } } puts("0"); return 0; }
AcWing链接
PAT链接
英语单词
解析
因为输出的是1-5这种形式,所以只要考虑哪个区间的和刚好大于等于m即可(避免考虑从左边切开链条和从右边切开链条的情况), 所以可以使用前缀和的思想,s[1]存放从1的价值,s[2]存放1-2的价值,s[n] - s[m]存放从m + 1 ~ n的价值
注意点
#include1040 Longest Symmetric Stringusing namespace std; const int N = 100010; int n, m; int s[N]; int main() { cin >> n >> m; for (int i = 1; i <= n; ++i) { cin >> s[i]; s[i] += s[i - 1]; //前缀和 // s[1] = 1 // s[2] = 1 - 2 // s[n] = 1 - n // s[n] - s[m] = m + 1 ~ n } int res = 0x3f3f3f3f; for (int i = 1, j = 0; i <= n; ++i) { // 让j不断变大,找到大于等于m的最小值 // 因为不知道区间里面是否存在刚好等于m的 // 遍历 i~j之间的价值,找到第一个大于等于m的 while (j < n && s[j] - s[i - 1] < m) j++; // 因为j = n的时候没判断过是否满足 if (s[j] - s[i - 1] >= m) res = min(s[j] - s[i - 1], res); } for (int i = 1, j = 0; i <= n; ++i) { while (j < n && s[j] - s[i - 1] < m) j++; // 因为j = n的时候没判断过是否满足 if (s[j] - s[i - 1] == res) { cout << i << "-" << j << endl; } } return 0; }
AcWing链接
PAT链接
解析
因为字符串在1000以内,所以可以枚举来做
使用双指针,遍历字符串,选取每一个点作为回文串的中心的,依次向两边拓展,记录最大值
枚举的时候要注意
回文串有奇数和偶数两种请客
奇数的中心点为i,左右指针为i-1,i+1
偶数的左指针为i,右指针为i+1;
所以每个点这两种情况都要枚举到
注意点
#includeusing namespace std; int main() { string s; getline(cin, s); int res = 0; for (int i = 0; i < s.size(); ++i) { int l = i - 1, r = i + 1; while (l >= 0 && l < s.size() && r < s.size() && s[l] == s[r]) l--, r++; res = max(res, r - l - 1); l = i, r = i + 1; while (l >= 0 && l < s.size() && r < s.size() && s[l] == s[r]) l--, r++; res = max(res, r - l - 1); } cout << res << endl; return 0; }
