CSP2025游记

· · 生活·游记

Day -inf

J组初赛免了，S组初赛79pts?反正过了。

Day -inf ~ -1

模拟赛都是三题，基本就是黄绿绿 2h通过 信心++

每天都看点模板题。But，Day -4时看到反悔贪心模板，感觉不大会考（wssb）

Day 0

老师在考前给我们发了一沓包含各种注意事项的资料，讲了1h后在试机前又给我们做了一黄一蓝的模拟赛（1h），黄题没写高精度挂了40pts（P7113），信心--

Day 1

J组

被压缩包硬控7min 555

神秘键盘回车和分号的相应会串在一起

T1若知题，5min。不是，原来 sort(a + 1, a + n + 1) 是从小到大排啊（伏笔 + 1）。 预估分100pts

T2看了半天没看到是S形排位，以为是Z形，卡了10min。预估分100pts

T3上来一眼前缀异或+贪心，但不会做，就整了个二分答案，二分子区间的最大长度，然后check里面用贪心求能有几段符合要求。大小样例都没问题，就用 O(n^2) 的暴力和他对排一下挂在那里（伏笔+1）预估分100pts

T4上来先写了个O(2^n)暴力，然后把全为1的特殊性质的结果算出来几项找规律，注意到 res_n = 2^n - (7 + \frac{(n - 3)(n + 4)}{2}) 预估分64pts。

随着监考老师提醒还有10分钟比赛结束的声音，我的T3对拍代码找到反例了（**）还是两个 \leq20 的反例，根本没空改。只能数据分治一下。预估分60+rand()pts。

总估分324pts，勉强还行。

S组

开局2h一分没拿。

和这个悲惨事件一起发生的还有键盘防滑的地方掉了，在厕所呆了30min（恶心、头疼、肚子的（疼））

T1先写了个O(3^n)暴力，然后写了一个100多行的反悔贪心，又另外写了个特殊性质B。预估分25+弱数据pts

T2先写出前4个测试点拿到16分，然后想了个O(n^2k)的暴力连边做法，发现挂了，于是将其与对原图做最小生成树的答案取min，顺利通过所有样例，但是n = 900, k = 7左右的样例要跑1.9s,遂想优化，然后注意到如果“将一个乡镇城市化并向原图连边”这个操作如果对答案有贡献那必定是松弛了一条在原图最小生成树上的边，但一直到考试结束都没有调出来，保留了O(n^2k)的做法。预估分80pts+-rand()

T3没看，直接输出0

T4先写了个O(n!)的8pts暴力，然后观察特殊性质A答案好像为n!或0？输出了一下，也不知道多少分。

考试结束还有15min，T1对拍：找到差异。我真的，欲哭无泪。检查发现只要有一个人对恰好两个组的满意度均为0时就会挂，没办法，只能这么挂着了。

又去看了眼T4。发现复杂度应为O(n^3)级别，就考虑设dp_{i,j,k} 表示前 i 个人中有 j 个没通过面试和 k 个人的耐心会被耗光的方案数。然后就不会了

总估分最高136pts,凉透了。

8年级，AFO，去搞MO了，祝好。