【笔记】POI 做题记录

honglan0301 · 2023-05-02 22:30:54 · 个人记录

未完待续（53/200）

Part 1. 远古简单题（17/17）

POI 1997~2003

P6701 [POI1997] Genotype

这种拆分啥的就很像区间 dp，不过数据范围误导人啊。。令 f(i,j,p) 表示目标串的 s_{[l,r]} 能否由 p 分裂得到，g(i,j) 表示 s_{[l,r]} 最少能由连续的几个 \texttt{S} 分裂得到，答案为 g(1,n)，时间复杂度 O(nm^3k)。-提交记录

P5939 [POI1998] 折线

旋转四十五度好像是常见套路，因为转完之后你可以把 \sqrt2\over 2 约掉。于是题意变成了一个点 i 只能向 x_j\geq x_i,y_j\geq y_i 的点连边，不妨先给 x 排序，那么只要求用多少条不降子序列能覆盖住所有点，这等价于最长下降子序列的长度。故结束了。-提交记录

P5921 [POI1999] 原始生物

【看题解】 感觉是很妙的题，第一次想的时候试图网络流但显然过不去。

感觉题解里上来就告诉你等价于欧拉路径有点抽象，我们不妨换个角度考虑。首先把每个限制抽象成一条有向边 (a_i,a_i+1)，那么整个序列就是一条路径，题意也就是可以随便加边，让你求一条最短的路径使得覆盖了所有给出的有向边。

然后注意到任两条路径都能通过在中间加一条边的方式合并起来。所以我们贪心地想，发现题意等价于求最小的路径条数使得能够走完所有边。 这与一笔画（欧拉路径）问题类似，事实上欧拉路径的结论确实可以拓展，即变成：一个 \sum |in_i-out_i|=2k 的弱联通有向图可以用 k 条有向路径覆盖所有边，并且至少用 k 条路径才能覆盖所有边（记得看到过 k=2 的题）。证明如下。

1. 必要性：考虑从空图开始加路径的过程，每加入一条路径只会对两端点的 |in_i-out_i| 产生至多 1 的影响，故必要性得证。

2. 充分性：考虑归纳，我们在图上任选选一个 in_i>out_i 的点 i 和一个 in_i<out_i 的点 j 连边，新图上归纳假设存在 k-1 条路径的覆盖方式，那么其中一条路径在这条边上断开后就形成了原图上 k 条路径的覆盖方式。而 k=1 时是欧拉路径问题，结论成立，故充分性得证。

故我们只需先把原图分成弱联通的子图，然后对于每个连通块分别求出答案，时间复杂度线性。-提交记录

P5929 [POI1999] 地图

容易发现要取中位数，又发现当有偶数个数时任意一个介于中间两数之间的数都是等价的，于是暴力 dp，把一段数分到一起的代价是 较大的一半数的和 减去 较小的一半数的和，前缀和处理，O(n^2m)。-提交记录

P5930 [POI1999] 降水

不是很懂，数据范围怎么这么小……按高度从小到大加点，并查集维护各连通块大小以及无法再存水的连通块大小和 即可 O(nm)。-提交记录

P5932 [POI1999] 多边形之战

发现是博弈板子题，当且仅当黑色三角形的至少两条边露在外面才能被取。于是记下它三边外面各有几个三角形，然后考虑打个表猜规律……哦忽然发现根本不需要，因为没有人会选择自杀，所以要么先手开局就赢了，要么一定会拖到全图只剩一个白色三角形为止，记录奇偶性即可。。 -提交记录

P8369 [POI2000] 条纹

多少有点板，暴力 n^2 预处理出每个棋盘长度的 sg 函数即可。感觉不如最近某次 CF div2E 或者 ABC G，那两个至少还要猜个结论（） -提交记录

P5546 [POI2000] 公共串

哦不会正解，但这个数据范围也太水了吧，注意到答案支持二分，于是字符串哈希套个二分，用 map 维护一下，O(nm\log^2 m) 可以通过…… -提交记录

学会 SAM 再来补正解（

P2444 [POI2000] 病毒

【看题解】 字符串的东西全都不会啊。题解感觉还挺神，不过确实是很有道理的，因为题目就是让你找一个永远匹配不上的字符串，会想到拿这样一个串在 ACAM 上匹配，发现这相当于在字典图上一个存在一个可达的环。只需注意"可达"的判定要考虑 fail 指针即可。 -提交记录

P8370 [POI2001] Goldmine

扫描线套路题。注意到单点加找矩形很不好弄，于是尝试对于每个金矿，维护其能够影响的矩形左下角位置，对这些位置区间加，然后即矩形加、询问全局最大值，可以使用扫描线维护。-提交记录

P8371 [POI2001] 绿色游戏

先读错题了，直接来了个一遍拓扑然后样例都过不去。看了一下才发现这个绿色点不一定是合法的，因为他的后继可能根本回不来……不过没关系，我们不妨类似调整的方法，先假设绿色点都是合法的，然后据此在反图上拓扑（点属于 A 还是 B 要分类讨论），此时再去判断哪些绿色点受后继的影响变得不合法了。

如果没有点受影响，那么显然它们的确就都是合法的。否则等价于我们把某一些钦定的合法点删掉了，这样的话不断重复此操作，最多会进行 n+m 次，剩下的就是最终的答案。 -提交记录

P5782 [POI2001] 和平委员会

我们发现每个党派居然只有两个人，还必选且只能选一个。。所以把它当成布尔变量，那么就是 2-SAT 板子，直接写就好了。 -提交记录

P8857 [POI2002] 滑雪者

之前正好写过。题意是问你用多少条路径能覆盖 DAG 上的所有边。

首先想到转化成最小路径覆盖，但是边转点复杂度会爆炸。不过我们可以考虑把每个工人的路径当成一条流，那么我们只需要求出每条弧上都有 \geq 1 的流量时的最小流，即上界为无穷大，下界为 1 的有源汇上下界最小流。上板子即可。不放提交记录了。

P5946 [POI2002]B-Smooth 数

只会复杂度其实不正确的暴力。所以以后再补。

P5944 [POI2002] 出圈游戏

容易发现还剩 q 个人的时候第 p 个报数的人出圈等价于 K\equiv p \pmod q，于是总共会列出 n 个同余式子，直接 \text{excrt} 求解即可，最小公倍数显然不会太大，开个 long long 就够。注意要特判求出来是 0 的情况（加上 mod 就行了）。

【看题解】（发现我不会 \text{excrt}，甚至不会 \text{exgcd}，于是现学了下）-提交记录

P5947 [POI2003] Trinomial

没推出来，只能用找规律做法，容易（根据定义）发现 f(i,j)=(f(i-1,j-2)+f(i-1,j-1)+f(i-1,j))\bmod 3，那么先打个表。【*图片没了】

然后眯起眼睛离远点看，很容易发现它递归分形的规律，于是就做完了。具体来说观察一下每次分形大概是分成九份，其中有两行全 1，三份全 0，四份相等，另外两份对应位置的和为 0，且每份内部也可以递归到顶上（更小的子问题）处理。-提交记录（找规律）

【看题解】 感觉是有点意思的，想法是二项式定理凑一个其中一项带 3 的然后全消掉，能发现：

那么即求：

于是再二项式定理一下：

使用 lucas 定理求解组合数即可。还是就觉得好神奇，只改变一下二项式定理的拆分方式居然有这么好的效果。

P8060 [POI2003] Sums

假设 A 中存在一个数 p，那么发现对于每一个模 p 的同余类，只需找到最小的一个数 q∈B，那么 \forall q'\equiv q\pmod p 都有 q'∈B。

这容易转化成同余最短路（其实就是板题），把 p 看作是基准数，于是只需找到到每个点的最短路径，因为非最短路径可以由最短路径加上若干个基准数得到。代码中使用了【转圈转移的完全背包】而非建图最短路 这一技巧，跑得还挺快（？-提交记录

Part 2.（36/183）

POI 2004

P5919 [POI2004] MAK

我觉得是挺好的题。从猜结论入手，先看什么时候“置换的 order 尽量大”。容易发现 order 其实就是置换环大小的 \text{lcm}，于是发现一个数含有多个质因子是劣的，故每个数只含有一种质因子，而又于是每种质因子只选一个数是不劣的（否则会出现整除关系，那个较小的数一点用都没有。）

哦好像还需要看字典序，根据样例发现把较小的置换环放前面，并且每个环内部都使用 i+1,i+2,i+3,\cdots,i+k,i 这种方式一定是最优的（可以根据字典序的定义归纳地证明），正巧这导致了每种质因子只选一个数不仅不劣，而且必是优的（\text{lcm} 不劣，字典序更优），于是考虑约 O({n^2\over \log n}) 的背包即可。

直接背包看起来存的值会巨大，然后我就没想到啥好方法，经过提醒发现既然转移的时候全是乘法，那么直接取对数就行了啊，感觉十分的合理（这也是题解里用鬼扯 long double 不会精度炸掉的原因（？）。

然后又发现被卡空间了。。没关系，感性理解特别大的质数一定没用，因为小的都取不完，去取大的不如多选几个小的乘起来，大概缩一下质数的范围就好了。-提交记录

P5911 [POI2004] PRZ

纯状压板子题，需要 O(3^n) 枚举子集，其它不解释。-提交记录

P1543 [POI2004] SZP

是基环树入门题，但我凭借极为优秀的调试能力调了好半天。

容易发现出度均为 1 的各点构成了一个内向基环树森林，我们常规的想法，试图把它变成树上问题（因为树上问题极好做，令 f(i,0/1) 表示该点选或不选能得到的最大值即可）。

然后发现这是容易的，我们只要找出一条在环上的边 (u,v) 并断开它，然后以 u 为根分别钦定选及不选 u，其中选 u 完全不影响树上 \text{dp}，不选 u 仅对选 v 的情况有影响（因为相当于已经有一个能监视 v 的人了），据此即可做到 O(n)。实现上可能要注意特判大小为 2 的环，不过我通过只存反边规避掉了特判。

我的写法常数有点巨大，不如题解中稍玄妙的贪心，但是断环 \text{dp} 更有普适性（？）-提交记录

P8384 [POI2004] SZN

不知道第多少次做几乎一样的题了，但还是调半天错。

我们肯定分别考虑两问的答案。先看第一问，考虑初始情况是每条边都是一条链，然后对于每个点我们一定要尽可能多地把周围一圈链两两合并起来。那么直接贪心，注意到这是能够保证正确性的，因为它不会使合并后的链变得不合法。于是第一问的答案是 n-1-\sum \lfloor {deg_i\over 2} \rfloor。

再看第二问，首先你发现可以二分转化成判定问题，然后再贪心地想，每个点会在子树中形成若干条链，然后向上传一条链，显然每个点向上传尽可能短的链一定是更优的。我们类似树上 \text{dp} 的方式，对于每个点 i 把它所有儿子传上来的链长插到 \text{multiset} 里，然后根据子节点个数 du_i 的奇偶性分类判断：

• 若 du_i\equiv 1 \pmod 2，那么为了保证链数最小一定是两两合并剩一条传上去，于是只需判断最后是否只剩一条链没合并然后往上传。

• 若 du_i\equiv 0 \pmod 2，那么若能两两合并完则把 0 传上去，否则合并完剩两条，其中长的那条就留在这了，短的那条传上去。

其余情况均不合法，容易判断。总时间复杂度 O(n\log^2 n)，可以通过本题。-提交记录

P8382 [POI2004] Gra

【看题解】 我们考虑一次“跳棋”的操作实质是把一段连续的棋拆成两段，然后令靠前的一段向前移动一格。那么有用的信息就只有每段棋子的长度和每两段棋子中间空格的数量。

然后我们寻找不变量，发现棋子的段数会变，但是空格的个数不变。于是转化成：

• 每一段连续的棋子由它们后面的空格所支配，每次操作即是把一个空格所支配的部分棋子转移到下一个空格上去。最终把棋子传给最后一个空格支配的人会输

也就是说除去最后两个空格外，先不能操作的人会输。即每次选一个 a\leq f_i 然后令 f_i\leftarrow f_i-a, \ f_{i-1}\leftarrow f_i+a。容易发现这是一个阶梯 \text{nim} 游戏，结论是奇数堆异或和是否不为 0 决定先手是否获胜。感觉有点神奇。记一个序列 f 的奇数堆异或和为 G(f)，下面给一个简单证明：

• 首先发现失败状态必有 G(f)=0，因为每一堆都是零。

• 然后发现 G(f)=0 的后继状态 f' 一定都有 G(f')\neq 0。原因是一次操作会且仅会改变一个奇数堆的状态，于是 G 必然会变。

• 然后发现 G(f)\neq 的后继状态 f' 中至少存在一个 G(f')=0。原因是我们考虑 G(f) 的最高位 j，发现至少有一个 f_i 满足 f_i\And 2^j=1，于是我们把它的低位改成 G(f)\bigoplus f_i 的低位，并把它的 第 j 位改成 0 即可使 G(f')=0。

• 于是易知 G(f)=0 都是必败状态，否则都是必胜状态。

注意要特判最后一个空格前面已经有棋子的情况。 -提交记录

P8383 [POI2004] Bra

注意到一个很好的性质是局部最大/小就是全局最大/小，于是我们只需要贪心地求出每个点的最小值和最大值，这可以通过分别从 \text{0,1} 开始 \text{bfs} 调整实现，感觉比较简单，不多解释。-提交记录

P5912 [POI2004] JAS

过于玄妙了，悟一悟再写。

P5913 [POI2004]KAG

想好久终于想出来一个时间复杂度正确的做法，但是还卡得挺紧的，不知道最优解 \text{20ms} 是怎么乱搞出来的？

首先我们观察 \text{C-Algae} 的性质，发现这两种操作是对称的，所以有：若 G 为 \text{C-Algae}，则 G 的补图也为 \text{C-Algae}（反之同理），原因是补图可以每次用与原图相反的合并方式造出来。于是我们会了一个暴力做法，即考虑倒推操作，交替进行以下两个拆分步骤，若最终能把图全都拆成单点则说明该图为 \text{C-Algae}：

1. 把原图分成多个不连通的子图（求连通块），然后分别检查各个子图。

2. 要么把反图分成多个不连通的子图（求反图连通块），然后分别检查各个子图的反图。

分析时间复杂度。单次操作 1,2 分别是 O(m) 和 O(n^2-m) 的，而操作 2 若能有效会消耗掉至少 O(n) 条边，故至多进行 O({m\over n}) 轮，时间复杂度 O(knm)。

接下来考虑优化拆分的步骤。发现我们应该不同情况差别对待地对操作 1,2 采取不一样的方式求连通块。操作 1 在稀疏图上可以直接枚举边，单次时间复杂度 O(n+m)。而操作 2 的图过于稠密，可以枚举点然后检查不存在的边（使用链表实现），因为至多会查到 m 条不存在的边，故单次时间复杂度同样为 O(n+m)。由于 m\leq n^2，故总时间复杂度 O(k(n+m)\times{\min(m,n^2)\over n})=O(k(n+m)\sqrt m)，常数不大，可以通过本题。-提交记录

POI 2005

P3417 [POI2005] BANK-Cash Dispenser

题面实在是太难看懂。。等价于问你这 n 个字符串有多少种长度为 4 的子序列，并且字符集只有数字，那么直接对于每个串预处理每个位置 i 之后的第一个数字 j 在哪里，记作 pos_{i,j}，然后暴力判断每个串是否合法，总时间复杂度 \sum t\times |\Sigma|+|\Sigma|^4n，可以通过本题。-提交记录

P3419 [POI2005]SAM-Toy Cars

核心是你发现顺序考虑没啥后效性，每个车有用的信息只有它下一次出现的时间。于是想到贪一下，每次如果需要换车就把出现最晚的车换到书架上，正确性是显然的（因为较早出现的车会较早地再被拿下来，而这个过程中出现晚的那个车没有做出任何贡献）。-提交记录

感觉这年的比较无聊？过几天再写

POI 2006

P3434 [POI2006] KRA-The Disks

评蓝是来搞笑的吧？？？单纯的模拟题，代码三行，建议评黄。-提交记录

P3435 [POI2006] OKR-Periods of Words

好像也是不配评蓝的题（），注意到前缀复制两遍能覆盖整个字符串等价于后缀是该串的 \text{border}，于是我们只需要求出每个位置最短的 \text{border}，也就是要找出 \text{kmp} 后最后一个非零的 nx[nx[...nx[i]]]，类似路径压缩地转移一下即可。-提交记录

P3439 [POI2006] MAG-Warehouse

好像现在是经典结论，在 \text{atcoder} 里见过好几次了？发现切比雪夫距离这个 \max 很难处理，于是我们尝试把 x,y 两维变得彼此独立（尝试变成曼哈顿距离）。

中考级别的知识，切比雪夫距离是正方形，而曼哈顿距离是斜着的正方形（），于是只需把坐标轴旋转 \pi \over 4，根据

容易把 {\sqrt 2}\over 2 消掉，变成 (x+y,-x+y)，之后单维的情况是比较显然的带权中位数，可以离散化之后扫一遍，总时间复杂度 O(n\log n)，可以通过本题。

然后写完发现有几个点过不了。。看题解才知道要注意这样算出来的坐标带回原坐标系下不一定是整点，所以要检查它附近的几个点。-提交记录

P3440 [POI2006] SZK-Schools

读题的时候还以为这个费用会有什么神奇的优化建图方法，然后一看数据范围发现想多了。。就是纯粹的二分图最大权完美匹配板子，建图费用流可以做到 O(n^3+n\times spfa())，如果拿势能重构边权并使用不加堆优的暴力 \text{dijkstra} 则能做到严格 O(n^3)，但是没必要。-提交记录

P3441 [POI2006] MET-Subway

【看题解】 好高妙的贪心（）

我认为核心是利用路径间可以相交，考虑把每条路径拆成两段去分层处理。令一个点 i 距叶子的最小距离为 ds_i，记满足 ds_j=i 的 j 个数为 cnt_i。这样分层的好处是 cnt_i 非严格单调递减，且每个 ds=i 的点都至少分别与一个 ds=i-1 的点相邻。

根据我们最初的想法，一条路径的 ds 长成 0,1,2\cdots p,p-1,\cdots 2,1,0 这个样子，且不同路径互不干扰。那么我们对 ds 贪心处理，易知 ds=i 的点至多取 \max(cnt_i,2l) 个（原因是每条路径上至多有两个 ds=i 的点），且一定能取到 \max(cnt_i,2l) 这个最大值（可以按 ds 从大到小归纳考虑）。

那么做完了，\text{bfs} 一遍，时间复杂度 O(n)。-提交记录

P3446 [POI2006]EST-Aesthetic Text

很简单的套路（）

首先明显是 \text{dp}，因为每行之和相邻两行会产生贡献，所以想到令 dp_{i,j} 表示目前最后一行选的是 (i...j) 这段单词时的最小代价。令 l(i,j) 表示 (i...j) 这段单词构成一行的长度，有显然的转移是：

接下来主要看一下 O(n^3) 变成 O(n^2) 这步。必然要拆括号，分成 \min\{dp_{j-1,k}+l(j,i)-l(k,j-1)\} 和 \min\{dp_{j-1,k}-l(j,i)+l(k,j-1)\} 这两部分考虑。发现前者对应的是 k 的一段后缀，后者对应一段前缀，故维护 dp_{j-1,k}-l(k,j-1) 的后缀最小值和 dp_{j-1,k}+l(k,j-1) 的前缀最小值即可通过本题。

转移的临界点 k 可以通过对每个 j 双指针预处理的方式均摊 O(1) 求，但我没想到（），而且数据范围有一点小，所以代码中使用了总时间复杂度 O(n^2\log n) 的二分。-提交记录

P3449 [POI2006] PAL-Palindromes

跟 \text{goodier djl} 一通瞎猜结论然后就用极简单的代码切了。。（？）不过感觉回文串的性质都听挺妙的，所以下面我们来写一下。*注意区分 周期 和 整周期。

1. 回文串的整周期还是回文串。

   证明：令回文串长度为 n，整周期长度为 k，有 s{[1\cdots k]}=s{[n-k+1\cdots n]}=s{[n\cdots n-k+1]}，故有该整周期也是回文串。

2. 若一个长为 n 的回文串串与另一个长为 m 的回文串拼起来能形成新的回文串，则这两个串有相同的长为 \gcd(n,m) 的整周期。

   证明：令两个串分别为 s,t，其中 |s|=n<|t|=m。与结论 1 类似地，有 s[1\cdots n]=t[m-n+1\cdots m]（原因：新串是回文串）=t[1\cdots n] （原因：t 是回文串）。一直推下去，即对于 ∀ k_1,k_2，都有s=t[k_1n+1\cdots (k_1+1)n]=t[m-(k_2+1)n+1\cdots m-k_2 n]。

   此时若 n|m 那么就结束了。否则下面来考虑 t[1\cdots (m\bmod n)] 这个串。

   我们首先断言它一定是回文串：原因是若 \lfloor {m\over n}\rfloor \equiv 0\pmod 2，则它是回文串 t 的中心部分；若 \lfloor {m\over n}\rfloor \equiv 1\pmod 2，则它是回文串 s+t 的中心部分。这都能推出它是回文串。

   然后又因为它是 s+t 的周期，所以只需证明它有长为 \gcd(n,m) 的整周期即可。那么注意到回文串 t[1\cdots(m\bmod n)] 与回文串 t[(m\bmod n)+1\cdots m] 拼成了新的回文串 t[1\cdots m]，故只需证明它也有长为 \gcd(n,m) 的整周期，而这是一个规模更小的子问题，由辗转相除易知其正确性。故得证。

然后发现两个串有相同的整周期等价于最小整周期相等，于是我们对每个串 \text{kmp} 一遍求出最小整周期，然后使用 \text{hash} 判断每种最小整周期对应的原串数量即可，时间复杂度线性或线性对数，取决于使用哈希表还是 \text{map}。-提交记录

P3437 [POI2006] TET-Tetris 3D

线段树套线段树板子，不多解释（）-提交记录

P3436 [POI2006] PRO-Professor Szu

脑抽了，被神奇输出格式卡了半天。

首先容易想到只需考虑能走到 n+1 的点，而又发现可以经过重复的边，于是如果中途有环就一定可以在环里一直绕使得有无数条路径，否则是 DAG 上求路径条数，按照拓扑序转移即可。

然后想有没有简洁的写法，发现可以先建反图缩点（这样就只用考虑从 n+1 出发的情况了），然后直接转移路径条数，只需注意若碰到了边数 \geq 1 的 scc 需要把答案设成 \text{INF}。

有个非常简单，非常典但是经常被人忘的性质是 \text{tarjan} 缩点的强连通分量编号就是逆拓扑序，所以完全没必要像题解那样写拓扑，可以直接按编号倒序转移。-提交记录

P3442 [POI2006]NAJ-The Invasion

还以为是啥计算几何高妙题，一看数据范围怎么就这。

容易发现暴力枚举三个点的复杂度是 O(n^3m)，但是明显没有必要对每个三角形都查一遍，所以我们尝试预处理使得能够 O(1) 查询答案。那么能想到从反面考虑，因为这样可以把一个三角形内的点权和转化成为三条直线外侧的点权和，复杂度变成 O(n^2m+n^3)。

再优化预处理，观察凸包的性质，记从点 i 到点 j 射线（向量）外侧的点权和为 f_{i,j}，发现一个资源对固定的 i 来说，会产生贡献的 j 区间在断环成链意义下是连续的，即只会对 f_{i,l\cdots r} 产生贡献，那么我们二分求出 l 之后用差分做离线区间加即可，只需判断点在向量的左/右侧，这可以通过面积法 O(1) 计算，故总时间复杂度 O(n^3+nm\log n)，可以通过。-提交记录

P3443 [POI2006]LIS-The Postman

【看题解】 拿这个题学了欧拉回路，感觉很妙啊。

发现题意等价于给你一些路径必须连续走，于是你想到对每条边记录个前驱和后继（如果有的话），这可以使用双向链表维护，然后有后继的边相当于出边锁死了，除此之外就是欧拉回路板子，跑一遍即可。说起来简单但因为是第一次写欧拉回路，调了半天。-提交记录

P3438 [POI2006] ZAB-Frogs

【看题解】 一眼平方斜优，但是只会 n^3 的？？？这为啥会想不出来啊。

我们考虑预处理出每个位置到最近坏点的距离，发现暴力枚举是 n^4 的，拆成 f_{i,j}=\min \{(i-x)^2+(j-y)^2\} 之后对每个 i 做斜率优化是 n^3 的，然后我就不会了…？？

事实上会发现固定 i 后有用的坏点个数是 O(n) 级别的，因为每一列的坏点只有里第 i 行最近的有用。于是我们先扫一遍预处理出 a_{j,i} 表示第 j 列的坏点到第 i 行的最小距离。于是化成 f_{i,j}=\min\{a_{k,i}+(j-k)^2\}。然后不管是考虑截距还是化成：

• 若 k_2>k_1 且 k_2 优于 k_1 则有 a_{i,k_1}^2+j^2-2jk_1+k_1^2>a_{i,k2}^2+j^2-2jk_2+k_2^2，即 \displaystyle\frac{(a_{i,k_2}^2+k_2^2-a_{i,k_1}^2-k_1^2)}{k_2-k_1}<2j

的这个形式都能够发现只需维护一个 (k,a_{i,k}^2+k^2) 的下凸包，横坐标与临界斜率都单增，于是单调队列做到线性。视 n,m 同级，总预处理复杂度即可做到 O(n^2)。

然后考虑怎么用预处理的东西算答案。想到二分 \text{bfs} 是容易的，不过因为 f 值域是 O(n^2) 的，于是用开桶替代排序，按照 f_{i,j} 从大到小并查集合并连通块做到更优的 O(n^2\alpha(n))，且感觉这种写法挺好（）-提交记录

P3444 [POI2006] ORK-Ploughing

好像想了个前一半都没有用的做法。。

首先还是发现行和列中至少有一个要删完，于是以下只讨论行被删完的情况，另一种是对称的。容易想到枚举没被删掉的列区间，然后只需判断这两点并取合法的最长区间即可：

1. 如果只剩了这些列，那么接下来能否删完所有行。

2. 能否在删这些列之前把其它列都删掉。

这样的好处是我们发现以上两点的操作过程其实是相同的，它们都要求尽可能地删掉更多行。所以先考虑更容易的前者，我们对每一对 (i,j) 使用二分或双指针预处理出 mn_{i,j} 表示固定左端点列为 j 后使得第一行不能被删掉的最小右端点列，然后找出 mn 的最小值并差分地计算即可，此处时间复杂度 O(n^2)。

再看后者，注意到 [l,r] 只能由 [l-1,r] 或 [l,r+1] 变过来，所以用区间 dp 的形式，最优情况与上面所求的情况是相同的。故为了方便，再多预处理一些东西，令 ll_{i,j},rr_{i,j} 表示只剩 [i,j] 列后无法删掉的最小行和最大行（易知 [ll,rr] 就是剩下的所有行），这容易根据前文所说的 mn_{i,j} 通过分别按从小到大和从大到小的顺序用并查集维护后继求得，时间复杂度也可以当成 O(n^2)。故之后只需考虑 \sum\limits_{i=ll_{l-1,r}}^{rr_{l-1,r}} t_{i,l-1} 是否 \leq k 即可判断从 [l-1,r] 来的转移，后者同理，故综上，总时间复杂度 O(n^2)，不过我不小心用了个带 \log 的写法。

当然后来看题解发现前面求的所有东西都是没有用的。。。感觉很妙啊，最后的区间 dp 可以直接在时间复杂度不变的同时把 ll,rr 搞出来，原因是 ll 单增，rr 单减，均摊分析，指针移动次数仍是 O(n^2)，总时间复杂度不变，且会好写不少，可惜没想到。我的 n^2\log n 恶心写法：-提交记录

P3447 [POI2006] KRY-Crystals

是好题。虽然数据范围过于小了，让我想了半天。。。

先想数位 \text{dp}，感觉不是很好做，因为你需要记录每个数的前 j 高位是否都是顶着 m_i 选的，状压下来直接就炸了。那么考虑异或与大小这两个性质之间的关系，发现更容易处理的是后者对前者的影响，因为当一个数的大小无限制时，其它数随便选都可以用它使异或和变成 0。也就是说我们并不需要知道具体是哪些数无限制，只要有一个数可以无限制地选，那么其它数就可以任选。

于是再按位考虑，异或在不同位之间互不影响，而大小当且仅当高位的 a_i 与 m_i 全相等时才受限制。于是我们想到枚举从高到低第一次出现 (a_i\And 2^j)<(m_i\And 2^j) 的位数 j，此时高于 j 的位是固定的，只需第 j 位的异或和为 0 且 \exists\ (a_i\And 2^j)<(m_i\And 2^j) 即可如上文所说地任选低位。

我们这样想，对于每个 a_i 容易求出第 j 位选 0,1 的方案数 b_i,c_i，我们求出 f(x)=\prod\limits_{i=1}^n{(c_ix+b_i)}，令 cnt 表示 \sum [m_i\And 2^j]，于是能使第 j 位异或和为 0 的方案数且存在 (a_i\And 2^j)<(m_i\And 2^j) 的合法方案数是 \sum [i\bmod 2=0][i\neq cnt][x^i]f(x)，因为其中有一个低位不受限的数要满足异或和为 0 （即相当于它被其它数固定了选法），所以这位的贡献是 \displaystyle\frac{\sum [i\bmod 2=0][i\neq cnt][x^i]f(x)}{2^j}。

以上的式子只是方便理解，事实上容易注意到这可以使用 \text{dp} 在 O(n) 的时间复杂度内完成。比如令 f_{i,0/1,0/1} 表示考虑了前 i 个数，异或和为 0 还是 1，当前有还是没有 (a_i\And 2^j)<(m_i\And 2^j) 的数。记 d_i 表示 m_i\bmod 2^j，有简单的转移：

• 若 m_i\And 2^j=0，则对 \forall j,k 有 f_{i,j,k}=f_{i-1,j,k}\times (d_i+1)。
• 若 m_i\And 2^j=1，则有：

易知这一位对 ans 的贡献即为 \displaystyle\frac{f_{n,0,1}}{2^j}，注意需要 \bigoplus\limits_{i=1}^n m_i 的高位均为 0 时才能计算此贡献，并且若 \bigoplus\limits_{i=1}^n m_i 本身就为 0 则也对 ans 有 1 的贡献。最后输出 ans-1，因为题目要求全 0 不合法。-提交记录

P3448 [POI2006] MIS-Teddies

一眼能看出是 \text{dp}，设 f_{i,j,k,p,0/1/2/3,0/1/2/3} 表示 A1,A2,B1,B2 分别选了 i,j,k,p 个，且最后两个分别是哪种（0,1,2,3 依次表示 A1,A2,B1,B2）的方案数。下面我们来考虑转移。

• 若 i+j+k+p\leq 2，则只要 (i,j,k,p,r,s) 合法就令 f_{i,j,k,p,r,s}=1。注意此处的合法仅指在 i,j,k,p 个 A1,A2,B1,B2 中能否找出两个分别是 r,s 的泰迪熊。

• 若 i+j+k+p>2，则首先判断同上判断 (i,j,k,p,r,s) 是否合法，然后若合法，则考虑令去掉 s 之后还剩下的 A1,A2,B1,B2 个数分别为 i',j',k',p'。之后只需枚举 0\leq q<4，若 q,r,s 能够放在连续的三个位置上，则 f_{i,j,k,p,r,s}\leftarrow f_{i,j,k,p,r,s}+f_{i',j',k',p',q,r}。

于是做完了，在实现上我们为了空间不炸可以滚动数组，于是空间优化到了大约 32n^3。为了时间不炸可以先预处理 hf_{q,r,s} 表示 q,r,s 能否连续地放，那么总时间复杂度 O(n^4)（带 64 倍常数，来自于枚举 r,s 的 16 倍和判断 (i,j,k,p,r,s) 是否合法与计算 i',j',k',p' 的 4 倍），算下来可以通过本题。

注意我这个写法需要特判 n=1。-提交记录

POI 2007

P3451 [POI2007] ATR-Tourist Attractions

不考虑卡空间的话是状压板子，考虑的话……我觉得没有必要，除了要增加点码长没任何意义，所以不说了。记得特判 k=0。-提交记录

P3452 [POI2007] BIU-Offices

转化一下，题意为给你一张图，求出它的反图中所有的连通块。这个技巧我在 [POI2004] KAG 里写过，不再重复。只不过注意一下当时实现上用了个 umap，这可以替换为暴力打标记使得做到严格线性。-提交记录

POI 2008

回来做几道。

P3466 [POI2008] KLO-Building blocks

巨大水题。相当于要对于每连续的 k 个数求出 \min \sum\limits_{i}^{i+k-1} |h_i-x| 和对应的 x。那么容易发现 x 一定是这 k 个数的中位数（或者 k 为偶数时是介于中间两数间的任意一个数），原因是记 h_i\sim h_{i+k-1} 中小于 x 的数的个数为 l_x，大于的个数为 r_x，若 l_x<r_x 则让 x 变为 x+1 一定更优，若 l_x>r_x 则让 x 变为 x-1 一定更优，若干次调整之后一定能得到 x 即为中位数。

所以随便拿点数据结构维护一下就行了，我直接写了个主席树，原因是支持的东西比较多（比如不固定 k 啥的也能做）。-提交记录

P3475 [POI2008] POD-Subdivision of Kingdom

大水题。百度一下发现 C_{26}^{13}≈10^7，直接暴力的话算贡献可能要多点常数，但我们可以考虑直接把每个点的连边压到一个 \text{int} 里，然后用快速的 \text{\_\_builtin\_popcount} 一边加点一边算答案，显然能过。-提交记录

P3465 [POI2008] CLO-Toll

还是大水题，，，什么情况。题意等价于让你找一个包含所有点的基环树森林，我直接每个连通块里找个环，然后对环上每个点往下搜就完事了。-提交记录

P3470 [POI2008] BBB-BBB

终于来了一道不单纯是板子的弱智题。

首先两种操作互不干扰，于是我们分别考虑，或者说考虑枚举第二种操作的次数去算所需的第一种操作数量（为什么不枚举第一个？因为第二种操作的对象是固定的，但第一种并不是。）

那么接下来只需考虑只使用第一种操作的情况。

先保证中途不出现负数，对前缀和数列来说这等价于 p+\min sum_i\geq 0，我们断言只需要进行 k_1=\max(0,(-p-\min sum_i+1)/2) 次操作，原因是显然贪心地从前往后将 -1 变为 1 是优的，而每次会使得 \min sum_i 增大 2。

再保证总和满足要求。我们发现经过上述操作后总前缀和变成了 sum_n+2\times k_1，于是显然需要进行 \dfrac{|p+sum_n+2\times k_1-q|}{2} 次操作。

再考虑枚举第二种操作后如何快速计算答案。哦等价于断环成链枚举位置，然后只需支持询问 \min\limits_{i}^{i+n-1} sum_i，随便单调队列或者线段树 \text{RMQ} 搞一下即可。时间复杂度线性或线性对数。-提交记录

P3471 [POI2008] POC-Trains

一道本应比较有趣的题（卡掉 \log 的话），但现在它被我用暴力数据结构切掉了。

容易发现全局总共会有 O(n+m) 种不同的字符串，所以我们暴力对它们字符串哈希并编号存下来，然后使用动态开点线段树直接维护每种串在时间序列上的出现次数即可，答案只需在每种被被更改时更新。

注意这里我有个小优化，不需要区间修改，只要每种串变多时把当前数量单点改上去即可，原因自行体会（显然的）。时间复杂度 O(m+n)\log m。-提交记录

P3472 [POI2008] MAF-Mafia

本来是断环树上 \text{dp} 板子题，但鉴于前面 \text{POI 2004} 里写过了，本处记一个稍有不同也稍微有趣点的想法。

对最大值和最小值分别考虑：

最大值：显然没有入度的点不可能被击中，故先将答案设为 ans=n-\sum [in_i=0]，之后我们考虑每个连通块会如何造成额外的影响。结论是当且仅当一个连通块是点数 >1 的环时会使 ans\leftarrow ans-1，原因如下：

• 若连通块是自环，显然它可以自己击中自己，没有额外影响。

• 若连通块是点数 >1 的环，则记第一个开枪的点是 i，显然 aim_{aim_i} 必然会活下来，并且可以通过让每个点开完枪就被击中（也就是在环上从 i 开始倒序开枪）使得只有 aim_{aim_i} 会活下来，所以额外影响是 ans\leftarrow ans-1。

• 否则连通块是环上挂了若干棵树，我们首先知道一棵树可以通过从根到叶依次开枪的方式使得所有非叶节点都被击中，于是我们只要找出环上挂了树的一个节点 p，让它作为上面的 aim_{aim_i} 先活下来，然后对每棵树分别处理即可让所有 [in_i\neq 0] 的点都被击中，即没有额外影响。

所以我们可以采用并查集直接找弱联通块，然后分别判断每个连通块的影响即可。

最小值：我们考虑贪心，转化成让活下来的人数最大，首先令能活的点都活下来（易知被 in_i=0 的点指向的 aim_i 必死，所以我们贪心地让 aim_i 在攻击前就被击中，这可以通过类似拓扑排序的方法实现），下面证明正确性（我们只需要证明一个点不开枪一定不劣于开枪）：

• 若不论 i 开不开枪 aim_i 都会寄那显然没影响。

• 若 i 不开枪会让 aim_i 活下来（比 i 开枪多活一个点了），此时只需证明对于 aim_i 之后的点，aim_i 活下来至多比 aim_i 寄掉多造成一个点被击中。

  因为 aim_i 活下来唯一的后果是 aim_{aim_i} 必死，所以我们考虑 aim_{aim_i} 的生死情况：

  • 若不论 aim_i 开不开枪 aim_{aim_i} 都会寄，那么 aim_i 开不开枪就对之后的点没有影响了，结论显然成立。

  • 若 aim_i 寄掉（不开枪）能让 aim_{aim_i} 活下来，此时我们发现若 aim_{aim_i} 不开枪一定不劣于开枪就结束了，而这是一个规模更小的子问题，从归纳的角度易知结论成立。

写得不是很清楚，不过大体没问题。注意有一些环会在本过程中未被考虑到，一个大小为 i 的环显然至少有 \lceil \frac{i}{2}\rceil 个点会被击中，加上就行了，可以沿用最大值中的并查集判断所属环。

所以做完了，时间复杂度 O(n)。另外我觉得我这里的代码实现非常得简洁优美，还挺不错（）-提交记录

P3474 [POI2008] KUP-Plot purchase

还算有趣的一道题。

我们首先观察发现这个限制是很松的，所以猜测除了特别极端的情况都能构造出来。

然后用调整的想法，先把单点就 >2\times k 的点全去掉，此时我们只考虑 sum\geq k 的矩形，如果同时有 sum\leq 2\times k 就结束了，否则我们把矩形分割成两部分，若有任意一部分满足 k\leq sum'\leq 2\times k 也就结束了，否则我们找出两部分中 sum' 较大的一部分递归处理即可。

其正确性来自于宽松的限制 \text{——} 一个 >2\times k 的数分成两部分，其较大的一部分不可能 <k，故在 sum 不断减小的过程中至少有一个时刻满足 k\leq sum\leq 2\times k，此时的矩形即为答案。

于是问题转化为了让你找一个单点 <2\times k，总权值 \geq k 的矩形。因为总权值没有上限，所以直接暴力单调栈找出所有的极大矩形判断即可。时间复杂度 O(n^2)。-提交记录

P3476 [POI2008] TRO-Triangles

【看题解】不会几何。

首先是一个我并不熟悉的结论，S_{\triangle ABC}=\dfrac{|\overrightarrow{AB}\times \overrightarrow{AC}|}{2}。

然后肯定拆贡献，枚举 A，只需计算 \sum\limits_{B=1}^{A-1} \sum\limits_{C=i+1}^{A-1}|\overrightarrow{AB}\times \overrightarrow {BC}|，保证其叉乘非负后分配成 \sum\limits_{B=1}^{A-1} \sum\limits_{C=i+1}^{A-1}|\overrightarrow{AB}\times \overrightarrow {BC}|=\sum\limits_{C}^{A-1}\overrightarrow {BC}\times \sum\limits_{B=1}^{C-1}\overrightarrow {AB}，后者可以前缀和计算优化掉一个 n。

那么只需考虑如何保证每个叉乘都非负。根据叉乘定义 \vec{A} 在 \vec{B} 的顺时针方向时才非负，于是一个我从来没有见过但应该很套路的方法是 先给每个点按照 x,y 分别为一二关键字从小到大排序，这样保证了 i 到编号 <i 的点的向量极角在某个 [k,k+\pi) 区间内，然后再对它们极角排序（为了精度方便使用叉乘）即可保证向量依次都成顺时针关系，叉乘非负。

莫名觉得很妙。不知道啥时候有空学学计算几何。-提交记录

P3468 [POI2008] ROB-Robinson

很快想到了一个 O(n^2) 做法，然后点开题解一看告诉我要 O(\frac{n^3}{\omega})？？？这也太不优美了吧（不过写完之后发现跟人家跑得差不多快，建议数据范围开到 n=5000。）

显然我们只需要求出船能在哪些位置之后就可以暴力 \text{bfs} 了，于是我们下面试图快速求出前者：

• 首先不妨以 最长列 nl 和 最长行 nh 的交点来定位船，因为这样能使四周都是凸的且向外的宽度递减、边界单调，方便处理。

• 然后从反面考虑，我们求出不合法的位置，因为不合法的位置可以叠加（而合法位置相当于需要做与运算，不好处理），这样方便拆分贡献。

• 然后考虑对行列分别处理（即分别考虑 因为太高而撞墙的 和 因为太宽而撞墙的，以下讨论前者）：我们枚举船所在的行 i，我们只需考虑每个点上方和下方的第一块墙所在行 j，它所对应的是船在原图上的第 nh-(i-j) 行。发现只需保证这行不撞该墙，其他行就一定撞不到这块墙（原因请自行考虑船的结构），故每块墙会造成一段位置不合法，差分即可。

于是分别对行列处理一遍，预处理时间复杂度 O(n^2)，\text{bfs} 时间复杂度 O(n^2)，总时间复杂度 O(n^2)，可以通过本题且写起来很简单（？

记得输出答案时要加上从 船在边界上边界 到 全部离开边界 的步数，这部分容易计算。-提交记录

POI 2009

POI 2010

POI 2011

POI 2012

POI 2013

POI 2014

POI 2015

POI 2016~2019