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: 修复了错别字。

文章操作