POI2012合集

感觉 loj 的 POI 的题面做的很好啊，spj 很全而且还可以下载数据。

反观某沙比网站。

P3530 [POI2012] FES-Festival

加深了对差分约束的理解。

这种不等式关系考虑建出来差分约束。如果两个点不在一个强连通分量之中，也就是两点之间有且仅有若干条同样的有向路径，此时两者上下限只能确定一个，所以两者实际上只有大小关系。而如果两个点在一个强连通分量，此时两者是有上下限关系的，而在本题中，两者的最短路虽然只表示两者的差值，却也反映了至少经过多少个不同的 $1$ 的边。

不在两个不同的强连通分量一定可以两两不同，因为两者只有大小关系。

所以答案就是在同一个连通块中，两两最短路的最大值 $+1$ 之和。

复杂度 $O(n^3)$。瓶颈在 Floyd。

注意一开始要把 $d_{i,i}=0$。

P3531 [POI2012] LIT-Letters

本来想着直接拿树状树组贪心的模拟一手，然后看了眼题解发现是逆序对。树状树组维护一下即可。复杂度 $O(n\log n)$。

警戒！

P3532 [POI2012] ODL-Distance

$d(x,y)=g(x)+g(y)-2\times g(\gcd(x,y)),g(x)$ 表示 $x$ 的质因子个数。

然后枚举 $\gcd$ 即可。如果没有重复的数字的话复杂度 $O(w\ln w)$，有的话应该是 $O(w^{4/3})$ 但是跑不满。

P3533 [POI2012] RAN-Rendezvous

根据环和树分开讨论。树上倍增，还要判联通什么的，有点烦。

P3534 [POI2012] STU-Well

考虑二分答案 $k$。然后先把 $a_i>a_{i-1}+k$ 和 $a_i>a_{i+1}+k$ 的给调整完，再枚举最后要变成 $0$ 的点。

对答案产生另外的影响的，就是从这个点 $i$ 划出两条斜率为 $k,-k$ 的直线的上面的点。

注意到枚举的点往右移动，产生影响的区间是不往左的。双指针指一下即可。复杂度 $O(n\log w)$。

P3535 [POI2012] TOU-Tour de Byteotia

先把两个点都 $>k$ 的边缩在一起。然后剩下的至少有一个端点 $\le k$。考虑能加边就加边。用并查集维护。

复杂度 $O(n)$。

P3536 [POI2012] BON-Vouchers

记录每个数 $x$ 枚举到哪里。然后最多枚到 $10^6$。

发现复杂度是 $O(10^6\sum \dfrac{1}{i})$ 的，就可以过了。

P3537 [POI2012] SZA-Cloakroom

把 $a$ 排序。离线下来。

如果状态设为 $01$ 就太 dinner 了。但是观察到 $b_i$ 有单调性。

令 $f_j$ 表示选出物品和为 $j$，$b_i$ 的最小值最大是 $f_j$。复杂度 $O(q\log q+nk)$。

P3538 [POI2012] OKR-A Horrible Poem

第一眼看成求子串的最大 border，感觉非常不可做啊。被 fxt 提醒是倍数关系才有点思路。

如果直接枚举因数的话很不可以啊。观察到如果 $\dfrac{n}{p}$ 是周期，$\dfrac{n}{q}$ 是周期，那么 $\dfrac{n}{pq}$ 也是周期。其实就是 $p+q\le n$ 那么 $\gcd(p,q)$ 也是周期这个定理。

然后枚举质因数即可。复杂度 $O(n+qw(n))$。感觉有点卡。

P3539 [POI2012] ROZ-Fibonacci Representation

考虑贪心的选择 $F(i)$ 使得 $|F(i)-n|$ 最小。

证明看题解吧。复杂度 $O(T\log n)$。

P3540 [POI2012] SQU-Squarks

先把 $a$ 排个序。手玩一下发现只需要知道第一个数就可以推出来所有数。

$a_1$ 是最小值+次小值，$a_2$ 是最小值+第三小值，我们只需要枚举第二小值+第三小值，然后把三个值解出来，最后 $O(n^2\log n)$ 模拟即可。

又观察到第二小值+第三小值在序列中的位置不会超过 $n$。所以枚举即可。复杂度 $O(n^3\log n)$。

P3544 [POI2012] BEZ-Minimalist Security

考虑从特殊到一般。

如果一个环是必须要解方程的。所以我们设起点为 $x$，记录每个点的系数和常数，然后 bfs，维护未知数的存在区间。中间判断一定解是固定的情况和无解的情况。最后输出即可。

复杂度 $O(n+m)$。

P3546 [POI2012] PRE-Prefixuffix

不会求一个东西的时候能不能递推？

问题其实就是求最长的 $AB$，能否把字符串划分为 $ABtBA$，其中 $A,B$ 指两个字符串。

问题转化为求一些区间的 border。而这些区间都是以字符串中间对称的。

令 $s_i$ 表示 $s[i+1,n-i]$，$f_i$ 表示 $s_i$ 的最大 border。考虑从 $s_i$ 掐头去尾变成 $s_{i+1}$，最长的 border 减少两个。

例如 abcd…abcd 变成 bcd…abc。

因此有 $f_i\le f_{i+1}+2$。 考虑 $i$ 从大到小递推。每次 $f_i$ 最多增加 $2$。时间复杂度 $O(n)$。相等判断用哈希。求出 $f_i$ 就很好计算答案了。

P6612 [POI2012] LIC-Bidding

沙比 extern 交互。

考虑暴力 dp 来找到胜负关系。然后发现对于状态 $x+y$，$x$ 都是由 $2,3$ 的幂次方转移过来的。所以状态数非常少，大概是 $O(\log^2 n)$ 级别的。预处理有用的状态以后暴力转移即可。复杂度 $O(n\log ^2 n)$。