2025 csp 游记喵

· · 生活·游记

day -??

Lisakhanya 大小姐 给我看了一道题，问给你一些数，问你选 n 个数，每个数不超过 c_i，多少种使得选出的数互不相同的选法。

然后我给了一个摁数（正着算）和一个概率论（倒着算）的办法。（伏笔 0）

day -3

仔细看了准考证，主场作战喵 但是 407 逆天键盘。（伏笔 1）

day -1

模板赛赤过去了点双边双，好耶！

day 1

上午是领军，最累的一集（伏笔 2），拼尽全力未能战胜组合计数。

房间里有 n 个人，编号为 1\sim n，玩 n 轮游戏，每次选一个房间里编号最小的未行动的人行动，从 1\sim n 中等概率随机一个人踢出房间，若本不在房间内则无改变，求最终期望人数。

然后领军的时候发现自己右手食指指甲裂了疼疼疼。

然后就是 csp。

考前脑子里一直在过 飞萤燃夜，准备默写歌词！

就算 撕裂夜空照亮群星的光会致盲

也要 在坠落大地之前点燃海洋

哪怕和薄如蝉翼的命运 狭路上相撞

萤火霎时滚烫 烧灭之前最像太阳

可惜一直在和 t4 智斗

同桌是 lxc，逆天座位排布。

17 min 速通 t1，今年 t1 没那么水诶。

然后 23 min 速通 t2，写的 O(2^kn\alpha)，大样例跑的飞快，懒得管了。

然后 1 min 意识到 t3 是 acam 板子但是 虽然我赛前打了 KMP 板子并记住了如何建 ACAM 但我懒得写了 于是我打开了大样例，发现出题人蛮会造数据的还把 hash 卡满了，逆天！

于是迅速糊了一个依赖分块和比特赛特的玩意总之跑得很快（大样例 0.08s 诶），但是忘记判 t_i 大小，我不要 RE。

但是代码长度也不短导致写到 t4 的时候只剩 2h 了。

然后 Lisakhanya 大小姐的题迅速发力让我会了 m=1 和 m=n 的两个特殊性质并光速写出 O(n^2) 的特殊性质分。

然后接下来的 1.5h 全部贡献给了 O(n^4) 暴力但是就是调不对概率系数 ...?（Lisakhanya 那个题我最开始给了一个基于概率论的做法，不过这题好像拓展不到 ...?），因为这题要同时正着数和倒着数两个玩意。

然后去了卫生间。

到最后 30 min 我终于意识到可以两个都正着数，只需要多一个 n，然后写写写并通过小样例，但是大样例除了特殊性质以外全挂了 ...?

然后就坠机了。。。。

我不要 300\ pts- ！！！

day 2

领军全家桶！！

交换数学和物理分数（相比去年）。。。。

纯逆天。

数学：度量空间射影几何大乱斗

物理：Gibbs 熵 自由能 统计力学大乱斗

Bonus

领军那个题存在亚线性做法

upd 2025.11.6: 修复了错别字。