POI2009合集
2023.12.06～2023.12.07
没和 08 接上是因为去做了写 bitset 和 dp 题目锻炼一下科技和马力。
感觉 bitset 很有前途啊！
有一道计算几何，其他都是没什么人做的，有这时间不如做点典题。
P3479 [POI2009] GAS-Fire Extinguishers
注意到一个位置可以放多个灭火器。
考虑贪心，放在深度更小的地方更优。如果当前子树中存在深度为 $k$ 没被覆盖就在这个点放若干个灭火器。
记 $f_{x,i}$ 表示 $x$ 的子树内深度为 $i$ 需要灭火器的个数，$g_{x,i}$ 表示 $x$ 的子树深度为 $i$ 内放灭火器且还没有覆盖过别的点的可以灭火的个数。
然后还要记得转移自己作为 lca，子树间的。
注意到每次转移一定要贪心的转移距离为 $k$ 的，不然会出错。复杂度 $O(nk)$。
P3480 [POI2009] KAM-Pebbles
5 分钟快速丹砂，感觉是最会博弈论的一集。
看到单调递增考虑差分，也就是保证差分数组始终 $>0$。
考虑一个位置 $i$ 减少 $x$，放在差分数组上就是 $i$ 到 $i+1$ 移动 $x$ 个。这就是阶梯 nim 博弈了。
差点被数据范围诈骗。复杂度 $O(n)$。
P3482 [POI2009] SLO-Elephants
之前做的。经典套路 $(i,p_i)$ 连边看成一堆环。然后分类讨论。复杂度 $O(n)$。
P3485 [POI2009] BAJ-The Walk of Bytie-boy
序列上怎么做？抛开在图上不太可行的 manacher，考虑区间 dp。
令 $f_{x,y}$ 表示从 $x\to y$ 的最短回文路径。转移枚举 $l\to x,y\to r$，如果经过同样的字母，就 $f_{l,r}\gets\min f_{x,y}+2$。
但是这样复杂度应该是 $O(m^2)$ 的，没有前途。
考虑转移拆成两部分，令 $f_{x,y}$ 还是表示 $x\to y$ 的最短回文路径，$g_{x,y,c}$ 表示 $x\to z\xrightarrow{c} y$ 且 $x\to z$ 是回文路径的最短路径。
有转移：
$f_{z,y}\gets \min{ g_{x,y,c}}+1,z\xrightarrow{c}x$。
$g_{x,z,c}\gets \min {f_{x,y}},y\xrightarrow{c}z$。
用 bfs，且实现的好的话，每个状态只会被转移一次。复杂度 $O(nm+26n^2)$。
为了保证复杂度正确，最好对每条边的起点和边权存终点，减少转移的冗余。
P3486 [POI2009] KON-Ticket Inspector
转化成最少检不到的人数。然后令 $f_{i,j}$ 表示上一个检查在 $i$ ，检查了 $j$ 个，暴力枚举转移点，转移的价值用二维前缀和预处理一下即可。复杂度 $O(n^2k)$。
P3487 [POI2009] ARC-Architects
第 $i$ 个数为在 $[b_{i-1}+1,n-i+1]$ 中最大的数。
发现可以单调队列。复杂度 $O(n)$。注意别开 O2。
P3488 [POI2009] LYZ-Ice Skates
丹砂！虽然好像很水。
Hall 定理，对于任意的集合，后面忘了。
但是其实集合的限制不如区间，因为任意区间满足了任意集合一定满足（把集合空的补满的限制更强），转化为 $\forall l\le r,\sum\limits _{i=l}^r a_i\le (r-l+1+d)\cdot k$，移项有 $\sum a_i-k\le d\cdot k$，也就是求最大子段和。
线段树维护即可，复杂度 $O((n+m)\log n)$。
P3489 [POI2009] WIE-Hexer
观察到 $p$ 很小，直接状态压缩。然后跑 dj 。
复杂度 $O((n+m)2^pp\log (n+m))$，反证能过。
P3492 [POI2009] TAB-Arrays
观察到每一行/列的元素集合组成不变。
每个数不同，所以随便判一下就好了。复杂度 $O(n)$。