联合省选 2026 游记

CommandSR · 2026-03-09 19:54:20 · 生活·游记

本来不想写的，后来想了一下发现高二不一定有机会了，还是写一下。

坐标 ZJ。

发现隔壁是 @Milmon，并且在签到表上看到了 @jiazhichen844。

总体来说就是比较爆炸。

Day1

recollector，这个名字不简单。

T1 看到是算一坨期望已经开始慌了。一开始想了一个假做法，假到只能过样例 1 的第一组测试数据，哦还能过个链。

想了很久，发现我算了个 l_u 表示 u 所在的重链期望长度，然后我直接把这个东西代入那坨概率算了。

那咋办，不会改，完全不太会刻画这个期望。我这人好像一旦陷入一个假做法就会受这个影响，重新思考的时候跳不出来，连树背包都没想到。

去做 T2，首先拼了一个指数级做法过了性质 A。

然后想性质 B，一开始想了一个贪心假了。后来发现可以给不同长度的连续 0 赋权值然后做背包 dp。进一步思考这个似乎也可以做性质 C，再爽拼一下就能过性质 D。但是这个非常难写难调，后面再来。

去做 T3，先果断写了一个 2^n。然后发现 m=1 应该也好做，但是我脑抽了以为直接判异或和是不对的。

中间好像注释里写了点小作文来着。

回去做 T1，产生了一大堆无效思考，这种感觉令我想起了 CSP 的不好的回忆。所以没有继续往下想。

去写 T2 背包 dp，但是到最后都没调出来。

这个时候脑子清醒了一点发现再不拼点暴力就没什么分了，补了一个 T1 的 2^n。写完就差不多结束了。

出场发现所有人都比我高。弘文。

我或许应该在比赛中知道我每一步在干什么。

Day2

交互题，传统题，传统题。

我从来没调过交互，且眼前是陌生的 Linux 系统。这不是又要炸了。

翻到 T2。

选手不需要，也不应该实现 main 函数。

哦这个也是交互，那做你马呢。

发现 T3 题面又臭又长，决定先研究一下交互题怎么调。

用 Geany 研究出来了，终于可以正常开题。

mex 这个东西的性质我本来就不太知道，而且是这种 Ad-hoc 状物的交互，所以一开始 T1 没什么思路。

看个特殊性质先，哦我会 A 性质。

再想一下发现 B 性质也会了。

其实这个时候思考正解就可以轻易想到了，因为 B 性质基本上就是正解。

但是或许是因为“交互题”的外表，写完上面两个性质，我继续拼暴力。

会了 n^2 次查询，能过最小那档，把其中一个 n 换成二分查询就可以做到 n\log n 次查找，不知道有多少分。

写完测了以下随机数据，发现随机情况下 n 次查询都不到。极限数据也到不了 n\log n。

这个时候决定先看后面。

T2 怎么什么都不会。

读懂了 T3 题面，看这个数据范围应该可以写很大规模的暴力。

首先 r=1 是好做的，菊花也简单。

然后想了以下那堆空集嵌套好像本质上就是括号串。可以 O(n^2) 暴力求一遍括号串然后暴力求 f(x,y)。