POI2010合集

2023.12.07～2023.12.08

这年感觉有点简单啊。除了一个 Pollard-Rho 用了点科技。

有两个没人做的题目就不写了。

P3496 [POI2010] GIL-Guilds

发现灰色是没有用的，于是贪心就好了。

P3497 [POI2010] KOL-Railway

双栈排序。记 $s_i=\min\limits_{j=i}^n a_i$。

发现如果 $i<j$ 且 $s_{j+1}<a_i<a_j$ 那么 $i,j$ 不在一个栈中。这启发我们对不合法的 $(i,j)$ 建边，最后贪心的染色判断是否是二分图。

但是建边是 $O(n^2)$ 的，考虑能不能建出来一片森林，先给每个点染上一个颜色，然后在做答案的时候判断合法性。

观察到 $s_{j+1}$ 是不降的，考虑维护每个连通块内的最小值大于 $s_{j+1}$ 的最小值和那个点。找到 $< a_i$ 的连通块，然后连边合并。这样我们只会连 $O(n)$ 条边。

我们需要的支持的操作有，弹出最小值，找到最小值，合并两个连通块，考虑可并堆。复杂度 $O(n\log n)$。

P3498 [POI2010] KOR-Beads

发现串的个数是 $O(n\ln n)$ 的，于是我们可以暴力哈希，拿 map 判重。

写完以后感觉可以字典树，似乎更好一点。复杂度 $O(n\log ^2n)/O(n\log n)$。

P3499 [POI2010] NAJ-Divine Divisor

Pollard-Rho 直接干。

注意到 $2^k$ 可能会爆，所以用 long double 以后转 string。

P3500 [POI2010] TES-Intelligence Test

模拟。

P3501 [POI2010] ANT-Antisymmetry

mancher。或者暴力哈希，但是感觉哈希没有前途。

P3502 [POI2010] CHO-Hamsters

KMP 搞一下两两后缀和前缀的最长相同的，然后矩阵优化转移，复杂度 $O(n|S|+n^3\log m)$。

P3503 [POI2010] KLO-Blocks

观察到就是让我们求满足 $[l,r],\sum\limits _{i=l}^r a_i-k\ge 0$ 的最大区间。

先预处理出 $a_i-k$ 的前缀和。发现对于升序左端点 $l$，它满足的右端点一定是单调的才能对答案有贡献。预处理后缀最大值之后双指针。

复杂度 $O(nm)$。

P3504 [POI2010] OWC-Sheep

预处理出在 $i,j$ 逆时针上的点的个数。具体参考 [POI2006]Naj-the Invasion。复杂度 $O(nm\log n+n^2)$。

然后区间 dp 就好了，条件是转移的三角形内部的偶数且三角形的边上没有点。

复杂度 $O(nm\log n+n^3)$。

P3505 [POI2010] TEL-Teleportation

转化成分层图，然后贪心。

P3506 [POI2010] MOT-Monotonicity 2

同 https://wgyhm.top/2023/11/14/P8277-USACO22OPEN-Up-Down-Subsequence-P/。

但是要输出方案，还是用线段树好写一点。复杂度 $O(n\log w)$。

P3509 [POI2010] ZAB-Frog

单调队列预处理出每个点跳一步跳到的点，然后类似快速幂一样倍增过去。

复杂度 $O(n\log m)$。

P3511 [POI2010] MOS-Bridges

显然先二分答案，转化为判断可行性问题。

如果一张有向图存在欧拉路径，其充要条件为联通且每个点的入度等于其出度。先判断如果一个点的度数为奇数则无解，否则其出度和入读就要等于它的度数除以 $2$。

这样就很网络流了！对于每条边新建一个节点 $e$，连边 $(S,e,1)$ 来限制流量。如果 $l\le mid$，连边 $(e,y,1)$；如果 $p\le mid$，连边 $(e,x,1)$。最后对于每个点，连边 $(i,T,\dfrac{deg_i}{2})$。如果跑满则存在一组解。

最后跑欧拉回路就好了。注意欧拉回路的 dfs 过程是要先搜再入栈，最后倒着输出。

复杂度 $O(m\sqrt m\log v)$，由于是网络流则显然跑不满。

P3512 [POI2010] PIL-Pilots

发现黄题也很难啊。

双指针，最大值最小值用单调队列维护。

感觉 POI 很喜欢考奇怪的线性数据结构，而且都是我不太熟练的。前面的单调队列和单调栈，还有前两年的神秘带权并查集。