-
9 30
- P2194
- 很显然的强连通分量
- P4168
- 考虑分块，预处理出每种颜色在每个整块中的出现次数，定义 \(p_{l,r}\) 为在第 \(l\) 块到第 \(r\) 块中出现次数最多的颜色
- 可以发现可以做到 \(O(N \sqrt{N})\)
- 下午vp mx模拟赛
- 两个小时写了一场模拟赛的前三道口胡了第四题，没什么有意义的记录
- P2194
-
10 1
- P2766
- 十分常见的网络流套路题，拆点即可
- P1391
- 考虑枚举第一行的状态，接下来的每个数都能知道是什么了
- P6034
- 考虑对式子 \(a \equiv b \mod(a \oplus b)\) 进行分解可以发现它就是说 \(a\) 在二进制位上为 1 的数的集合是 \(b\) 在二进制上为 1 的个数的集合的子集
- 数位 DP 求解即可
- P3977
- 读题十分困难，准确来说我一开始把行看成从 1 开始导致浪费了半个小时的时间
- 那么我们就可以发现当前行只会影响上面一行和下面一行，故可以算出当当前行的状态为 \(s\) 的时候下一行可以是哪些 \(t\)，然后矩阵乘法即可
- P3422
- 一眼倍增后发现这题卡空间，没有办法只得另辟蹊径
- 很常见的套路为斩环为链
- 我们可以发现这个等价于任意的 \(\sum p_i - \sum d_i >= 0\) 等价于 \(\min(\sum p_i - \sum d_i) >= 0\)
- 那么我们就可以令 \(a_i = p_i - d_i\)，用 \(sum_i = \sum a_i\) 用单调队列求出左边第一个大于自身的 \(sum_j\)
- 统计答案即可
- P2766
-
10 2
- 难泵，一开始自以为掌握了 T1 的60-80分的暴力做法，和T2的正解然后就一直坐牢想T3结果后面写的时候发现全挂了（
- T1挂的点在于我把 \(f(n)\) 想成了 \(n\) 的约数个数加上 \(n-1\) 的约数个数
- 后面发现很显然是有反例的（
- T2挂的点在于求解 \(p = 2\) 的时候我忽略了喇叭从多个跑道来的时候会互相影响答案
- T1挂的点在于我把 \(f(n)\) 想成了 \(n\) 的约数个数加上 \(n-1\) 的约数个数
- P2219
- 二维单调队列
- 核心思想是从固定长度一维数组求最值变成了固定矩阵形态，二维数组求最值
- 先对行求出最值，再对列求出最值
- \(s_{i,j}\) 是原数组， \(dis_{i,j}\) 是行最值数组，\(f_{i,j}\) 是矩阵最值数组
-
long long cnt = b - d - 1, tmp = a - c - 1; for (long long i = 1; i <= n; i++) {long long h = 1, t = 0;for (long long j = 1; j <= m; j++) {for (; h <= t && j - q[h] + 1 > cnt; h++) {}for (; h <= t && s[i][j] <= s[i][q[t]]; t--) {}q[++t] = j;if (h <= t) {dis[i][j] = s[i][q[h]];}} } for (long long j = 1; j <= m; j++) {long long h = 1, t = 0;for (long long i = 1; i <= n; i++) {for (; h <= t && i - q[h] + 1 > tmp; h++) {}for (; h <= t && dis[i][j] <= dis[q[t]][j]; t--) {}q[++t] = i;if (h <= t) {f[i][j] = dis[q[h]][j];}} }
- 二维单调队列
- P2765
- 很显然答案是具有单调性的，故可以二分
- 我们可以拆点若 \(i < j\) 且 \(i + j\) 为完全平方数则让 \(i\) 向 \(j+n\) 连一条流量为1的边
- 然后我们知道 最小路径覆盖=总点数-最大匹配 则本题结束
- p4474
- 可以很容易的发现我们无法弄到相邻的点
- 则可以奇偶分点，然后求最大权的独立集
- 难泵，一开始自以为掌握了 T1 的60-80分的暴力做法，和T2的正解然后就一直坐牢想T3结果后面写的时候发现全挂了（
