查看源代码：
GZOI2025-2.md

---
title: GZOI 2025 两日游 · 其二
createTime: 2025/9/14
categories:
    - IT
tags:
    - OI
    - OI-travel-notes
---

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

但是二试比一试简单……

## ​T1

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

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

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

感觉被降智了。

## T2

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

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

:::warning 注意
最小单调切分个数和单调区间个数是不同的，例如 $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

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

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

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

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

### T3 正解

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

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

## T4

:::note 题意
给定一棵树，根为 $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$。

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