POI2006合集

POI2006

2023.11.28～2023.12.01

不知道按什么顺序，不如就直接洛谷题号了。

P3434 [POI2006] KRA-The Disks

老早做的题。模拟一下然后二分似乎就好了。

平凡。

P3435 [POI2006] OKR-Periods of Words

有经典结论：$S[1,p]$ 是 Border 等价于 $|S|-p$ 是 $S$ 的周期。

跑 KMP 以后维护集合里的最小 border 即可。

P3436 [POI2006] PRO-Professor Szu

反向边，缩点以后跑拓扑即可。

P3437 [POI2006] TET-Tetris 3D

二维线段树板题。

P3438 [POI2006] ZAB-Frogs

斜率优化。

https://wgyhm.top/2023/11/28/bzoj1514-POI2006-ZAB-Frogs/

P3439 [POI2006] MAG-Warehouse

注意到转为曼哈顿距离以后 $x,y$ 坐标独立。取带权中位数即可。

P3440 [POI2006] SZK-Schools

简单费用流。

P3441 [POI2006] MET-Subway

先取直径，然后转化为选择 $2l-1$ 条到直径的路径。

拿堆维护一下即可。

P3442 [POI2006] NAJ-The Invasion

凸包，通过二分和差分先预处理两个点向量逆时针上的价值和，计算三个点贡献的时候用全部的减去在外面的。

https://wgyhm.top/2023/12/01/bzoj1518-POI2006-Naj-The-Invasion/

P3443 [POI2006] LIS-The Postman

观察到没有重边，所以把一条路径缩成一起，维护每条边的前驱后继，然后新建图跑欧拉回路即可。

P3444 [POI2006] ORK-Ploughing

感觉妙妙，等等。贺完了。

观察到一种可能的删除，一定是删完所有行（列），删一部分列（行），剩下没删的一定是连续的一段区间。

我们不妨设删完的是行，令 $f_{l,r}$ 表示还剩下列 $[l,r]$，在尽量删的前提下剩下区间 $f_{l,r}$。容易发现尽量删的贪心策略是对的。

由于我们有尽量删的前提，所以对于列 $[l,r]$ ，它的剩下区间 $[l,r]$ 一定是固定的。这一点我们可以反证。

考虑转移，显然 $[l,r]$ 可以从 $[l-1,r]$ 和 $[l,r+1]$ 转移过来。如果可以直接删，那么就可以转移。前缀和维护一下即可。

为了保证尽量删就暴力删除。均摊下来是 $O(nm)$ 的。

然后交换一下行列再做一遍即可。

本题的关键在于，找到最终答案的特殊形式（可以叫做性质？），然后贪心结合递推处理。

P3445 [POI2006] TAN-Dancing in Circles

感觉困难，等等。

P3446 [POI2006] EST-Aesthetic Text

暴力 dp，维护前后缀最小值，拆绝对值直接做。

P3447 [POI2006] KRY-Crystals

按位，感觉高妙。

P3448 [POI2006] MIS-Teddies

暴力 dp。

P3449 [POI2006] PAL-Palindromes

我的做法很愚蠢啊。

先 mancher 跑出每个点的后缀是否是回文串，然后扔到字典树上。观察到如果两个串加起来要是回文串，一定是一个包含倒着的另一个，然后多出的部分本身是回文串。算下贡献就好了。

不过好像不依赖串本身是回文串的性质。

P3450 [POI2006] ZOS-Sophie

没人做，我也先不做了。