vp 了一下，发现自己还是被吊打。。

A

首先必须要和 $k$ 奇偶性相同，然后贪心地想最小能被表示出的数一定是 $\sum_{i=1}^k (2i-1) = k^2$，判断一下是否大于等于最小能被表示出的数和奇偶性就行了，一定可以通过调整每次增加 $2$。

B

先按照他的方式模拟一遍，然后判断是否有落单的公主，如果有的话可以直接和随便一个落单的王子匹配。因为他们俩落单了就说明和后面的选取完全没有关系，不会影响后面的选择。

C

注意到这个奇怪的限制“如果一个格子在边界上并且向边界的方向移动，那么会不动“，所以我们先花费 $n-1+m-1$ 步将所有棋子都聚集在 $(1,1)$，再通过 $nm-1$ 步遍历所有格子就可以了。总步数是 $nm+n+m-3 \leq 2nm$，注意到 $n,m \geq 1$ 就可以证明这个不等式了。

D

一开始看错题了自闭了一会。。

首先可以连出边 $i \to p_i$，一个排列合法当且仅当有一个环的所有颜色相同。

这个题 $p^{k+1}$ 的意义就是让每个点指向它走 $k$ 步能到达的点。我们对于每个环分开考虑：设当前考虑的环环长为 $l$，一个 $k$ 有意义当且仅当 $k|l$（会将环按 $\bmod k$ 分类分成 $k$ 个小环），所以我们可以直接去枚举 $l$ 的因子（大概有 $<300$ 个），判断一下这种分组是否能分出一个颜色相同的环就行了。

注意实现的时候判断部分要精细实现使得复杂度是 $O(l)$ 的，这样才能做到理论复杂度 $O(300\sum l_i) = O(300n)$，否则可能会退化。

E

这个题感觉 Div2B 还差不多啊。。之前有个 Div2B 就这样的。

这个题要计算长度为 $k$ 的极大相同段数量，我们分类讨论：

• $k=n$，答案显然是 $10$
• $k < n$，我们去枚举所有长度为 $k$ 的区间：首先我们有两个贴着边界的区间，方案数是 $2 \times 10 \times 9 \times 10^{n-i-1}$（$9$ 的原因是要强制和这个区间不同），那么还有 $n-k-1$ 个不贴着边界的区间， 方案数是 $(n-k-1)\times 10 \times 9 \times 9 \times 10^{n-k-2}$。

预处理 $10$ 的次幂就好了（说个笑话，我这里数组越界了但还是过了）

F

当时 vp 的时候想的是对的但是没写。。我那个想法还是比较初步细节比较多。看了题解之后思路就更明确了。

首先我们显然可以每一位考虑，现在限制就变成了限制一段区间 $[l,r]$ 是全 $1$ 或者是至少有一个 $0$。

我 vp 时的想法是大力讨论变成只有至少有一个 $0$ 的情况然后去掉包含段然后dp，但是其实不用那么麻烦：我们设 $f_i$ 表示 $i$ 位置为 $0$ 的方案数，如果 $i$ 有限制为 $1$ 那么显然 $f_i = 0$，否则我们可以直接预处理 $las_i$ 表示最小的 $j$ 满足 $[j+1,i-1]$ 填 $1$都是合法的（其实这里可以先让 $las_{r_i} = l_i$ 然后前缀 $\max$ 一下就可以包括所有包含和相交的区间的情况了），那么转移就有 $f_i = \sum_{las_i \leq j < i} f_j$，可以直接转移的时候顺便处理出前缀和/开个指针维护。

G

考完才发现是个 sb 题但是当时考试的时候没看。。

如果没有 ? 我们只需要建出 AC 自动机，每个点的权值就是 fail 树上到祖先所有点的点权和，答案就是走一遍，把每一步到达的节点的点权和加起来。

有的话我们可以考虑dp：设 $f_{i,v.S}$ 表示考虑了 $S$ 的前 $i$ 位，已经使用了 $S$ 内的字符的最大收益，直接转移即可。但是这样的复杂度是 $O(|S| \times \sum|t_i| \times 2^{\Sigma} \times \Sigma)$ 的，不能通过。

我们发现中间一大步不是 ? 的位置转移都是一样的，所以我们只需要考虑在 ? 的地方转移，只需要对于每一段没有 ? 的极长区间预处理出 $to_i$ 和 $val_i$ 表示走过这段区间后到达那个点和中间的收益即可，所以只用转移问号的个数次，也就是 $\Sigma$ 次。现在复杂度变成了 $O(\sum|t_i| \times 2^{\Sigma} \times \Sigma^2)$，还是过不了。

我们只需要加一点优化：在 dp 状态不合法的地方不转移即可。为什么呢？

因为我们注意到处理到第 $i$ 个问号合法的状态集合维 $S$ 一定保证 $|S| = i$，所以复杂度就是 $O(\sum |t_i| \times 2^{\Sigma} \times \Sigma)$ 了，这样就稳过了。