KpmCup#0解题报告

比赛状况：获得前三名的选手分别是oldmanren（400分，完美AK），以及离AK只有一步之遥的wyx528（390分）和huzecong（370分），祝贺各位屠场的神牛！（其实是我自己太弱出题太水了还好意思说...QaQ555），下面是解题报告：

                                     Problem A 小K的农场（farm）

本题共有4位选手满分。

解法一（期望50分）：

由于输出只有两种，那么random一下还是可以期望得到相当可观的分数的啦（第一题嘛，送分是必须的）

解法二（期望60~100分）:

事实上这是个明显的差分约束系统，利用最短路中的三角不等式dist[t]<=dist[s]+cost(s,t)，将所有不等式都转化为最短路中的连边，然后SPFA，如果存在负环，就是No，否则是No。（在本题中，裸的SPFA可以得到40分，SPFA+SLF优化可以得到90分，用栈维护的SPFA可以过全部测试点）

                                Problem B 小P的牧场（pasture）

这道题是这次比赛中AC人数最多的一道了，共有12位选手AC此题。

解法：动态规划

可以很容易地写出DP方程

cf1b9d16fdfaaf51346f73e78e5494eef11f7ade.jpg.png

30分解法：直接转移是O(n^{3)，用前缀和维护的话是O(n}2)

100分解法：斜率优化

对方程进行变形：

令

1e30e924b899a90118d8a96e1f950a7b0308f5fd.jpg.png

那么，对于两个决策j,k（j>k），如果K(j,k)<i，那么决策j优于k，然后就是斜率优化的经典做法，用一个队列维护决策的凸单调性即可。

以上做法每次状态转移的时间复杂度是O(1),总复杂度是O(n)，可以通过所有数据。

                                 Problem C 小M的作物（crop）

本题共有3位选手AC。

解法：网络流

此题将所有点划分成两个集合，要求获得的点权及附加权最大，可以很容易联想到最小割模型：

我们先把所有的收益加起来，然后建图（令划分到A的点为集合S，划分到B的点为集合T）:

对于一个点i，从源点到该点连一条容量为ai的边，再从该点连一条容量为bi的边到汇点，对于一种附加权方案j，添加两个辅助点vj,uj，从源点连一条容量为c1j的边到vj，然后从vj连边到该方案中的所有点，容量为正无穷，从uj连一条容量为c2j的边到汇点，然后对于方案中的所有点连边到uj，容量为正无穷。

然后跑一次最大流算法求出最小割，用总的收益减去最小割即为答案。

证明：假如一个点i划分到T，那么该点划分在S的收益以及于该点有关的附加权方案划分到S的收益将都被割去，对应的就是图中i与源点汇点的连边以及对于方案辅助点的连边。

                         Problem D Kpm的MC密码（password）

这道题总共有5位选手获得满分。

解法一：AC自动机+平衡树启发式合并

我们先把所有的字符串读入之后建立AC自动机，然后对于每个节点，以该节点的fail指针为父亲指针重新建立一棵树（暂且称之为fail树），那么我们发现，fail树中某个串的KPM串的结束节点都在该串结束节点的子树中，那么此题就成立求子树第k小值的经典问题，我们可以每个节点上标记在该节点结束的串的编号，每个节点上用一棵平衡树维护以该节点为根的fail子树里的所有编号，然后进行一次DFS遍历，每次遍历完一棵子树，就把它上的平衡树于其父亲节点的平衡树进行启发式合并（把小的树暴力合并到大的树里面），顺便在平衡树中求第k小值就可以了。

时间复杂度:O(n log^2 n)

期望得分：100分

解法二：AC自动机+DFS序列+主席树

关于AC自动机的处理与解法一相同，建立fail树之后对树进行一次DFS遍历，处理出树的DFS序列（括号序列），然后将问题转化为静态区间第k最值查询，那么就主席树即可。（你要使用时代的眼泪划分树貌似也没什么问题就是了）这种方法相当好写，也是标程的写法。

时间复杂度：O(n log n)

期望得分：100分

解法三：后缀数组+二分查找+RMQ+主席树

把所有的串串起来做后缀数组，那么某个串的KPM串的与该串相同的后缀就在sa数组的一个区间中（这个可以用RMQ+二分查找确定），然后转化为区间k最值的问题，主席树即可。

时间复杂度:O(n log^2 n)

期望得分:100分

题目&&解题报告&&数据&&标程下载：http://pan.baidu.com/s/1c0vK2PU