推式子的复杂程度让​我时常感觉到自己打的是高联。

但是二试比一试简单……

​T1

题意

有 $n$ 个格子排成一列，其中一些可以落脚。每次只能向右跳 $1$ 或 $2$ 步，每次询问给出 $l, r$，求能否从 $l$ 跳到 $r$。

一想到这是 Day2，我一下子想复杂了，动态 DP 打到一半才发现正解（去年 D1T1 也是，辛辛苦苦打了矩阵快速幂，结果讲题的说通项公式其实就是个二次函数而已）

正解是把用连续两个不可落脚格把地图分割成若干块，$l$ 能到达 $r$ 当且仅当 $l \le r$ 且 $l,r$ 在同一块。

感觉被降智了。

T2

题意

求总共 $k$ 个 $\{1,2,\dots,m\}$ 或 $\{m,m-1,\dots,1\}$ 拼接成的所有数列的所有大小为 $n$ 的不同子序列的个数。

题意有一种等价表述： 求长度为 $n$ 且值域包含于 $[1,m]$ 且可以被切分成不多于 $k$ 个串，满足每个串都单调的整数列的个数 $\bmod (10^9+7)$。

注意

最小单调切分个数和单调区间个数是不同的，例如 $1, 2, 3, 2, 3, 4$，单调切分个数是 $2$，单调区间个数是 $3$。

考场上被这个卡住了，还是做了个朴素暴力对比才发现的。

​于是记 $f(i,j,t,w)$ 为数列长度为 $i$，最小单调切分个数为 $j$, 当前结尾为 $t$, 最后单调切分段的单调性为 $w \in \{\nearrow, \searrow, \bullet\}$ 时的方案数。

（注意：孤点需要占一种单独的单调性）。

孤点再分三种帮助转移：

• $\nearrow$：比前一个单调递减段高
• $\searrow$：比前一个单调递增段低
• $-$：恰好等于前一个数

​于是可得状态转移方程

$$\begin{align*} g(i, j, t, \nearrow) &= \sum_{1 \le t' < t} f(i-1, t-1, t', \searrow) \\ &= g(i, j, t-1, \nearrow) + { f(i-1, j-1, t-1, \searrow)} \\[12pts] g(i, j, t, \searrow) &= \sum_{t < t' \le m} f(i-1, j-1, t+1, \nearrow) \\ &= g(i, j, t+1, \searrow) + f(i-1, j-1, t+1, \nearrow) \\[12pts] g(i, j, t, -) &= \sum_{w\in\{\nearrow,\searrow,\bullet\}} f(i-1, j-1, t, w)\\ \\\hline\\ f(i, j, t, \bullet) &= \sum_{w\in\{\nearrow,\searrow,-\}} g(i, j, t, w) \\[18pts] f(i, j, t, \nearrow) &= \sum_{1 \le t' < t} f(i-1, j, t', \nearrow) + f(i-1, j, t', \bullet) \\ &= f(i, j, t-1, \nearrow) + f(i-1, j, t-1, \nearrow) + f(i-1, j, t-1, \bullet) \\[12pts] f(i, j, t, \searrow) &= \sum_{t < t' \le m} f(i-1, t, t', \searrow) + f(i-1, j, t', \bullet) \\ &= f(i, j, t+1, \searrow) + f(i-1, t, t+1, \searrow) + f(i-1, j, t+1, \bullet) \end{align*}$$

​ （越界的求值视为 $0$，且省略 $\bmod (10^9+7)$）。

插曲

喝了太多水，结果拉了。人体内环境稳态这一块（

​T3

​题意

有一个完全图，点有点权，边权为两点权的异或。从任意点出发进行遍历，每次离当前点最近的未访问的点中随机选一个访问。求所有可能路径的个数。

显然如果有重复的点权，这些点都会排到一起。于是考虑把点权去重，此时答案就会除以 $\prod_v \mathrm{count}(v)!$。
（这是之后才想到的，考场上只是把边权相同的点视作等价的而没有去重，这里先说正确方法，有助于理解）

丢掉标号之后就可以做了，见到异或最值不难想到建一棵 trie。（注意此处可重）

我是直接依题意删点模拟的，平方级。

T3 正解

​考察每条路径在 trie 上的转移，发现一定走完一个子树才会走到另一个子树。

​递归计算两个子树上的路径（含端点），然后合并两个子树的答案。

T4

题意

给定一棵树，根为 $1$，对于叶子 $f$，有点权 $w_f$，且路径 $1-f$ 上的任意两点可以以 $w_f$ 的时间互通。每次询问给定一个点集 $S$，求 $\displaystyle\sum_{u \in V} \min_{v \in S} \mathrm{dis}(u,v)$。

将非叶结点的点权定义为它的子树下的叶结点中最小的点权，则不难发现：

• 若 $u$ 为 $v$ 祖先，则 $w_u \le w_v$

• $$\mathrm{dis}(u,v) = \begin{cases} w_u + w_v, &\text{$u, v$ 无关} \\ w_u, &\text{$u$ 是 $v$ 的后代，反之亦然} \\ 0, &u=v \\ \end{cases}$$

于是可以把点 $u$ 分成三类：

1. 在点集中，对答案的贡献为 $0$
2. 在点集中某个点的子树下，对答案的贡献为 $w_u$
3. 其他情况，对答案的贡献为 $\displaystyle \min\left\{ w_u + \min_{v \in S} w_v, \min_{v \in S \cap \mathrm{subtree}(u)} w_v \right\}$

然后不会了，以此为基础的暴力写挂了。

T4 正解

树上关键点问题，考虑虚树（把树中的关键点抽出来），然后在虚树边（对应一条链）中二分向上/下走的位置。

​可以理解，但是确实不会。

分数

$${\color{green}{100}} + {\color{green}{100}} + {\color{orange}{35}} + {\color{red}{0}} = {\color{green}{235}}$$

​比上次 NOIP 还好。 上次 $200$，就算 T4 不挂也只有 $232$。

这对我来说也算是提振了信心。