202111月做题总结

11.1 ~ 11.9

停竞赛课准备期中考试，最后才年级 $180$ ，自闭了。

11.10

11.11

【2020.11.22 NOIP模拟赛 T2】玩具

link

code

标签：

贪心 + 模拟

思路：

贪心的想，每次操作都把身体和脚尽量多的往前移动，这样就可以减少操作次数，然后模拟就行

【2020.11.22 NOIP模拟赛 T3】整除

link

code

标签：

同余最短路

思路：

用同余最短路做，从 $i$​ 向 $10i$​ 到 $10i + k - 1$ 连边，表示在后面加上 $0$ 到 $(k - 1)$​ ， 然后直接 $bfs$ ， 最小的数只需满足位数最小的情况下字典序最小，$bfs$ 可以实现.

【2020.11.22 NOIP模拟赛 T4】集合

link

code

标签:

并查集

思路:

对于每个集合维护对它进行的加操作和修改操作，要同时记录操作时间和操作值。对于合并两个集合用并查集维护，还要在边上记录合并时间，所以不能路径压缩。

对于询问操作, 通过在并查集上跳父亲找到最后一次在什么时候被覆盖，被覆盖为了多少，然后再从 $x$​ 开始不断跳父亲统计在最后一次覆盖之后的加法操作的贡献.

[USACO15JAN]Grass Cownoisseur G

link

code

标签：

缩点 + 拓扑排序

思路：

显然要先缩一下点，然后得到一个 $dag$ ， 然后考虑在 $dag$ 上做这道题。

根据 $dag$​ 的定义逆行后不会再经过逆行前的点，因为如果经过，那就说明从这个点能回到1点，但是从1点可以到达这个点，不符合 $dag$​ 的定义.

所以只需要对 $1$ 所在的 $scc$ 的前驱和后继分别跑一遍拓扑排序，然后通过逆行的边拼起来就行。即从 $1$ 所在的 $scc$ 开始跑后继，跑到一个点后逆行到前驱，然后从前驱回到 $1$, 显然只有走这样的路径才合法。

UVA11671 矩阵中的符号 Sign of Matrix

link

code

标签：

差分约数

思路：

考虑 $x_i$​​ 表示对于第 $i$​​ 行的操作， $y_i$​​ 表示对于第 $i$​​ 列的操作。值为 $+x$​​ 表示加 $x$​, 值为 $-x$​ 表示减 $x$​​​。

对于第 $i$ 行, 第 $j$​​ 列的格子。如果为 $+$ , 则 $x_i + y_i > 0$​ , 如果为 $0$ , 则 $x_i + y_i = 0$ , 如果为 $-$ , 则 $x_i + y_i < 0$.

考虑把它们转化成差分约束的形式。

$x_i + y_i > 0 \Leftrightarrow x_i - (-y_i) > 0$​​​

$x_i + y_i = 0 \Leftrightarrow x_i - (-y_i) = 0$​​

$x_i + y_i < 0 \Leftrightarrow -x_i - y_i > 0 \Leftrightarrow -y_i - x_i > 0$​​​

然后跑差分约束（有负环就无解），但是差分约束出来的只是可行解，不保证最优，考虑让它们最优。

只需要所有变量同时减去一个 $\Delta$​ , 原来的答案为 $\sum_{i=1}^{n}|x_i| + \sum_{i=1}^{n}|y_i|$​ , 加上 $\Delta$​ 后会变成 $\sum_{i=1}^{n}|\Delta-x_i| + \sum_{i=1}^{n} |\Delta - y_i|$​

根据初中数学知识，当 $\Delta$​ 为 所有 $x_i$​ 和 $y_i$​​ 构成的数列的中位数时最优。（绝对值的几何意义）

然后就求出答案啦。

11.12