风起水起难靠岸

1.Majority

好题啊。

首先发现操作比较复杂，但是有递归性，我们可以只研究最后一次操作。

然后令 $f_i$ 表示长度为 $i$ 的合法串的方案数，转移的时候枚举两段和中间，前缀和优化一下。

然后发现会算重，因为 $10101$ 这样的串，最后一步可以是 $11101$ 或者 $10111$ 变化而来。

我们想要去重，就可以让操作唯一。

操作唯一可以在从左往右扫的时候，能合并就合并。

这样的话，$dp$ 其实不太好设计状态，在一个合并过程中的串是比较复杂的。

总之我们想多记录一维，因为还是考虑最后一次合并，最后一次合并形如 $111000000111$ 合并成全是 $1$。

因此考虑记录一维，代表前缀 $1$ 的个数，并且能遵循能合并就合并。

具体来说 $dp_{i,j}$ 表示长度为 $i$，合并后前缀 $1$ 的个数是 $j$ 的方案数。

然后考虑转移。

$dp_{i,j}$ 从 $i-1$ 或者 $j-1$ 转移过来都不是特别好办。

然后手玩一下，发现可以从 $dp_{j,j}$ 和后面一段 $0$，再一段串拼接而来。

$dp_{i,j}=\sum dp_{j,j}\times dp_{k,x}$

这里满足 $k+x\le i-2j-1$，因为得满足不能合并。

这个限制使得我们可以用一个前缀和轻易维护。

时间复杂度：$O(n^2)$。

link

2.Bracket Cost

先考虑固定 $l,r$ 的时候，贡献是什么样子的。

首先令这个区间内左括号的个数为 $a$，右括号的个数为 $b$。

首先需要 $\max(a,b)-\min(a,b)$ 满足括号个数配对好。

其次新加入的时候，肯定能配对好，原来的形态里如果有 $c$ 对配对好的，那么最后还有 $\min(a,b)-c$ 对是肯定需要调整的。

下界因此就是 $\max(a,b)-c$。

然后上界显然也是，因为每一次操作一定能使得匹配数 $+1$。

考虑这个怎么计算。

先看 $c$，如果在 $[l,r]$ 中一对括号匹配，那么在原串中也一定匹配，反之亦然。

所以对于 $x,y$ 两个位置匹配，贡献就是 $x\times (n-y+1)$。

然后 $\max(a,b)$ 考虑拆开。

先有 $\max(a,b)=\min(a,b)+|a-b|$，因为 $\max(a,b)+\min(a,b)$ 是好求的，凑这个形式。

因此 $2\max(a,b)=\max(a,b)+\min(a,b)+|a-b|=a+b+|a-b|$。

这些都是好算的，$|a-b|=|s_r-s_{l-1}|$，其中 $s$ 是前缀和。

绝对值就先排序再处理就可以了。

时间复杂度：$O(n\log n)$。

link

3.Count Sequences

考虑原数组的差分数组，对 $3$ 取模之后每个数只能为 $1/2$。

考虑枚举 $1$ 的个数 $i$，$2$ 的个数显然是 $n-1-i$。

枚举 $a_1$ 对 $3$ 取模的余数，然后考虑任意一个形态，从某个位置往后以 $3$ 为单位的平移依然是合法的。

所以剩下计算一下 $3$ 的个数，直接插板即可。

时间复杂度：$O(n)$。

link

4.No Smoking!

扫描线。

维护一个 $\text {set}$ 来存当前的线段，这些线段一定是能按照函数值排序的，而且不会发生错乱，否则一定有交。

因此在每一条线段插入的时候，考虑和 $\text{set}$ 中上一个和下一个判一判是否相交即可。

删除的时候也要判！！！

判 $(x,pre_x)$ $(x,nxt_x)$ $(pre_x,nxt_x)$。

对于 $x1=x2$ 的线段，有一个巧妙的处理方法是所有线段随机偏转一个小角度，规避特判。

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

5.Two Professors

不考虑 $1$ 和 $2$ 的情况，可以有一个贪心做法。

按左端点排序，拿一个 $\text{priority queue}$ 来维护当前的所有进程的右端点。

这样某条线段插入的时候，所有能放的进程在后面都是等价的，随便放一个，更新 $\text{priority queue}$ 即可。

这个贪心的正确性显然。

设这样做出来的答案为 $x$。

那么真实答案只能是 $x$ 或者 $x+1$。

取决于是否存在一种方案，使得答案是 $x$，$1$ 和 $2$ 不放在一起。

假设 $1$ 的左端点在 $2$，前面，否则可以 $\text {swap}$。

注意到，如果一个进程放进去的时候，如果有多个选择，其中一个选择是 $1$ 的话，那么就可以将这些行，后面的部分全部调换。

所以这样就是能做到 $x$，否则如果放入 $1$ 那一行的所有决策唯一，而且 $2$ 也在，就只能 $x+1$。

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

6.Construct a Matrix

$0$ 和 $1/2$ 的询问是独立的。

$1/2$ 的询问其实是限制了区间内 $2$ 个数的奇偶性。

把 $1$ 和 $2$ 的询问区间覆盖之后，其他全部填 $0$ 即可。

剩下的可以形如一些方程，每个方程用前缀和可以改成 $4$ 个未知数。

也就是 $8000$ 个元，$2000$ 个方程的异或方程组，$\text {bitset}$ 优化即可。

最后填回去，注意到如果有一个地方，应该填 $2$，但是又和前面 $0$ 的冲突了，填 $0$ 没有影响，后面的前缀和关于这个的更改是抵消掉的。

时间复杂度：$O(\frac{n^3} w)$

7.Telegraph

首先如果确定了所有选的点的 $dep$，那么和 $val$ 应该是大的对大的，小的对小的。

所以考虑从小到大枚举 $dep$，然后选，这一步其实挺自然的，但是我没想到，一直在树型结构上想。

考虑 $dp(dep,i,j,k)$ 表示考虑当前层是 $dep$，已经匹配了 $val$ 前 $i$ 大，当前层有 $j$ 个，上一层有 $k$ 个。

其中 $j$ 都是没被选，$k$ 都是已经生成过左儿子，没生成右儿子，没被选的。

保留 $j,k$ 的意义在于可以生成下一层的点。

$dp(dep,i,j,k)+dep\times a_{i+1}\rightarrow dp(dep,i+1,j-1,k)\\ dp(dep,i,j,k)\rightarrow dp(dep+1,i,j+k,j)$

考虑换一种计算贡献的方式，每一次换层的时候，都把加上还没选的 $val$ 总和，这样显然正确。

因此就有

$dp(dep,i,j,k)\rightarrow dp(dep,i+1,j-1,k)\\ dp(dep,i,j,k)+suf_{i+1}\rightarrow dp(dep+1,i,j+k,j)$

转移和 $dep$ 无关，可以忽略掉 $dep$ 吗，答案是肯定的。

因为取答案的时候和 $dep$ 无关，转移的时候也不会出现环。

固定住 $i$ ，按 $i$ 分层的时候第一种转移是换层的，第二层是 $j$ 不递减的转移。

因此直接写成 $dp(i,j,k)$ 这个取到最优的时候，$dep$ 也是唯一固定的，而且不需要考虑 $dep$ 相关的事情。

滚动掉 $i$，把空间做到 $n^2$ 即可通过。

时间复杂度：$O(n^2)$。

8.Substring Restrictions

每次操作发现就是把 $[x,x+len-1]$ 和 $[y,y+len-1]$ 对应的位置并查集合并起来。

考虑优化这个过程。

下一步感觉挺套路的，但我不是很会，入门的时候倍增就没学好。

并查集这种可以结合的，重复贡献不影响结果的，可以用类似 $ST$ 表的那种办法倍增拆成两个区间，把这一层分成 $2$ 组合并起来。

然后就是跑 $\log n$ 层，每一层合并完之后还传到下面去，对于每一个 $i$，如果 $find(i)=x,x\ne i$，那么就把下一层中 $i,x$ 合并 $i+len/2,x+len/2$ 合并。

可以证明每一层合并到下面的边数都是 $O(n)$ 的。

时间复杂度：$O(n\log n \alpha(n))$

9.Max Intersection Partition

首先考虑 $n^2$ 做法。

设计一个 $dp(i,j)$ 表示前 $i$ 个线段，已经分成了 $j$ 段的最大值。

然后因为这样连续选一段区间需要排序，所以想怎么排序。

发现怎么排序都不可以处理包含的关系，所以考虑特殊处理包含关系。

如果 $a$ 包含 $b$，那么 $a$ 要么自成一段，要么在别的段都是添乱的，可以直接放到 $b$ 这一段来。

这样我们就可以在 $dp$ 的时候忽略这样的 $a$。

然后 $dp$ 就很好做了，所有左端点递增，右端点递增。

$dp$ 的过程可能需要贡献和 $0$ 取 $\max$，但是如果这种情况，说明有的段是 $0$，那么更优的一种方案是取最大的 $k-1$ 条自成一段，其余放一起，这种特判。

所以不需要考虑取 $\max$，总是 $r-l$ 即可。

接着考虑如果分成了若干段，那么贡献是形如 $r_1-l_{p_1}+r_{p_1+1}-l_{p_2}+...+r_{p_n}-l_m$。

进而发现每个断点的贡献都是独立的，和包含其他的段一起选 $k-1$ 个最大的即可。

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

10.MST and Rectangles

看到 MST 题的基本做法就是分析一下问题，然后套用三个最小生成树算法。

Boruvka 的拓展性是最强的，本题也就是用 Boruvka。

首先一条边 $(x,y)$ 的代价是 $A_{x,y}+A_{y,x}$，我们可以另外维护一个矩形 $C$，满足 $C_{x,y}=A_{x,y}+A_{y,x}$。

这样 $(x,y)$ 的代价直接就是 $C_{x,y}$。

对于一个操作，对于若干的 $A_{x,y}$ 同时加上 $w$，其实可以看作 $C_{x,y}$ 和 $C_{y,x}$ 同时加上 $w$，也就是两次矩形加。

Boruvka 的流程是，每一轮把所有连通块向外的最短边找出来连接，每一轮连通块个数至少除以 $2$，共 $O(\log n)$ 轮。

找最短边考虑每一轮离线+扫描线，从左往右扫的时候，遇到一些操作，先把操作用来更新线段树上维护的信息。

扫描线的下标是当前考虑向外连的节点，线段树的下标是其他的点。

对于每一个点，需要考虑向外连接的最小边，也就是线段树上的最小值，由于可能会在同一个连通块内，所以维护两个颜色不同的即可。

对于一段 $[l,r]$ 都没有操作，那么 $x\in [l,r]$ 的最小边应该和 $x-1$ 相同。

时间复杂度：$O(n\log^2 n)$

空间复杂度：$O(n)$

11.Monster

首先发现，如果想要花费 $b_i$ 的代价，你可以覆盖尽量多，具体来说就是直到左边和右边第一个代价大于 $b_i$ 的位置。

这样构建出一个树形结构，并且恰好是笛卡尔树。

改写一下限制，形如：

第 $i$ 号节点，在笛卡尔树上到根的路径中要选至少 $a_i$ 次，在 $i$ 选一次的代价是 $b_i$。

笛卡尔树上面的 $b_i$ 要比下面的大。

因此我们可以想一些贪心。

在 $u$ 节点，先选 $a_u$ 次 $b_u$，然后这么做可以让儿子里的少选，然后还可以多选几次 $b_u$，直到再选 $b_u$ 是亏的。

维护若干个二元组形如 $(x,y)$ 表示 代价为 $x$ 的要选 $y$ 次，考虑在当前多选一次 $b_u$，花费是 $b_u$，正向的贡献是所有 $y>0$ 的 $x$ 求和。

把所有的 $y$ 按照顺序维护，一直选 $b_u$，直到某个 $y\le0$ 之后选 $b_u$ 是不划算的。

考虑复杂度，如果用一个数据结构维护 $(x,y)$，再启发式合并，就是 $2 \log$。

每个 $u$ 会贡献一对新的 $(x,y)$，且这一对 $(x,y)$ 最多会被删除一次。

然后这么做会发现可能对于一个 $v$ 已经被父亲 $u$ 覆盖，对于一个 $x$ 作为 $u$ 的父亲，替换一次 $u$ 之后会把 $v$ 的贡献再算一次。

这种情况就可以把 $u,v$ 维护出一种树形结构，先忽略 $v$，$u$ 的删完再把 $v$ 的贡献还原进去。

这个树形结构可以不显式建出来，魔改一下二元组的意义即可。

12.清风

考虑倒着做，最终答案的形态可以分成若干段 $n=m$ 的。

$n=m$ 的容易做，令 $f_n$ 表示答案，转移枚举最后一次放的是谁。

$f_n=(n+1)\sum\limits_{i=1}^n f_{i-1}f_{n-i}\binom {n-1} {i-1}$

这个可以分治ntt算。

后面是一个背包，考虑对白色格子的个数背包而不是黑色格子，这样填一个白色前面可以带若干个黑色，多项式 $\text {exp}$ 即可。

时间复杂度：$O(n\log^2n)$

然而原题的模数是 $10^9+7$，所以得考虑组合意义做法。

考虑添加一个 $n+1$，然后连成一个环，每次视作从一个位置出发，顺时针或者逆时针出发，到第一个白色格子染黑。

这个和原问题其实是等价的，因为如果一个选到了 $n+1$ 的决策一定是黑色的，那么被当做不合法的方案。

这样一来，每个格子被染黑的 “概率” 其实是相等的。

因此答案就是 $\frac {n+1-m}{n+1}(2n+2)^m$。

13.半夜

$n^3$ 的做法是显然的，把 $s$ 变成 $s+s$，从每一个位置出发做一次 $n^2$ 的 $\text{dp}$ 求 $\text{lcs}$ 即可。

进一步数形结合发现这个 $\text {dp}$ 的轮廓线是具有单调性的。

分治做决策单调性即可。

感觉很智慧，也可能比较套路，值得学习。

14.鸣蝉

多个线段并这种事情很逆天，所以基本上不太有简单做法。

考虑暴力，用 $\text {bitset}$ 来维护不同的颜色。

然后分块，对于散块暴力，大块维护，大块用 $\text{ST}$ 表存 $\text {bitset}$ 即可。

设 $B$ 为块长。

时间复杂度：$O((\sum k)B+\dfrac {\frac {n^2} B \log \frac n B} \omega+\dfrac {nq} w)$

空间复杂度：$O(n+\dfrac {\frac {n^2} B \log \frac n B} \omega)$

取 $\frac n B=32$ 左右就能通过。

进一步有一个卡常是预处理只出现了一次的颜色，这个可以前缀和维护，$\text {bitset}$ 的大小就会变成原来的 $\frac 1 2$。

15.隔膜

满分做法和倒着 $\text {dp}$ 的做法没有任何关系，不写。

考虑正向贪心，每个人应该有怎么样的决策。

每个数首先都大于等于 $0$，所以变成自己的那一面一定更好。

如果一个人只有至多一个不是自己的面，翻它。

否则陷入一个选择，$i$ 和 $i+1$ 翻谁。

先说出结论，如果 $i$ 是一个后缀 $\text {min}$，那么翻 $i+1$，否则翻 $i$。

证明感性理解一下就是如果翻了 $i+1$，后面会换来一个后缀 $\text {min}$，和 $i$ 比较大小，多手玩一下也可以发现。

然后就可以用 $\text {set}$ 来维护后缀 $\text {min}$，以及选择 $i+1$ 的位置，这样一来发现所有 $a_i$ 的正反面都是很有规律的，只有被选择来选 $i+1$ 的后缀 $\text{min}$ 位置，是和初始不同的。

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

16.Dungeon Crawler

17.Where Am I?

18.CowMooing

19.Color a Tree

20.Wild West

21.Peaks

22.Sorting a Matrix

23.Random Walk to Millionaire

24.Constrained Sums

25.Chocolate

$\text {Exchange Argument}$ 简单题，直接按照 $val$ 排序就是对的。

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

26.Choosing Two Paths

27.Cyclic Cipher

28.Fragile Balls

29.Arbitrage

30.Point Set Range Sort Range Composite