POI2011合集
2023.12.8～2023.12.12
P3513 [POI2011] KON-Conspiracy
很久以前做的题。现在看都没什么思路啊。
我们要求的是把图划分成一个团和一个独立集的方案数。考虑先用 2-SAT 判无解和构造出一种方案。
观察到只有把团上的一个点换到独立集，独立集的一个点换到团，对调一个团上的点和独立集中的一个点。
如果存在独立集的两个点换到团，则这两个点之间一定没有边则不可能存在这种情况。
暴力枚举，有点细节。复杂度 $O(n^2+m)$。
P3514 [POI2011] LIZ-Lollipop
写过题解。
P3515 [POI2011] Lightning Conductor
决策单调性。使用分治解决。复杂度 $O(n\log n)$。
P3517 [POI2011] WYK-Plot
倍增典题，但是我不会。
一个显然的想法是二分以后，对于每个左端点再二分一下，里面做最小圆覆盖，找到这个左端点的最右的右端点。
但考虑一种所有只能分成长度为 $1$ 的段的情况，此时复杂度是 $O(n^2\log n)$。
然后我就不会了啊。发现倍增可以和二分很好的结合在一起。
考虑先倍增出一个区间长度 $2^k$，表示这个左端点的区间长度至少为 $2^k$，最多为 $2^{k+1}-1$。然后在这里面二分。
由于倍增的总长度是 $O(n)$ 的，而二分的总长度与倍增的总长度同阶。所以复杂度 $O(n\log^2 n)$。但是常数很大，怪不得这题开 10s。
P3518 [POI2011] SEJ-Strongbox
第一次做群相关的东西，虽然好像和群一点关系都没有。fxt 你说是不是。一开始没注意到 $a$ 可以等于 $b$ 写了个假的东西。
如果 $x$ 在群中，则 $\gcd(x,n)$ 和其倍数也在群中。我们考虑枚举这个 $d=\gcd(a_k,n)$，则只需要求出最小的 $d$ 满足条件即可，也就是 $d$ 不是 $d_i=\gcd(a_i,n)$ 的因数，不然就把 $a_i$ 表示出来了。
因数的话用推懒标记的推一下就好了。
复杂度 $O(k\log n+w(n)d(n))$。后面的复杂度是先把因数预处理出来，枚举不同的质因数下推。
P3519 [POI2011] ROZ-Difference
极差的最大值，等于任意两两字母区间两个字母出现次数差的最大值。容易发现这是不影响答案且包含答案的。
然后枚举两个字符，合并起来做最大子段，注意一个区间一定要同时出现两个字符才能记入答案。
复杂度 $O(26n)$。
P3520 [POI2011] SMI-Garbage
观察到一条欧拉回路，一定可以拆成若干个环。所以我们考虑求欧拉路径。
把要不改变的边再加一遍表示要经过两遍。有解的条件等同于存在欧拉回路。注意欧拉回路的写法不要写假。
复杂度 $O(n+m)$。
P3521 [POI2011] ROT-Tree Rotations
发现每个子树的左右儿子子树中是独立的，也就是左右儿子子树再怎么交换，也不会影响两个子树中的点的相对顺序。
统计逆序对用线段树合并。复杂度 $O(n\log n)$。
P3522 [POI2011] TEM-Temperature
感觉绿题还是有点思维难度的啊。
这种题一眼双指针。如果一个点可以加入，则满足 $r_i\ge \max\limits_{j=l}^r l_i$。双指针用单调队列维护即可。
复杂度 $O(n)$。
P3523 [POI2011] DYN-Dynamite
考虑二分然后贪心，贪心最少的覆盖点。
记录每个点子树内最远的要覆盖且还没有覆盖的和最近的选的关键节点。注意特判树根，如果存在没有覆盖的就要对答案 $+1$。
复杂度 $O(n\log n)$。
P3524 [POI2011] IMP-Party
绿题不会做。看了题解以后感觉很高妙啊！
如果 $(i,j)$ 之间没有边，那么至少有一个不在那个 $2n/3$ 团里，我们删掉这两个点。
删到不能删以后，由于我们必定有一个 $2n/3$ 的团，所以最多只会删 $n/3$ 次。最后没删的点随便输出 $n/3$ 个点即可。
还是要用好 $2$ 倍关系。虽然这种构造题感觉就是和出题人在对脑电波。
P3525 [POI2011] INS-Inspection
观察到有解的充要条件是最大的子树不超过 $n/2$。
容易发现这也是重心的判断条件，也就是不超过两个。所以可以暴力跑。
还有，如果其最大子树的大小恰好为 $n/2$ 且 $n$ 为偶数，则那个最长的路径要在它最大的子树中。
复杂度 $O(n)$。
P3526 [POI2011] OKR-Periodicity
设 $s$ 中两个相同的 border 的长度为 $x,y$。
- 如果 $2x\ge y$，则直接把 $x$ 复制一遍再重叠一部分使得长度为 $y$。
- 反之，我们希望中间填的串字典序最小：
- 全填 $0$，则存在一部分情况比如 $000$ 会使得 border 变多。
- 打表观察到全填 $0$ 不行的话填 $0^{y-2x-1}1$ 不会使 border 变多，且字典序一定小。
证明看题解吧。复杂度度的话，第一种情况复杂度 $O(n)$，第二种暴力判断 $T(n)=T(n/2)+O(n)=O(n)$。
P3527 [POI2011] MET-Meteors
整体二分模板。
P3528 [POI2011] PAT-Sticks
假设有三根小木棍 $x\le y\le z$，对于 $y$ ，我们需要找到最大的 $x$ 和最小的 $z$。
排个序以后，找到后面最小和次小的不同颜色的木棍，然后再从前面做一遍。最后找答案就好了。
复杂度 $O(n\log n+nk)$。
P3529 [POI2011] PRO-Programming Contest
简单费用流。不想写题解了。哈哈。