当前位置：首页 > news >正文

9 30 -

news 2026/3/27 7:02:51

9 30
- P2194
  - 很显然的强连通分量
- P4168
  - 考虑分块，预处理出每种颜色在每个整块中的出现次数，定义 \(p_{l,r}\) 为在第 \(l\) 块到第 \(r\) 块中出现次数最多的颜色
  - 可以发现可以做到 \(O(N \sqrt{N})\)
- 下午vp mx模拟赛
- 两个小时写了一场模拟赛的前三道口胡了第四题，没什么有意义的记录
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\)
  - 统计答案即可
10 2
- 难泵，一开始自以为掌握了 T1 的60-80分的暴力做法，和T2的正解然后就一直坐牢想T3结果后面写的时候发现全挂了（
  - T1挂的点在于我把 \(f(n)\) 想成了 \(n\) 的约数个数加上 \(n-1\) 的约数个数
    - 后面发现很显然是有反例的（
  - T2挂的点在于求解 \(p = 2\) 的时候我忽略了喇叭从多个跑道来的时候会互相影响答案
- 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
  - 可以很容易的发现我们无法弄到相邻的点
  - 则可以奇偶分点，然后求最大权的独立集