当前没有测试数据。

T1 追逐游戏 2

关键观察

先看什么情况下 Prof. Shou 一定逃不掉。若他位于度数为 $1$ 的叶子 $x$，Prof. Pang 位于 $x$ 唯一的邻点，那么 Prof. Shou 无论停留还是走向该邻点，都会在这一回合被抓住。因此，原树的每个叶子都必须通过新增通道得到至少一个新的逃跑方向。

这个新方向不能只通向与原父亲相邻的房间。设叶子 $x$ 的原邻点为 $p$。如果它新增的每个邻点也与 $p$ 相邻，那么 Prof. Shou 从 $x$ 出发、Prof. Pang 从 $p$ 出发时，Prof. Shou 仍无法走到一个不被 Prof. Pang 一步到达的房间。因此，$x$ 至少需要一条通向不与 $p$ 相邻的房间的新增边。该房间可以是另一组叶子，也可以是非叶顶点；后者并不改善下界。

把叶子按照它们在原树中的唯一邻点分组。设叶子总数为 $L$，最大一组的大小为 $M$。一条新增边至多照顾两个叶子，所以至少需要 $\lceil L/2\rceil$ 条边；一条边又至多照顾最大组中的一个叶子，所以还至少需要 $M$ 条边。答案的下界是叶子总数一半上取整与最大叶子组大小的较大值，即

$$\max\left(\left\lceil\frac L2\right\rceil,M\right).$$

正解算法

1. 统计叶子分组

遍历所有顶点。若顶点 $x$ 的度数为 $1$，就把叶子总数 $L$ 加一，并把其唯一邻点 $p$ 的计数 $c_p$ 加一。最后令

$$M=\max_p c_p.$$

2. 判断无解

当 $n=2$ 时，图中只有一条已经存在的边，不能再添加一条新的简单边，答案为 $-1$。

当 $M=L$ 时，所有叶子都有同一个邻点。对 $n>2$ 的树，这正是星形树。叶子之间全是兄弟，任何新增边都不能给叶子提供一个不与中心相邻的落点，因此无解，输出 $-1$。

3. 输出最少边数

其余情况输出

$$\max\left(\left\lceil\frac L2\right\rceil,M\right).$$

虽然题目只要求数量，仍需证明这个下界确实能达到。只在父亲不同的叶子之间加边：

• 若 $M>L-M$，先把最大组外的每个叶子与最大组中的不同叶子配对；最大组内尚未覆盖的每个叶子再连向任意一个组外叶子。共使用 $M$ 条边。
• 若 $M\le L-M$，不存在超过一半的叶子组。每次从当前叶子数最多的两个不同组各取一个叶子配对，可以得到覆盖所有叶子的匹配；若 $L$ 为奇数，最后只剩一个叶子，再把它连向任意一个父亲不同的、已经配对的叶子。共使用 $\lceil L/2\rceil$ 条边。

第一种构造的新增边构成二分图，第二种构造的新增边构成匹配外加至多一条边；两者都不会在新增边之间产生三角形。又因为只连接父亲不同的叶子，也不会和原树中的两条边组成三角形。加边后的图没有三角形，且每个顶点的度数都至少为 $2$。

正确性证明

引理 1：每个叶子都需要一条有效新增边

设原叶子 $x$ 的唯一邻点为 $p$。若 $x$ 没有新增边，Prof. Shou 从 $x$ 出发、Prof. Pang 从 $p$ 出发时必被抓住。即使增加了边，只要 $x$ 的所有新增邻点仍与 $p$ 相邻，Prof. Pang 也能在 Prof. Shou 第一步后立即抓住他。因此，每个原叶子都必须关联一条另一端不与其原父亲相邻的新增边；另一端不必是叶子。

引理 2：任何方案至少需要 $\max(\lceil L/2\rceil,M)$ 条边

一条新增边最多关联两个叶子，覆盖全部 $L$ 个叶子至少需要 $\lceil L/2\rceil$ 条。对于含 $M$ 个叶子的最大组，连接两个同组叶子的边对这两个叶子都无效，因为另一端仍与共同的父亲相邻；因此每条有效新增边最多覆盖该组的一个叶子，至少需要 $M$ 条。两者同时成立，得到所述下界。

引理 3：非星形树可以用该下界条边构造出无三角形且最小度数至少为 $2$ 的图

前述两种跨组配对构造分别使用 $M$ 或 $\lceil L/2\rceil$ 条边，恰好等于下界。每个原叶子至少得到一条新边，原非叶顶点的度数本来就至少为 $2$，故新图最小度数至少为 $2$。新增边只连接不同组叶子，且新增边自身不成三角形，所以新图无三角形。

引理 4：在无三角形且最小度数至少为 $2$ 的图上，Prof. Shou 能从任意不同的初始位置永远逃脱

轮到 Prof. Shou 行动时，若两人不相邻，他留在原地即可，Prof. Pang 一步不能到达他。若两人相邻，Prof. Shou 当前顶点至少还有另一个邻点 $z$。因为图中没有三角形，$z$ 不与 Prof. Pang 当前所在顶点相邻；Prof. Shou 移到 $z$ 后，Prof. Pang 仍无法一步抓住他。每回合重复这一策略即可永远不被抓住。

由引理 1、2，答案不可能小于公式；由引理 3、4，非星形且 $n>2$ 时公式给出的边数一定可行。算法输出正确。

部分分做法

各子任务独立计分。

子任务 1（30 分）

本子任务保证任意两个叶子都不与同一个顶点相邻。先处理 $n=2$；其余情况下扫描所有顶点，统计叶子总数 $L$。

由于每个叶子的父亲都不同，最大叶子组大小恒为 $1$，不存在星形无解情形。把叶子两两跨组连接即可，若叶子数为奇数，就让最后一个叶子再连接到任意其它叶子。因此答案是 $\lceil L/2\rceil$。

时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。这个做法没有统计最大叶子组；一旦一般数据中多个叶子共享父亲，$\lceil L/2\rceil$ 可能小于真正下界，甚至可能遇到星形树，所以不能保证通过后续子任务。

子任务 2（35 分）

本子任务保证每个测试用例的 $n\le 6000$。可以使用完整数学结论，但用朴素方法统计最大叶子组。

先收集每个叶子的唯一邻点。对每个叶子，再扫描全部叶子，数出有多少叶子与它的唯一邻点相同，所有计数的最大值就是 $M$。然后按正文判定 $n=2$、$M=L$，或输出 $\max(\lceil L/2\rceil,M)$。

时间复杂度为 $O(n^2)$，空间复杂度为 $O(n)$。在 $n$ 扩大到 $100000$ 且叶子数为线性级别时，两层扫描需要数十亿次比较，无法保证通过完整范围。

子任务 3（35 分）

本子任务没有额外限制。使用正文完整算法：扫描叶子时直接令其唯一邻点的计数加一，再扫描计数数组得到 $M$，最后输出无解或两个下界的较大值。

时间复杂度和空间复杂度均为 $O(n)$。按父亲编号排序叶子后分组的 $O(n\log n)$ 做法也能通过完整范围；原限制无法稳定区分这个对数因子，因此它与线性做法同属满分层。

复杂度分析

每个测试用例只需扫描顶点和边，时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。所有测试用例的 $n$ 之和不超过 $2\times 10^5$。

实现要点

• $n=2$ 需要单独判无解；此时两个顶点都是叶子，但不存在可添加的新边。
• 只需统计每个叶子的唯一邻点，不需要真正构造新增边。
• 星形树的判定是 $M=L$，不能只按某个顶点的度数猜测。
• 每个测试用例结束后要清空使用过的邻接表或度数数组。

T2 模式搜索

关键观察

设 $m=|t|$。若同一个模式串 $P$ 在文本中从位置 $0,p,2p,\ldots$ 开始连续出现，则 $P_i=P_{i+p}$，也就是说 $P$ 必须以 $p$ 为周期。

把模式串按下标模 $p$ 分成 $p$ 列。每一列必须填同一个字母。若 $m=bp+r$，则前 $r$ 列在模式中出现 $b+1$ 次，后 $p-r$ 列出现 $b$ 次。于是问题变成：能否把 $p$ 列分配给 26 个字母，使得每个字母在模式中的总次数恰好等于 $t$ 中的次数。

如果某个字母在 $t$ 中出现 $c$ 次，而一列贡献 $b$ 或 $b+1$ 次，那么这个字母占用的列数 $x$ 必须满足

$$\left\lceil \frac c{b+1}\right\rceil \le x \le \left\lfloor \frac cb\right\rfloor .$$

同时，其中有多少列是长列（贡献 $b+1$ 次）由 $c-bx$ 决定。只要各字母所取列数之和为 $p$，长列总数就自动等于 $\sum c-bp=m-bp=r$，因此可以构造这样的模式。

接下来考虑 $k$ 次出现。第一次出现已经消耗了 $t$ 的字母。之后每多一次出现，只会在末尾额外增加一个长度为 $p$ 的周期块。因此若某个字母占用了 $x$ 列，就还需要额外消耗 $(k-1)x$ 个该字母。文本 $s$ 的剩余字母数量给出了上界。

正解算法

先统计 $s$ 和 $t$ 的 26 个字母出现次数。若存在某个字母在 $s$ 中少于在 $t$ 中，则连一次都无法出现，答案为 $0$。

然后枚举周期长度 $p=1,2,\ldots,m$。设 $b=\lfloor m/p\rfloor$，$r=m\bmod p$。对每个在 $t$ 中出现过的字母 $a$：

• 记 $c=\mathrm{cnt}_t[a]$。
• 这个字母占用的列数下界为 $L_a=\lceil c/(b+1)\rceil$。
• 上界先为 $U_a=\lfloor c/b\rfloor$。
• 若希望总共出现 $k>1$ 次，则还需满足 $(k-1)x_a\le \mathrm{cnt}_s[a]-\mathrm{cnt}_t[a]$，所以 $U_a$ 还要与 $\left\lfloor(\mathrm{cnt}_s[a]-\mathrm{cnt}_t[a])/(k-1)\right\rfloor$ 取最小值。

对固定的 $p$ 和 $k$，只需判断每个区间 $[L_a,U_a]$ 是否非空，以及是否满足 $\sum_a L_a\le p\le\sum_a U_a$。这是整数区间的和能否取到 $p$ 的充要条件；长列总数随后自动正确。$k=1$ 已由最初的字母计数检查处理。

对固定 $p$，可行性关于 $k$ 单调：如果能出现 $k$ 次，也一定能出现更少次。因此对 $k-1$ 二分。枚举所有 $p$ 后取最大值。

复杂度分析

每个周期 $p$ 的可行性检查只扫描 26 个字母，并对出现次数做一次二分。总复杂度为

$$O(26\cdot |t|\log |s|),$$

可写作 $O(|t|\log |s|)$。空间复杂度为 $O(26)$。

部分分做法

子任务 1（15 分）

本档中，每个测试用例的模式串只由同一种字母组成，且模式长度至少为 2。

设模式为字母 $c$ 重复 $m$ 次。无论怎样重排模式，它仍然是 $c^m$。为了让它出现尽量多次，应把文本中所有 $c$ 放在一个连续段里。若文本中共有 $C$ 个 $c$，则长度为 $m$ 的全 $c$ 子串有

$$\max(0,C-m+1)$$

个，这就是答案。

该做法只需统计 $c$ 在 $s$ 中的出现次数，时间复杂度 $O(|s|+|t|)$，空间复杂度 $O(1)$。它不能处理模式含有多种字母的情况，因此不能保证通过后续子任务。

子任务 2（20 分）

本档中，每个测试用例的模式串所有字母两两不同。

如果模式中每个字母只出现一次，那么它不可能以小于 $|t|$ 的距离与自己重叠出现。否则重叠部分会要求模式中两个不同位置的字符相等，与“所有字母两两不同”矛盾。因此多次出现只能看成若干个互不重叠的完整模式。

每出现一次模式，就需要消耗模式中每个字母各一个。于是答案为这些字母在文本 $s$ 中出现次数的最小值。时间复杂度 $O(|s|+|t|+26)$，空间复杂度 $O(26)$。

该做法依赖模式字符互异。一旦模式中有重复字母，重叠出现可能显著优于非重叠放置，所以它不能通过完整数据。

子任务 3（65 分）

本档为题目完整数据范围，需要使用上文完整算法。

关键是枚举相邻出现的起点差 $p$，把模式按下标模 $p$ 分成周期列。设 $|t|=bp+r$，每列在一个模式内贡献 $b$ 或 $b+1$ 次。对每个字母建立占用列数的上下界，并在文本剩余字母数限制下检查出现 $k$ 次是否可行。固定 $p$ 时对 $k$ 二分，枚举所有 $p$ 取最大值。

时间复杂度 $O(26\cdot |t|\log |s|)$，空间复杂度 $O(26)$。

实现要点

• $b=\lfloor m/p\rfloor$ 至少为 $1$，因为只枚举 $p\le m$。
• 计算 $\lceil c/(b+1)\rceil$ 时不要用浮点数。
• 二分的是额外出现次数 $k-1$ 更方便；最终答案要加上第一次出现。
• 若 $t$ 中某字母根本不存在，可以跳过它，否则区间约束会被无意义的 $0$ 干扰。
• 所有字符串总长度可达 $4\cdot 10^6$，需要线性读入和常数级额外空间。

正确性证明

任取一个有 $k$ 次出现的方案。设相邻出现起点的最小差为 $p$；若 $k=1$，单独处理即可。若 $p<|P|$，那一对出现重叠，要求 $P_i=P_{i+p}$，所以 $p$ 是模式串 $P$ 的周期；若没有重叠，可取 $p=|P|$。按起点顺序放置原方案中的出现时，每次新增出现至少追加末尾 $p$ 个字符，而这些字符正是以周期 $p$ 等距放置时每次需要追加的字符。因此把这 $k$ 次出现改为等距放置，不会增加任何字母的使用量。反过来，只要 $P$ 有周期 $p$，按距离 $p$ 等距放置就能得到 $k$ 次出现。

对固定 $p$，每个字母占用多少列完全决定了它在一个模式内的出现次数范围：短列贡献 $b$ 次，长列贡献 $b+1$ 次。因此 $L_a$ 与 $U_a$ 给出了所有可能列数的充要范围。只要列数之和为 $p$，长列总数就恰好为 $r$。多出现一次只额外添加一个周期块，所以额外消耗正好等于各字母占用列数。文本剩余字母数量限制由此给出。

以上条件既必要又充分。枚举所有可能的相邻起点差 $p$，并对每个 $p$ 求最大可行出现次数，就覆盖了最优方案。

T3 彩虹数组

关键观察

考虑希望变成彩虹子数组的一段 $[l,r]$。修改后的元素应满足

$$a_i'=x+i$$

其中 $x$ 对整个区间固定。令

$$b_i=a_i-i,$$

则把 $[l,r]$ 变成彩虹子数组的修改次数恰为

$$\sum_{i=l}^{r}|b_i-x|.$$

于是原问题等价于：寻找最长连续区间，使区间内所有 $b_i$ 变成同一个整数所需的最少修改次数不超过 $k$。

对于一组数，函数 $\sum |b_i-x|$ 在中位数处取得最小值。因此，若窗口中位数为 $m$，窗口的最小修改代价就是

$$\sum_{b_i<m}(m-b_i)+\sum_{b_i>m}(b_i-m).$$

最后，删除窗口中的任意元素都不会增大最小修改代价。因此，当右端点向右移动时，如果当前窗口代价超过 $k$，不断右移左端点，直到窗口重新合法即可。这正是滑动窗口所需的单调性。

正解算法

对每组测试数据：

1. 将每个元素改写为 $b_i=a_i-i$。

2. 用两个可重复元素的有序集合维护当前窗口：

   • low 保存较小的一半；
   • high 保存较大的一半，并令 high 的最小值作为中位数；
   • 同时维护两边元素和 sum_low、sum_high。

3. 始终保持 $|high|=|low|$ 或 $|high|=|low|+1$，并保证 low 中所有数不大于 high 中所有数。

4. 设中位数 $m=\min(high)$。窗口代价可在 $O(1)$ 时间计算为

   $$(m\cdot |low|-sum\_low)+(sum\_high-m\cdot |high|).$$

5. 从左到右枚举右端点，把新元素加入两个集合。若代价超过 $k$，就依次删除左端点元素并重新平衡，直至代价不超过 $k$。

6. 每次更新答案为当前窗口长度的最大值。

正确性证明

首先证明下标平移的等价性。区间修改后为彩虹子数组，当且仅当存在整数 $x$，使其中每个位置满足 $a_i'=x+i$。单次修改只改变一个元素 $1$，故固定 $x$ 时的最小操作数为 $\sum |a_i-(x+i)|=\sum |b_i-x|$。

其次，根据中位数最小化绝对值距离和的性质，选择窗口中位数 $m$ 时，上式达到最小值，所以算法计算出的窗口代价正是把该窗口改成彩虹子数组所需的最少操作数。

最后，合法窗口的任意子窗口仍合法：从一个可行修改方案中删去被移出窗口的元素，对剩余元素的修改次数不会增加。因此，当右端点固定时，算法不断移动左端点后得到的是最靠左的合法位置，也就是以该右端点结尾的最长合法窗口。枚举所有右端点并取最大值，所得答案即为全局最优。

部分分做法

子任务 1（10 分）

本档中，每组序列长度与所有测试数据的总长度均不超过 $30$。

仍先令 $b_i=a_i-i$。枚举区间 $[l,r]$，再枚举区间中的某个 $b_p$ 作为统一后的目标值 $x$，逐项计算

$$\sum_{i=l}^{r}|b_i-x|.$$

绝对值距离和的最优点总可以取在某个已有元素处，因此枚举这些候选不会漏解。时间复杂度为 $O(n^4)$，空间复杂度为 $O(n)$。

当 $n$ 增大到下一档范围时，区间、目标和元素的四重枚举无法通过，所以该做法不能保证获得更高档分数。

子任务 2（35 分）

本档中，每组序列长度与所有测试数据的总长度均不超过 $2000$。

枚举左端点 $l$。对固定的 $l$，从左到右扩展右端点，并用两个可重复元素的有序集合维护当前区间的中位数和两侧元素和。这样每次扩展后都能快速判断当前区间代价是否不超过 $k$。

每个左端点需要 $O(n\log n)$ 时间，总时间复杂度为 $O(n^2\log n)$，空间复杂度为 $O(n)$。这个做法已经使用了下标平移和中位数性质，但没有利用左端点只需单调移动的观察；在完整的 $5\times10^5$ 规模下会超时。

子任务 3（55 分）

本档满足题目完整数据范围。

使用正文中的完整算法：右端点逐步扩展窗口，当中位数代价超过 $k$ 时持续删除左端点。删除元素不会增加最优代价，所以左端点只会向右移动，每个元素最多加入和删除各一次。

时间复杂度为 $O(n\log n)$，空间复杂度为 $O(n)$。实现时必须正确处理重复值、窗口为空时的边界，以及 64 位代价。

复杂度分析

每个元素至多加入和删除各一次，每次集合操作为 $O(\log n)$。

• 时间复杂度：$O(n\log n)$；
• 空间复杂度：$O(n)$。

所有测试数据的 $n$ 之和不超过 $5\times 10^5$。

实现要点

• 必须先计算 $a_i-i$；下标从 $1$ 开始。
• 元素可能重复，因此要使用 multiset，删除时只删除一个迭代器指向的副本。
• $k$ 可达 $10^{15}$，窗口元素和与代价必须使用 64 位有符号整数。
• 插入或删除后都要恢复两边大小关系和有序关系。
• 空窗口没有中位数；实现中应在计算代价前保证 high 非空。

T4 激进舍入

核心观察

我们需要统计区间 $[0,z]$ 中有多少个整数 $y$ 能经过若干次操作变成 $x$。

一次操作会把某一位变成 $0$：该位小于 $5$ 时向下舍入，否则向上舍入并向更高位产生进位。虽然操作顺序很多，但从高位到低位观察时，所有可能的舍入历史只需区分三种等价状态。记为 $0,1,2$。

把 $x$ 和候选数 $y$ 都补成 $20$ 位十进制数。处理某一位时，设 $x$ 在这一位的数字为 $d$，$y$ 的数字为 $j$。若处理更高位后的状态为 $s$，处理当前位后得到状态 $s'$。所有合法转移如下；表中的集合表示允许的旧状态：

$d$ 的情况	$j$ 的情况	新状态 $s'$	允许的旧状态 $s$
$d=0$	$j<4$	$2$	$0,2$
	$j=4$
		$1$
	$j>4$	$2$	$1,2$
$d=1$	$j=0$	$1$	$0,2$
	$j=1$	$2$
	$2\le j<5$	$1$
	$j\ge5$		$1,2$
$d\ge2$	$j=d-1$		$0,2$
	$j=d$	$0$

除此之外均无合法转移。初始状态为 $0$，所有数位处理完后，状态 $0$ 和 $2$ 合法，状态 $1$ 不合法。

这张转移表可以直接由舍入规则逐位得到：向下舍入不会影响更高位，向上舍入只会向更高位传递一个进位；连续的进位以及某位已经被置零的情况合并后，恰好只剩上述三类。数字 $4$ 与 $5$ 是向下、向上舍入的分界，因此 $d=0$ 和 $d=1$ 时需要单独讨论；当 $d\ge2$ 时，候选位只能是 $d$ 或因进位而对应的 $d-1$。

数位 DP

在上述三状态自动机上增加对上界 $z$ 的限制即可。

令

$$dp[p][s][t]$$

表示已经处理完比第 $p$ 位更高的数位，当前自动机状态为 $s$ 的方案数。其中 $t=1$ 表示候选数当前的前缀与 $z$ 相同，$t=0$ 表示已经严格小于 $z$。

初始时尚未选择任何数字：

$$dp[20][0][1]=1.$$

从高位到低位枚举位置，再枚举候选数字 $j\in[0,9]$：

• 若 $t=1$，必须满足 $j\le z_p$；
• 新的上界状态为 $t'=t\land(j=z_p)$；
• 根据上表，将当前方案转移到对应的新自动机状态。

处理完全部 $20$ 位后，答案为

$$\sum_{t\in\{0,1\}}\bigl(dp[0][0][t]+dp[0][2][t]\bigr).$$

补前导零不会改变数值，也不会影响操作的可达性。使用 $20$ 位足以覆盖 $0\le x,z\le10^{18}$，并为最高位可能涉及的进位留出空间。

正确性证明

首先，对任意已经处理的高位前缀，将所有可能的舍入操作按其对未处理低位的影响分类。向下舍入不产生进位，向上舍入至多产生一个向高位传播的进位，而已经舍入的数位均为零。因此所有舍入历史对后续数位的影响只可能属于状态 $0,1,2$ 三类。

对当前位枚举目标数字 $d$ 和候选数字 $j$。分别考虑 $d=0$、$d=1$ 和 $d\ge2$，再按照 $j<5$ 或 $j\ge5$ 判断该位向下还是向上舍入，可逐项得到转移表。故表中每个转移都对应至少一种合法操作序列，而任何合法操作序列也必然落入表中的某个转移。

由高位到低位归纳，DP 中的每个方案与一个前缀满足自动机条件的候选数一一对应。紧致标记保证且仅保证完整候选数不超过 $z$。全部数位处理后，状态 $0$ 和 $2$ 表示所有影响均已闭合，恰好对应能够舍入为 $x$ 的数；状态 $1$ 仍有未完成条件，不能计入。因此算法统计的正是区间 $[0,z]$ 中所有可激进舍入为 $x$ 的整数。

复杂度分析

每组数据处理 $20$ 个数位、$3$ 个状态、$2$ 个上界状态，并枚举 $10$ 个数字，时间复杂度为 $O(20\times3\times2\times10)=O(1)$，空间复杂度为 $O(20\times3\times2)=O(1)$。

实现要点

• 使用 long long 存储输入和答案；最大答案为 $z+1\le10^{18}+1$。
• 固定提取 $20$ 位数字，未出现的高位补零。
• 转移表中的分界是 $j<4$、$j=4$、$j>4$，以及 $j<5$、$j\ge5$，实现时应注意边界。
• 每组测试数据开始前清空 DP 数组。

部分分做法

子任务 1（10 分）

本子任务满足 $x=0$。任意非负整数都可以通过若干次舍入变为 $0$，因此区间 $[0,z]$ 中的所有整数均符合要求，答案为 $z+1$。

每组询问的时间复杂度和空间复杂度均为 $O(1)$。该做法利用了 $x=0$ 的特殊性质，可以通过本子任务；当 $x\ne0$ 时，答案不再恒为 $z+1$，因此不能保证通过下一档。

子任务 2（15 分）

本子任务满足 $T\le10$ 且 $z\le1000$。可以枚举 $y=0,1,\ldots,z$，并从每个 $y$ 出发搜索所有能够通过舍入得到的不同整数状态；若其中包含 $x$，就将该候选计入答案。

设单个候选数可达的不同状态数为 $S$，数字位数为 $D$，则每组询问的时间复杂度为 $O(zSD)$，空间复杂度为 $O(S)$。在本档的小上界下，这一搜索规模足够小；下一档允许 $z$ 达到 $10^{18}-1$，逐个枚举候选将无法完成。

子任务 3（50 分）

本子任务中存在 $0\le k\le18$，使得 $z=10^k-1$。把候选数视为允许前导零的 $k$ 位十进制串后，区间 $[0,z]$ 恰好包含所有这样的串。可以建立一个三状态自动机，记录已经扫描的高位与后续舍入之间的关系，再从高位到低位进行动态规划。由于所有 $k$ 位串都不超过上界，无须维护与 $z$ 的前缀大小关系。

每组询问的时间复杂度为 $O(D\cdot3\cdot10)$，空间复杂度为 $O(1)$，其中 $D\le20$。该做法能够统计全 9 上界下的全部候选；下一档中的 $z$ 可以是任意数，只统计固定位数的全部串会把大于 $z$ 的候选也计入答案，因此不能保证通过下一档。

子任务 4（25 分）

本子任务没有额外限制。在三状态自动机的数位 DP 中加入上界状态：记录当前候选前缀是否仍与 $z$ 的前缀相同。若仍然相同，当前位不能超过 $z$ 的对应位；一旦选择了更小的数字，后续各位即可自由选择 $0$ 至 $9$。将 $x$ 与 $z$ 补至相同的固定长度，扫描完所有数位后累加自动机的接受状态即可。

每组询问的时间复杂度为 $O(D\cdot3\cdot2\cdot10)$，空间复杂度为 $O(1)$，其中 $D\le20$。上界状态保证只统计 $[0,z]$ 内的候选，因此该做法覆盖完整数据范围；这是最后一档，不存在更高档约束。