2020.10.21新生赛（十一）题解

1. CF501B Misha and Changing Handles

这道题就是人们要在cf上面不断地更换自己的昵称。一定好好读一读输入和输出的要求，有时候不仅仅是格式，而且会给一些限制条件，会简化这个题目。

这道题把新昵称作为键，旧昵称作为值。 对于map<string, string>不存在的键值对，m[a] 默认为“”，即空字符串。 删除键值对，可以只在 erase() 函数的参数写入键即可，不一定非要写入键值对。 另外我看了一下每个测试样例的时间，发现最终显示的结果时间并非平均时间，而是程序运行最大时间。

#include<iostream> #include<map> #include<string> using namespace std; map<string, string> m; int main() { int Q; cin >> Q; string a, b; while (Q--) { cin >> a >> b; if (m[a] != "") m[b] = m[a]; else m[b] = a; m.erase(a); } cout << m.size() << endl; for (auto p : m) { cout << p.second << ' ' << p.first << endl; } return 0; }

2.Divisors of Two Integers CodeForces - 1108B

（1）如果 a 不是 b 的倍数，那么从后往前遍历，找到第一个不能整除的。如果a 是 b 的倍数，那么从后往前遍历，找到第一个出现了两次的数。

#include<cstdio> #include<algorithm> using namespace std; int main() { int N; int a[130]; scanf("%d", &N); for (int i = 0; i < N; i++) { scanf("%d", &a[i]); } sort(a, a + N); for (int i = N - 1; i > 0; i--) { if (a[N - 1] % a[i] || a[i] == a[i - 1]) { printf("%d %d\n", a[N - 1], a[i]); break; } } return 0; }

3.CF556A Case of the Zeros and Ones

（1）记住，abs函数是在 stdlib.h 中定义的。 （2）用C++17比C++11更好更快一些。 （3）这道题的思路是，因为一对儿0和1可以消除，所以可以计算有多少个1，假设有 cnt 个，那么0的个数是 N - cnt 个，若 1 的个数多，那么答案就是 $2\ast cnt-N$；若1的个数多，答案就是 $N-2\ast cnt$;

#include<cstdio> #include<cmath> using namespace std; int main() { int N; scanf("%d", &N); getchar(); int cnt = 0; char tmp; for (int i = 0; i < N; i++) { tmp = getchar(); cnt += tmp - '0'; } int ans = abs(N - cnt - cnt); printf("%d\n", ans); return 0; }

4. Quadcopter Competition CodeForces - 883M

（1）这道题绕开就可以了，很简单的模拟题。 （2）这道题有一个地方容易错，就是当x1 == x2，或是 y1 == y2 的时候。因此用$max(abs(x1-x2),1)$ 避免这种特殊情况。

#include<cstdio> #include<cstdlib> #include<algorithm> using namespace std; int main() { int x1, y1, x2, y2; scanf("%d%d%d%d", &x1, &y1, &x2, &y2); int ans = (max(abs(x1 - x2), 1) + max(abs(y1 - y2), 1) + 2) * 2; printf("%d\n", ans); return 0; }

5. Square Filling CodeForces - 1207B

（1）不用考虑左上左下右上右下四个方向，只考虑右下一个就行了，因为题目说了，1 <= x < n，1 <= y < n；因此不用考虑最后一行与最后一列。 （2）先对矩阵按照题目要求操作一遍。每次把 $field[i,j],field[i+1,j],field[i,j+1],field[i+1,j+1]$ 都置为1。这样子可以得到操作的步骤。然后判断所得矩阵是否都为1。否则输出-1.

#include<cstdio> #include<vector> using namespace std; int vis[55][55], field[55][55]; vector<int> vx, vy; int main() { int N, M; scanf("%d%d", &N, &M); for (int i = 1; i <= N; i++) { for (int j = 1; j <= M; j++) { scanf("%d", &field[i][j]); } } for (int i = 1; i < N; i++) { for (int j = 1; j < M; j++) { if (field[i][j] && field[i + 1][j] && field[i][j + 1] && field[i + 1][j + 1]) { vis[i][j] = vis[i + 1][j] = vis[i][j + 1] = vis[i + 1][j + 1] = 1; vx.push_back(i), vy.push_back(j); } } } for (int i = 1; i <= N; i++) { for (int j = 1; j <= M; j++) { if (field[i][j] != vis[i][j]) { printf("-1\n"); return 0; } } } int sz = vx.size(); printf("%d\n", vx.size()); for (int i = 0; i < sz; i++) printf("%d %d\n", vx[i], vy[i]); return 0; }

6.Middle Class CodeForces - 1334B

（1）这道题想明白了之后，就是全部都减去x，然后从后往前遍历，看看什么时候sum<0即可。注意 cnt 和 if 判断句的位置。

#include<cstdio> #include<algorithm> using namespace std; typedef long long ll; int a[100005]; int T, N, X; void solve() { sort(a, a + N); ll sum = 0; int cnt = 0; for (int idx = N - 1; idx >= 0; idx--) { sum += a[idx]; if (sum < 0) break; cnt++; } printf("%d\n", cnt); } int main() { scanf("%d", &T); while (T--) { scanf("%d%d", &N, &X); for (int i = 0; i < N; i++) { scanf("%d", &a[i]); a[i] -= X; } solve(); } return 0; }