联合省选 2026 游记

· · 生活·游记

Day -1

询问 zwc2008 要不要复习一下交互题，zwc2008 表示省选并没有考过交互题，所以无需复习。出于严谨的心态，还是看了看猜数的交互模板。

Day 0

去华科试机，试机时间只有一个小时，心想试机题应该很简单吧，发现试机题是 P8114 [Cnoi2021] 六边形战士 a=b=c 的特殊情况，获得了 40 分的好成绩，数学题还是太神秘了，全场零个人切了这道题。

Day 1

开场看 T1，感觉维护一下链长的期望和 X 的期望就可以了，觉得非常简单，写完发现连小样例都过不了，手模一下样例，发现自己成唐氏了，式子完全是错的，想想感觉可以维护每个子树不同链长的概率，然后在树上每个点做 deg 次背包，每次用 set 维护一下转移的链长。但感觉不是很有前途，时间复杂度应该是 O(deg^2\times max_(dep))，遂去写 T2，A 性质直接 O(n^22^n)，B 性质尝试手模构造一下，发现选更多的 0 比较优，写了写发现有点小问题，似乎会比正确答案多一点，考虑背包准确转移，加 set 优化一下状态数，感觉比较可过，其它性质并不会写，于是实现了 30 分就溜了。又去看 T3，上来实现了 O(n2^n) 的暴力与测试点 3 的特判，又看了看其它性质，这都是啥玩意？只好逃去实现 T1 的暴力，调了一堆细节，发现大样例都过了？！但是自己用菊花 hack 了，并不会优化这个做法，直接赌数据太水（~埋下伏笔~）。又倒回去看 T3 性质，冥思苦想 n 久，发现又傻了，B 性质显然保证了每次合并的是后缀 1+3i 个数，直接搜索。

Day 1 期望分数 64+30+32=124。

Day 2

打开 pdf，发现 T1 题目类型是交互型，呵呵，T2 是披着传统型外衣的交互型，哈哈哈哈。（~已疯掉~）

看一眼 T1 发现好眼熟，发现 xyd 联考出过一样思路的计数题，于是 10 分钟就切了 T1（~有史以来最强的一次，xyd 你是我亲爹~），但出于 Day 1 T1 并不简单，决定拍一拍，发现 3\times 10^4 时 TLE 了，觉得很不对劲，我的代码明明是 O(n\log n) 的，于是看了看交互库，发现交互库【~数据删除~】是 O(n^3) 的，手改交互库为 O(n) 的，终于跑过了。

试题目录下的 grader.cpp 是交互库参考实现，最终测试时所用的交互库实现与该参考实现有所不同，因此选手的解法不应该依赖交互库实现。

我真的会谢！

考虑继续看 T2，这是什么东西？发现指数暴力都想不出，感觉要废，于是溜去看 T3，感觉测试点 1，2，5，6 非常可写，什么，你问我为什么写了 5Kb 代码，问就是测试点 1，2，5和6，分别实现了 3 种不同的算法，然后发现没有分可写了（~实则是太菜了~）。于是去写 T2 ,想了想可以用背包实现所有选择方案，然后再背包复原方案，应该有 8 分。

Day 2 期望分数 100+8+16=124。

于是省选期望总分 64+30+32+100+8+16=250（~这个分数怎么感觉在骂我~）。

Day 6

出分了，获得了 84+20+32+100+0+16=252（看起来比 250 舒服多了），考虑 Day 1 T2 没有特判 B 性质 n=1,k\neq 0 的情况，挂了 10 分，Day 2 T2 TLE 挂了 8 分，qwq。

这么看是不是还反向挂了 2 分，但别忘了还有伏笔，我 Day 1 T1 没有预处理逆元，如果预处理就可以跑过去，AC 记录 。

于是，我成功省选怒挂 34 分。哎，不对，如果不挂分我是不是刚好进队了（~红温了，现在变女队还来得及吗？~）。

已成功完成任务：高一 AFO。