Kick Start Round G 2020 题解

A.
注意到kick和start没有重复子母.
从左到右,每次碰到kick给cnt += 1,每次遇到start给ans += cnt.
复杂度(O(|S|)).
B.
求所有(i-j)相同位置的和的最大值.
复杂度(O(N^2)).
C.
对(X)排序后倍长,即对(i=W+1,cdots,2W,X_i=X_{i-W}+N).
枚举其中长度为(W)的一段求这段区间变成中位数的代价,还需要预处理前缀和.
复杂度(O(Wlog W)).除排序外复杂度是(O(W)).
D.
(dp[i][j]),表示长度为(i)的序列中第(j)个位置的期望贡献.
每个状态转移最多有(4)种.

1. 合并(j)左边两个,下标位置(-1);
2. 合并(j)和左边一个,下标位置(-1),贡献(+1);
3. 合并(j)和右边一个,下标不变,贡献(+1);
4. 合并(j)和右边一个,下标不变.

(O(N^2))预处理完后可以(O(N))求出每组数据答案.