2025 CCH非专业级软件能力认证提高级第六轮总结
DFbd
·
·
个人记录
骗分大失败。
挂的最难受的一场，没开long long，200->140。
预期：100 + 36 + 40 + 0
实际：100 + 0 + 40 + 0
T1
原题又没找到，题意就是有一个 $n \times n$ 的矩形和 $q$ 次操作，每次给一个左上顶点为 $(r,c)$、直角边长为 $l$ 的下三角区域加上 $s$，求最终矩阵的异或和。
很容易想到 $\mathcal{O}(nq)$ 的做法，每次操作枚举行，再用差分。
写完还想了想感觉过不了，但是可以拿不少分就走了，这时15min。
想T2时突然又会 $O(q)$ 了就回来了。
我们发现，每次操作都是将差分数组的某一列的一段和一条斜线的一段加上某个值。
于是我们再对差分数组做一个列的差分和斜线的差分，最后还原出差分数组，再还原出矩阵，就可以求异或和。
写完正好1h。
```cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int kMaxN = 1e3 + 5, kMaxM = 3e5 + 5;
int n, q, r, c, l;
ll s, d1[kMaxN][kMaxN], d2[kMaxN][kMaxN], ans;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
for (cin >> n >> q; q; q--) {
cin >> r >> c >> l >> s;
d1[r][c] += s;
d1[min(n + 1, r + l)][c] -= s;
d2[r][c + 1] += s;
d2[min(n + 1, r + l)][min(n + 1, c + l + 1)] -= s;
}
for (int j = 1; j <= n; j++)
for (int i = 1; i <= n; i++)
d1[i][j] += d1[i - 1][j];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
d2[i][j] += d2[i - 1][j - 1];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
d1[i][j] += d1[i][j - 1] - d2[i][j];
ans ^= d1[i][j];
}
cout << ans;
return 0;
}
```
### T2
原题是没有 Alice 和 Bob 的，老师给我们加上了，使这题又多了几分博弈的色彩😋
[原题](https://www.codechef.com/problems/RMVNUMBERS)
开题想了很久，没有头绪，只能暴力。
首先暴搜，$O(2^mn)$，拿到24pts。
然后看性质A，显然当 $m = 1$ 时就 $\mathcal{O}(n)$ 求一下，否则答案必然是 $0$，再加12pts。
性质B没看出来，于是输出0了，可以拿到60pts高分。
**但是我long long没开全**
后来发现，当 $m > 28$ 时，答案必然是0。
这个是可以证的，~~读者自证不难~~这里就不写了。
### T3
开题->暴力启动！
原题没找到，题意是有 $n$ 个点，若两个点的值的 $\gcd$ 为合数，则这两点间有连边。可以删去任意一个节点，求剩下的节点中最大连通块的节点数的最小值。
直接枚举两个点，然后求个 $\gcd$，写个线性筛判下是不是合数，然后枚举删掉的点，再暴力求连通块。
拿到40pts。
### T4
13~16的性质看错了，以为答案是0，能拿20pts。
结果当然是什么都没有。
## 总结
**一定要开long long**
又一次血的教训，都这么久了还能不开long long见祖宗，我也是神人了。