POI 2005 选做
Richard_Whr
·
·
个人记录
POI 2005
其实不是选做，而是挑贺得动的做，其他的贺不动了……
P3420 [POI2005] SKA-Piggy Banks
这题难度其实并不大，首先看到先后顺序就可以考虑连接有向边：
如果第 i 个存钱罐的钥匙在j中，就从 j 项 i 连一条有向边，表示要打开i必须先打开j
这样的话每个点都只有一条出边
然后可以发现，如果是一个链，那么需要砸开第一个，如果是一个环，那么需要砸开其中一个
也就是说，对于每一个连通块，都需要砸开一个，连通块可以用并查集或搜索。
P3423 [POI2005] BAN-Bank Notes
题意非常简单粗暴：多重背包记录方案
若是多重背包记录方案，最好用单调队列优化
单调队列优化：
将体积大小按照余数分类，设对 v 取模为 j
则对于 j+kv 这一条线上的，都是 f[j+k \times v] 这种形式的
但是前 s 各还不能直接用单调队列，因为体积越小，我新添加的 w 就可以越多，因此需要在单调队列中体现这一点
具体一点来说就是给第一个 - 0 \times w，给第二个 -
1 \times w，以此类推
因为选第一个可以比第二个多拿一个 w
记录转移，dfs即可
P3419 [POI2005] SAM-Toy Cars
看到数据范围 1e5 如此这样只能用 O(nlogn) 的复杂度了。
首先前几个当地板不满的时候，是肯定要拿的。
到后面，若已经有了，则无需再拿，若地板上没有，就要考虑挑一个了。
结合复杂度的分析，大概率时要使用一个优先队列了，因为没有其他优秀的算法可以在 log 的限制内选出 1 个最怎么怎么样的
现在我们考虑优先队列中存储什么，首先必要的一维是编号，但是肯定不作为关键字排序
贪心策略：挑日后最晚出现的那个拿出来，因为这样可以保证后效性尽可能地小
所以我们预处理出每一个位置对应的玩具，下一次出现的位置，并将其作为第一关键字放入优先队列当中。
若他之后不出现，则设为 +∞
- 若已经在地板上了，更新他下一次出现的位置
- 若不在地板上，取出优先队列队头，插入当前位置
对于第一个操作，由于不方便删除一个节点，所以我们索性将其一直留在地板上，而将地板的容量 ++，插入更新结点
P3431 [POI2005] AUT-The Bus
二维偏序板子题
左和下就是二维，按照其中一维排序，然后树状数组就可以了
注意，离散化需要先排序再判重。
[P3422 [POI2005] LOT-A Journey to Mars](https://www.luogu.com.cn/problem/P3422)
单调队列经典好题。不做过多阐述，细节过多，费脑费手，不想再写。
------------
[P3430 [POI2005] DWU-Double-row](https://www.luogu.com.cn/problem/P3430)
想出来半个正解，首先第一步转化成图论是绝对的。因为很明显有从属，矛盾和同步的 **点对** 关系，因此可以想到连边。
- 若同一排中两个数相等，意味着这两列必须有一列上下交换，连一条 $w=1$ 的边
- 若不同排两个数相等，意味着这两列必须同时换或者同时不换，连一条 $w=0 $ 的边
然后就染色，若换就染黑的，若不换就染白的，对于一个连通块，只要有一个确定，其他都确定，因此我们若当前方案不是最优解，那么黑白颠倒后一定是最优解
不过我还是不太知道为啥我是错的
若有大佬想帮一下可以看此帖：
[P3430存疑未答](https://www.luogu.com.cn/discuss/692498)
------------
[P3424 [POI2005] SUM-Fibonacci Sums](https://www.luogu.com.cn/problem/P3424)
没有啥意义的一道题，如果你看懂了第一篇题解，那还是有很大意义的，如果你只看懂了第二篇题解，恭喜你可以通过一道蓝题，如果你自己想出来了，那么我只有bx。但是很遗憾他没有任何实质价值和启发思考。
------------
[P3425 [POI2005] KOS-Dicing](https://www.luogu.com.cn/problem/P3425)
非常好的一道**二分+网络流判定**的题
最大最小，考虑二分。关键是 $check$ 函数咋写
看限制：
- 每场比赛只有一个赢家
- 每个人最多赢mid次
- 一场比赛中一个人只能赢一次
$S,T$ 和谁连边呢
由于每场比赛只有一个赢家，因此从起点向每场比赛连一条容量为 $1$ 的边
然后因为只有一个人能赢，所以每场比赛向对弈双方都连一条容量是 $1$ 的边，这样的话就意味着只有一个人有机会流过1的流量。
最后从每个人向汇点连一条容量是 $mid$ 的边，表示他最多能赢 $mid$ 次
最后判断是否合法呢？就是看总共的胜利场次是不是 $m$,也就是从源点发出的边是否都为满流。
dinic板子不要写挂了，注意看两倍空间
------------
[P3426 [POI2005] SZA-Template](https://www.luogu.com.cn/problem/P3426)
考虑dp（我不知道咋想到用dp的），因为我是贺的
$f[i]$ 表示印前 $i$ 个字母的最小单位
显而易见的，有 $f[i]=i$，自己必能覆盖自己
那么可不可以更短呢。
如果这个字符串中出现了重复的，那么只需要其中一部分即可。重复的且没有反向，考虑kmp
求出ne数组
首先覆盖 $i$ 的必要条件就是覆盖 $i$ 的子串，但是覆盖 $i$ 的子串不是覆盖 $i$ 的充分条件.
那么什么时候成为充要条件呢。可以想象，如果最长前后缀中间有重叠，那么一定可以通过只覆盖前缀的单位来覆盖整个串。
如果没有重叠，就需要用覆盖前缀的最短的相同单位来覆盖中间一部分，可以多但不可以少，也就是说，现在我们把后缀用可以覆盖与其相等的前缀的单位涂好了，需要在用这个单位图剩下的
换而言之，就是要找到一个 $j$ 使得 $f[j]==f[ne[i]]
这样f[i]就可以从 f[ne[i]] 转移了
复杂度：O(n+n)
剩下的题做不动了。