KTXY Round 1 官方题解

2026-03-02 19:23:19

发布于：河南

128阅读

0回复

0点赞

T1

经典 trick，将 $n \bmod m=S(m)$ 转化为 $n-\left\lfloor \dfrac{n}{m} \right\rfloor \times m=S(m)$ ，继而变成 $n-S(m)=\left\lfloor \dfrac{n}{m} \right\rfloor \times m$ 。由于 $S(m) \le 81$ ，所以考虑暴力枚举 $S(m)$ 。右式两个值均为整数，可以再次暴力枚举左式的约数当作 $m$ ，检查式子是否合法。

时间复杂度 $O(81 \times 9 \times \sqrt{n})$ 。

T2

不难发现答案 $\le 2$ 。分类讨论一下。

答案为 $0$ ，直接判断即可。
答案为 $1$ ，发现连接 $u,v$ 一条边之后，相当于可以对 $[u,v-1]$ 这段区间中的数进行循环移位，所以找到第一个不满足 $a_i=i$ 的和最后一个不满足 $a_i=i$ 的位置，将这段区间进行循环移位，判断能否合法即可。
剩下的答案为 $2$ ，这里给出一种构造：发现若能构造出能交换相邻两个数的操作，则整个序列一定可以任意排列。故连接 $(1,n),(1,n-1)$ ，设要交换 $a_i,a_{i+1}$ ，根据答案为 $1$ 中的结论，总可以进行循环移位将这两位移到开头，所以不妨假设交换的相邻的两个数为 $a_1,a_2$ ，下文设 $0$ 为空位， $i$ 为初始位置 $i$ 的数，当 $n=4$ 时，可以进行如下操作：

$12340 \to 02341 \to 23401 \to 03421 \to 13420 \to 01342 \to 21340$

此时成功构造出来交换相邻两个数的操作，于是证明答案 $\le 2$ 。

时间复杂度 $O(n)$ 。

T3

先钦定节点 $1$ 为根，即定根怎么做。

可以设计出来一个简单的 dp， $dp_{i,j}$ 表示以 $i$ 为根的子树中有 $j$ 个小型信标的方案数。

转移分为两种，一种为当前节点选择小型信标，即 $dp_{i,1}=1$ ；另一种就是正常树上背包合并：设当前与儿子 $v$ 合并，则有 $dp_{i,k} = \sum_{j=0}^k dp_{i,j} \times dp_{v,k-j}$ 。初值有 $dp_{i,0}=1$ 。滚动数组倒着枚举 $k$ 。

设 $siz_i$ 为以 $i$ 为根的子树，不妨将上面的 dp 转移时间放大，即每次合并时间为 $O(siz_v \times (n-siz_v))$ ，则总时间为 $O(n \times \sum siz_v - \sum siz_v^2 < n \times \sum siz_v)$ ，问题为求出 $\sum siz_v$ 。考虑每个点都会造成自己祖先个数的贡献，所以总时间复杂度上限为 $O(n^2 \times d)$ 。其中， $d$ 为树高。由于保证数据随机，在这种随机生成树的情况下，树高期望为 $\log n$ ，所以时间复杂度即为 $n^2 \log n$ 。

对于每个根来说，dp 一次的时间复杂度是 $O(n^2 \times \log n)$ 的，于是做到了 $O(n^3 \times \log n)$ 。发现对于相邻的根来说，很多节点的 $dp$ 值都没有改变，所以考虑换根 dp。

假设当前根为 $u$ ，要将根换到 $v$ 上，考虑处理三件事：

将 $v$ 对 $u$ 的贡献从 $dp_u$ 中退下。合并时是倒着枚举 $k$ ，退下贡献时则正着枚举 $k$ 。即 $dp_{u,k}=\dfrac{dp_{u,k}-\sum_{j=0}^{k-1} dp_{u,j} \times dp_{v,k-j}}{dp_{v,0}}$ ，由于 $dp_{v,0}=1$ ，所以分母可以直接去掉，这样使用 $O(n)$ 的时间就可以将 $v$ 对 $u$ 的贡献退下。
将 $dp_u$ 合并到 $dp_v$ 上，由于贡献已经退下，直接合并即可。
回溯是再将 $dp_u$ 复原，可以考虑先备份 $dp_u$ 数组。

换根的时间复杂度分析跟背包合并分析相同，总时间复杂度 $O(n^2 \times \log n)$ 。

T4

发现左端点一定为前缀 $\min$ ，右端点一定为后缀 $\max$ 。将这些端点进行重编号，考虑对中间的每个点 $i$ 算贡献，其会对 $l<i \land a_l<a_i$ 的左端点和 $r>i\land a_r>a_i$ 的右端点产生贡献。由于前缀 $\min$ 和后缀 $\max$ 都具有单调性，二分找出临界端点，相当于对 $l \in [a,b] \land r \in [c,d]$ 的矩形加 $1$ ，最后查全局 $\max$ 。扫描线加线段树维护即可。

有帮助，赞一个

去预览

0/2000

全部评论 6

Xylophone
orz
但是 $T\in[2,4]$ 题有 $[0,0]$ 发 AC 是不是有些离谱了（）还是某省二大佬只是在开摆（）

2026-03-03 来自广东
2
prediction
orz

2026-03-03 来自浙江
1
Eucatastrophe‌废号
省选模拟赛题解来了

2026-03-02 来自浙江
1
dream92143
orz

2026-03-02 来自江苏
1
不会C++的noah
ORZ

2026-03-02 来自浙江
1
Zzzzzzsr（不处）
orz

2026-03-02 来自广东
1

T1

T2

T3

T4

全部评论 6

热门讨论