PTS 2026

035966_L3 · 2026-03-13 21:54:10 · 生活·游记

Day 1

Part 0 (8:00)

小 Y：我猜今年 D1T1 考树链剖分！

小 C：我猜今年 D1T1 考随机化！

哇，这都能猜对，他们俩真该考完去买彩票……

等等！！！GCC 9.5？Ubuntu 24.04？Intel Xeon Platinum 8372C @ 3.20GHz？

什么玩意？？？组委会铁了心不接受申诉？？？

组委会怎么这么……

Part 1 (8:30)

打开 T1！n \le 5000，那大概是 O(n^2) 的树上背包了！

然而……Tn^2 = 1.25 \times 10^8，1.5 秒？又要卡常数了？最后一档多达 36 分？？？

组委会怎么这么……

回归正题：对于题目中要求的结果，只需要求出每条边向下的重链长度的分布列，然后将每条边成为轻边的概率乘上对应的子树大小。

这样写完大概是 O(n^3) 的，大约有……只有 48 分吗？

Part 2 (9:30)

我似乎需要算出某些多项式的乘法，再分别除以每个多项式；但这么做对吗……？

那么让我猜猜：每次转移的时候，各个子树的决策是完全独立的，于是可以用解比例式代替多项式的除法：随机给边排序，一条边最终成为重边的概率，等于考虑到它时它成为重边的概率，乘上它后面的边都不成为重边的概率。

那么开始写吧！

[Custom Invocation, Sample Test #2]
(Time: 4 ms)

Output:
76071087
214734988
238202108
930516808
469062705

Answer:
609523566
506130945
706163310
806422043
285617817

[Wrong Answer!]

……好吧，这么写是错的。

Part 3 (10:00)

再这样整场 Day 1 搞不好就要 0 分了！先写 O(n^3)……

[Custom Invocation, Sample Test #7]
(Time: 1386 ms)

Output:
873482579
24221162
533965767
160335375
832211714

Answer:
873482579
24221162
533965767
160335375
832211714

[Accepted!]

嗯？大样例就这个强度吗？？？

组委会怎么这么……

那么多项式乘法时忽略最低次项后面的部分！

[Custom Invocation, Sample Test #7]
(Time: 1112 ms)

Output:
873482579
24221162
533965767
160335375
832211714

Answer:
873482579
24221162
533965767
160335375
832211714

[Accepted!]

好！但愿 System Test 能冲过去。

Part 4 (11:00)

接下来看到 T2！对于最开始的 15 分……爆搜！没什么好讲的。

……等等，大样例呢？？？

组委会怎么这么……

[Custom Invocation, Sample Test #1]
(Time: 105 ms)

Output:
10
Impossible
0101
011100
001100

Answer:
10
Impossible
0101
011100
001100

[Accepted!]

Part 5 (11:30)

接下来是特殊性质 B：将连续的 0 看成物品做背包。

[Custom Invocation, Sample Test #2]
(Time: 37 ms)

Output:
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000010
Impossible
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
Impossible
Impossible

Answer:
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000010
Impossible
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
Impossible
Impossible

[Accepted!]

Part 6 (11:50)

那么再来看 T3！对于前面 8 分，直接爆搜；对于接下来的 4 分，只需要比较异或和并随便操作。

但是……等等，那个大样例在 n \le 16 下给我 n = 7？？？

组委会怎么这么……

[Custom Invocation, Sample Test #2]
(Time: 5 ms)

...

[Accepted!]

Part 7 (12:30)

等等，再回到 T1……继续跳过所有系数非 0 的项！

[Custom Invocation, Sample Test #7]
(Time: 438 ms)

Output:
873482579
24221162
533965767
160335375
832211714

Answer:
873482579
24221162
533965767
160335375
832211714

[Accepted!]

好！！！但愿 System Test 能冲过去。

Part 8 (13:00)

再来看看 T2 能不能多拿些分！对于特殊性质 C……

继续做背包吧！猜测答案长度不大于 A = 200，时间复杂度是 O(kA^2)。

[Custom Invocation, Sample Test #3]
(Time: 481 ms)

Output:
011111101111110111111011111101111110111111011111110110111111110
01110111111111111111111111111111111111111111111111111011
000000000000000000000000000000000000000000001000000000000000000
Impossible
0111111110111111110111111111011111111010111111111

Answer:
000000000000000000000000000000000000000000000001111111100000000
00000111111111111111111111111111111111111111111111111000
000000000000000000000000000000000000000000000000000000000111101
Impossible
0000000000000000000000000000011111111110000000000

[Wrong Answer!]

答案长度是对的……但是等等，s 需要是 t 的子串！！！

这个大样例的强度很低！！！

组委会怎么这么……

[Custom Invocation, Sample Test #3]
(Time: 972 ms)

Output:
011111101111110111111011111101111110111111011111110110111111110
01110111111111111111111111111111111111111111111111111011
000000000000000000000000000000000000000000001000000000000000000
Impossible
0111111110111111110111111111011111111010111111111

Answer:
000000000000000000000000000000000000000000000001111111100000000
00000111111111111111111111111111111111111111111111111000
000000000000000000000000000000000000000000000000000000000111101
Impossible
0000000000000000000000000000011111111110000000000

[Accepted!]

啊！有惊无险。

Part 9 (13:30)

交卷！最终的得分是 100 + 45 + 12 = 157。

Day 2

Part 0 (8:00)

一圈测下来，你这排名还好啊！这场不要失误。

好吧，但愿不要失误。

Part 1 (8:30)

打开 T1……啊，交互题？

那么先稳住脚步，首先 0 的位置可以 O(\log n) 确定，然后两边以相同步长倍增，找到下一个元素后再确定方向。

那么……上限是 3n + \log n 次询问，期望 65 分。

但等等！！！大样例只有 n \le 100，交互库还是 O(n^3)？？？

组委会怎么这么……

Part 2 (9:10)

T2 看上去很抽象啊！先去看 T3。

那么这一大堆抽象的题面大概想让我们比较：

同构的树彼此相等。
空树是最小的树。
只有 1 个结点的树是第二小的树。
对于一般的两棵树，将它们的根结点去掉形成两个森林，将每个森林中的树按本规则制定的大小降序排序，然后像字符串那样给两个序列比较字典序。
由于子树的大小总是小于原树，递归的比较过程一定是有限的。

那么直接写是……O(n^3 \log n)？但是先写吧。

Part 3 (10:30)

啊？？？T3 样例解释更正？？？延时 15 分钟？？？

组委会怎么这么……

我都做了一个多小时的 T3 了，这该怎么办？

……等等！我理解题意时没看 T3 样例解释，那没事了。

Part 4 (10:40)

好，T3 的 O(n^3 \log n) 写完了！让我试试 n \le 2000 能不能过去……

[Custom Invocation, Sample Test #12]
(Time: 2069 ms)

...

[Accepted!]

哇，过去了！大概是随机数据卡不满吧。

Part 5 (10:40)

接下来看向 T2！对于 k \le 3 的特殊性质，不断操作直至每个点的度数 \ge n - 2 即可。

[Custom Invocation, Sample Test #4]
(Time: 104 ms)

...

[Accepted!]

Part 6 (11:10)

接下来看向 T1 的特殊性质 A！此时只需要以 0 位左端点都询问一下就好。

那么……上限是 3n + \log n 次询问，期望 70 分。

Part 7 (11:30)

接下来是特殊性质 B！此时的步长一定是 1，不用倍增，上限是 2n + \log n 次询问。

那么……上限是 3n + \log n 次询问，期望 71 分。

Part 8 (11:40)

等等，T3 的特殊性质 A……啊，直接分类讨论就好。

[Custom Invocation, Sample Test #8]
(Time: 7 ms)

...

[Accepted!]

Part 9 (11:50)

接下来，对于一般情况……啊，可以先确定方向再确定步长，此时上限是 2n + \log n 次询问。

那么……上限是 2n + \log n 次询问，期望 73 分。

Part 10 (12:10)

我会随机化！当一次方向猜测以 50\% 的概率成功时，我们可以跳过下一次猜测。

那么……上限是 \dfrac{5}{3}n + \epsilon 次询问，期望 77 分。

Part 11 (12:20)

等等，这个解法适用于特殊性质 B，此时的上限是 \dfrac{2}{3}n + \epsilon 次询问！

那么……上限是 \dfrac{5}{3}n + \epsilon 次询问，期望 82 分。

Part 12 (12:50)

啊！没什么事可做了。

Part 13 (13:50)

交卷！最终的得分是 82.31 + 12 + 20 = 114.31。

Summary

那么一切都结束了！最终的得分是 157 + 114.31 = 271.31。

…………