chxB
比较板的在自动机上DP. 我们首先考虑如何判断一个给定了的串是不是合法的. 我们钦定从前向后扫描, 由于每个 c 和 p 在每个子序列中只出现一次, 所以它们就贪心去附加在已有的子序列后面就可以了, 但是相对而言困难的是决定 u 是作为一个新的子序列的开头, 还是附加在某个 c 后面呢?
可以采取如下的策略, 如果存在 uc , 那么就把 u 附加在后面得到一个 ucu , 若不然就自己形成一个子序列 u . 但是这样做会出现把一些原本要用来作为开头的 u 划分到 ucu 里, 于是我们再引入调整策略, 加入 c 的时候, 如果有现成的 u 就直接添加在后面, 如果没有, 那么就从现成的 ucu 里拆一个 u 下来给这个 c , 这样我们只需要记录下当前前缀总共分别有多少个 u , uc , ucu 即可. 然后我们把这个自动机的状态写进 DP 里就好了.
H
神秘贪心期望题. 由于答案只和最后的最大值相关, 所以对于初始序列, 我们先保留最大值, 其余的卡牌刷新不会使答案降低的, 所以我们会一直刷新 $k-1$ 次, 之后根据刷新的 $k-1$ 次的结果来决定要不要继续刷新. 具体的, 我们将 $S$ 中的元素排序, 之后我们枚举前 $k-1$ 次取到的最大值是多少(若这个值出现多次, 则可以考虑把它们之间再相互排序区分) , 假定是第 $m$ 个值, 那么最后抽一次的期望收益就是
$$\frac{m-k+1}{n-k+1}b_m+\frac{1}{n-k+1}b_{m+1}+...+\frac{1}{n-k+1}b_n$$我们根据这个值和初始序列的最大值取 $\max$ 即可, 最后我们需要求出刷新 $k-1$ 次最大值恰好为 $b_m$ 的概率, 这个东西可以拿组合数来算, 但是问题在于如果参照取模意义下预处理阶乘会丢掉很多精度, 于是天才wjr认为可以预处理阶乘的log, 最后计算的时候再exp回去.
I
首先wjr瞪出了一个结论:
假定数字 $i$ 最早出现的位置和最晚出现的位置分别是 $L_i,R_i$ 那么答案就是
$${\scr l} =\max_i R_i-L_i$$我们只说明答案的上界是这个. 若不然, 假定存在长度为 $l>\scr l$ 的匹配段落 $[x,x+l-1]$ , $[y,y+l-1]$ . 假定他们的交的长度为 $t$ , 于是他们的不交的子段 $[x,x+l-1-t]$ , $[y+t,y+l-1]$ 也是一对匹配段落由于这两个段内的值的出现次数相同, 所以我们可以匹配他们, 具体的, 令 $i\in[x,x+l-1-t]$ 去匹配 $\phi(i)\in[y+t,y+l-1]$ 要求这个 $\phi$ 是双射并且 $a_i=a_{\phi(i)}$ , 于是显然我们有 $\phi(i)-i\le R_{a_i}-L_{a_i}\le \scr l$ , 并且我们有
$$\begin{aligned}\sum_{i}\phi(i)-i&=\sum_{y+t\le i\le y+l-1}i-\sum_{x\le i\le x+l-1-t} i\\&=(l-t)*l\\&>(l-t)*\scr l\end{aligned}$$矛盾
有了这个结论之后我们考虑二分答案 $mid$, 对于每个 $i(\le k)$ 我要指派一个 $R_i$ , 之后要求所有的 $i$ 都出现在 $[R_i-mid,R_i]$ 内即可, 对于每个 $i$ 而言, 这个 $R_i$ 的选取是有一个连续的限制范围的. 我们考虑贪心, 从前向后往0内填数, 如果当前存在一个已经指定了的 $R_x$ 能够覆盖到这个位置那就填 $x$ , 若不然, 考虑选取可以覆盖到当前位置的且限制范围的右端点最小的那个 $R_x$ 将其确定下来并在这个位置填入对应的数. 整个过程使用一个堆来维护即可.
D
神秘博弈题. 没什么想法, 于是二分答案 $k$ . 这样问题就转化为了, 我有 $O(n)$ 个长度为 $k$ 的区间, 只要存在一个区间被全部填满 $0$ 那么就获胜了. 再进一步分析, 我们实际上只关心区间里的?, 于是每个区间被简化为了对某若干连续的?的限制. 假定第 $i$ 个区间限制的是第 $L_i$ 到第 $R_i$ 个问号, 则首先可以判断如果存在 $i$ 使得 $R_i=L_i$ 那么我就能获胜; 假定所有的 $i$ 均有 $R_i-L_i>2$ , 那么我一定无法获胜, 我们可以用归纳法来证明, 任意没被填过 $1$ 的问号区间至少包含两个问号, 只要我填了 0 对方就可以在区间内的另一个填 1. 最后只剩下 … 好繁琐不写了
E
有趣的计数DP. 首先观察出来一个等级 $i$ 是符合要求的当且仅当该等级的最小的车站 $L_i$ 和最大的车站 $R_i$ 是直接可达的. 在排除掉天然就符合要求的等级(即存在 $e$ 使得 $p_e\le R_i$ 且 $x_e\le i$ 或者只有一个车站)后, 第 $i$ 个等级符合要求当且仅当存在 $e$ 满足 $p_e<L_i \or L_i\le p_e<R_i\and x_e\le i$ 并且整个 $e$ 的 $y_e$ 要小于等于 $i$ . 这种至少存在一个的就很不好处理, 考虑容斥, 条件就变成了满足这个范围的 $e$ 的 $y_e$ 全部都要大于 $i$ . 朴素的容斥做法是枚举钦定违反的条件的集合, 然后在固定了这个集合的前提下得到了每个 $y_e$ 的选择范围从而算出满足这些限制的情况下有多少种取值, 之后将这个值乘以容斥系数贡献到答案里. 我们需要针对这个题目的违反条件所产生的影响来设计如何模拟这个枚举集合的过程. 注意到当多个 $i$ 作用到 $e$ 上时, 真正起作用的是最大的 $i$ , 所以我们考虑DP来解决它, 具体的, 考虑从大往小地决策是否违反第 $i$ 个等级的限制, 为此我们需要知道当前有哪些 $y_e$ 的范围已经被限制了从而计算在此基础上钦定违反第 $i$ 个等级的限制会导致多少没被限制过的 $y_e$ 变成被限制的状态. 之后观察到我们只需要记住上一个钦定违反的等级和第一个违反的等级就可以了(利用我们预处理的限制: 对于每个 $i$ 不存在 $e$ 使得 $p_e\ge R_i\and x_e\le i$), 于是这就变成了一个 $O(k^3)$ 的DP了, 而对于容斥系数, 常见的技巧是在钦定违反限制的时候把 $-1$ 乘进DP里一并转移就可以了.