POI2008合集

12.02～12.04

*12.02 是星期六，12.03 有模拟赛。

P2546 [POI2008] SZK - Mirror trap

首先答案是 n/2。

然后构造不会啊。看题解都是基于矩形的周长暴力求出来，但是为什么这样的复杂度是可以接受的？

P3465 [POI2008] CLO-Toll

如果每个连通块里有一个环那么就一定可以。

然后 dfs 树跑出来找一个返租边就行了。

P3466 [POI2008] KLO-Building blocks

发现最优的点是中位数。算贡献就平衡树一类的就可以了。

如果是现在的我会写权值线段树。

P3467 [POI2008] PLA-Postering

如果两个点可以用一张海报同时解决就称产生了 $-1$ 的贡献。

发现如果两个点大小相等，且之间的高度都大于这两个点就会产生贡献。

ST 表太蠢了不是吗。所以笛卡尔树搞一搞。复杂度 $O(n)$。

P3470 [POI2008] BBB-BBB

观察到先进行 $2$ 操作，再进行 $1$ 操作和两个交替进行是等价的。

然后把序列复制一遍，相当于滑动窗口。找到至少需要几个最前面的 $-1$ 改为 $1$，然后再做 $p+S_n=q$ 限制调整一下。

复杂度 $O(n)$。

P3471 [POI2008] POC-Trains

数据结构学傻了。算是小清新数据结构题？

判断相同考虑哈希。

我们对每个哈希值维护一个集合，集合按加入时间排序（所以为什么不叫序列呢），集合中的每个点带权表示当这个点加入时刻下的集合大小。我们删除一个点时查询这个点在原来所在集合中的后缀最大值。也就是我们要在线维护：

• 加入一个数。
• 查询一个数在集合中的后缀最大值。

显然可以用平衡树搞一搞，那这样不是太平凡了吗？

考虑带权并查集，每次把一个点加入集合时把他作为这个集合的根。查询时做路径压缩的时候，把到根的权值的最大值和自己本身取最大。这样每个点的后缀最大值信息就维护好了。

如果自己写哈希表的话可以做到 $O(nl+m)$。但我比较懒用 unordered_map。

P3472 [POI2008] MAF-Mafia

先以 $(i,a_i)$ 建一颗内向基环树。

考虑先计算最多的情况。

观察到如果一棵基环树只有环，那么最多能存活 $1$ 个，否则除了入度为 $0$ 的点一定能杀光。还要特判只有一个自环的情况，这种情况这个点也可以被自己杀死。

然后计算最少的情况。

考虑最优策略有：如果一个人一定被杀死，那么就不要让他在杀别人之前被杀。

先把树的部分处理出来。这样环上就成了一些一定要被杀死的点和不被确定的点。如果环上存在一定被杀死的点，则被分为许多不被确定的链，一条长度为 $x$ 的链最少被杀死的人数是 $\lfloor\dfrac{x}{2}\rfloor$；如果环上都是不被确定的点，令环的长度为 $x$，则最少被杀死的人数是 $\lceil \dfrac{x}{2} \rceil$。

复杂度 $O(n)$。

P3473 [POI2008] UCI-The Great Escape

还是一些细节没想好啊。

观察到每次相当于切割一次矩阵，我们令 $f_{i,j,k,l,0/1/2/3}$ 表示矩阵的左下角的为 $(i,j)$，右上角为 $(k,l)$，接下来要往 上/右/下/左 走。

先不考虑有障碍的情况。

感觉从 $(1,1)$ 开始不好赋初值啊，于是我们考虑从 $(sx,sy)$ 开始倒着走，也就是每次左转。比如我们以往上走为例子：

$f_{i,j,k,l,0}\gets f_{r,j+1,k,l,1}$。

考虑用已经递推出来的来化简这个东西：

$f_{i,j,k,l,0}\gets f_{i+1,j,k,l,0}+f_{i,j+1,k,l,1}$。

可以发现新加入的一条是列为 $j$，行 $[i,k]$ 的一列值，只需要判断这一段上没有障碍就可以转移。

同样的可以扩展到剩下 $3$ 种情况。

最初状态 $f_{sx,sy,sx,sy,i}=1$。

然后考虑转移方向，观察到每次让矩形的半周长增加 $1$。所以我们先枚举矩形半周长即可。

这样就可以 $O(n^4)$ 递推了。空间需要滚动数组优化，复杂度为 $O(n^3)$，有 $8$ 倍的常数。

P3474 [POI2008] KUP-Plot purchase

这题的关键在于用到 $[k,2k]$ 和 $<k$ 的关系。

显然如果一个点：

• $>2k$，那么这个点一定不能被选。
• $k\le a_{i,j}\le 2k$，这个点就可以作为答案。
• $<k$。

把上面两种判掉，那么转化为我们要选一个只有 $<k$ 的点组成的矩阵，满足矩阵元素之和在 $[k,2k]$ 之间。

观察到如果一个矩阵仅有 $<k$ 的组成，如果这个矩阵的和 $\ge k$，那么一定有解。

• 如果矩阵的和 $\le 2k$，它就是答案。
• 否则如果矩阵的第一行 $<k$，那么删掉这一行。
• 如果矩阵的第一行 $\ge k$，那么只保留这一行，并不断删数删到这一行的和 $\le 2k$ 为止。

因为我们选出的这个矩阵中的所有元素都 $<k$，所以一定可以删到 $[k,2k]$ 之间。

要找一个满足条件且 $\ge k$ 的矩阵，等价于找一个只包含 $<k$ 元素的最大子矩阵。悬线法即可。复杂度 $O(n^2)$。

P3475 [POI2008] POD-Subdivision of Kingdom

观察到状态很少，考虑直接搜。

关于 $O(1)$ 计算状态，考虑在搜的时候计算出一个数从一个集合移到另外一个集合的变化量，状压以后计算状态里 $1$ 的个数。

直接 $2^{26}$ 预处理计算是不现实的，可以计算前 $13$ 位和后 $13$ 位的 $1$ 的个数的和。

P3476 [POI2008] TRO-Triangles

计算几何入门题。

如果直接枚举三角形的一个点 $A$，发现叉积的绝对值不好去。如果要去的话要 360 度的极角排序后双指针。考虑更高妙的枚举方式。

观察到我们只需要先将所有点按 $A$ 排个序，每次只枚举这个点后面的点那么就只用 180 度的极角排序，按叉积排序就好了。排完序以后做个后缀向量和叉积即可。

复杂度 $O(n^2\log n)$，瓶颈在排序。

P3478 [POI2008] STA-Station

简单树形换根。