A. 字符

题中保证$p_i<=1e5$，还可以很显然地发现当总长度大于$p_{max}+c$，一定不会更优。

于是枚举长度的大小。

将每一个限制对长度取模。

显然如果相邻两个字符所在的区间存在交集，就表示状态非法。

于是得到$O(m*p_{max})$的暴力。

发现在取模的过程中如果已经不合法，可以直接跳出。

在随机数据下这个算法已经很优秀，

但如果特殊构造也是能卡掉的：比如给出10000个字符0的位置，大部分算法无法剪枝。

考虑优化。

我们要求的其实就是每个字符在模意义下的最小值和最大值。

于是直接预处理出每个点左右最近的一个有字符的点。

在统计过程中不断给下标+len，表示当前考虑的一段区间，同一段区间内的最值是显然的。

根据调和级数，这样做的复杂度为$O(p_{max}*logp_{max})$

考试时这个题刚开始打的暴力，过了样例直接交了。

因为有一个比较自信很难卡的剪枝，通过显示$submit$的时间，我猜测应该是A掉了。

但心里还是很不安，打了一个st表，复杂度对了，调了一个小时。

考完才发现暴力没删$freopen$，所以打了正解反而是对的？

B. 蛋糕

直接区间dp，

考虑一下哪些状态是合法的就完了。

C. 游戏

考虑一条性质：

由岐的路径一定为被一个莉露露带着跑，抛出，然后下一个没有动过的莉露露过来带着跑并抛出。

第n个莉露露一定不会动。

于是问题转化为最短路问题。

暴力建边有$X^3$个，算上$dijkstra$的复杂度已经$O(X^3log)$，过不去。

所以考虑优化建边。

对于$a=0$，线段树优化建边是可行的。

但是在$a!=0$的情况下，每个点向其它点的边权值为一个等差数列，线段树就萎了。

考虑网络流中常用的建图技巧：

每次移动的增量a是固定的，

所以将每个点拆为三个点，分别表示在这个点，在这个点行方向被抛出中，在这个点列方向被抛出中。

以下为具体建边：

1.点1向点2，3建边，权值为让最近莉露露过来。

2.点2，3向点1建边，权值为退出状态的b。

3.点1向周围四个点建边，权值为c。

4.点2，3分别向行、列建边，权值为a。

精髓主要在于拆点的操作和第四种建边，成功地把一些边合在了一起，保证了边的数量为$X^2$级别。