CSP-S 游记

· · 生活·游记

上午前两个小时摸鱼，敲了一会儿木鱼试图增加功德。

中午睡不着，心脏的轰鸣一直在宿舍回荡，一开灯就出宿舍了。

下午很紧张也很激动。

先看 T1，这是啥阴，一眼没有看出来，仔细想想，好像只会一个 O(n^3) 的 DP。

不会是 NOIP2024 T1 的神秘题吧？想了半个小时还是不会。

跳了，去做 T2。

T2 题目读错了，以为乡村就是原图的 1\sim k，写了个克鲁斯卡尔过不了样例，发现其实是新建节点。

仔细思考好像可以状压乡村，但是复杂度有点爆炸。

就把 O(n^2) 和性质的 72 分写了。

看 T3，现在有点暴钢了，没写出一道正解，但时间还早，才不到四点。

看了一下暴力分很多，有 70，抉择一下选择打暴力，变成暴力王了。

做完 B 性质发现会正解了，二维数点随便数数就行了。

此时五点出头，看 T4，排列计数是个大阴，把 20 分的状压写了后，稍微想了一下 DP 状态，f_{i,j,k} 表示前 i 天有 j 人淘汰，此时是第 k 人。

不会转移。

最后一个小时再看 T1，依旧不会。

“反悔贪心”

这个东西在脑海中闪过了一瞬间，但是我没能够抓住它。

最后 10 分钟尝试给 T2 写一个状压卡时骗分，GDB 一直在并查集找父亲那报错。

调不出来了，按住 Ctrl+Z 不松手，终于在最后一分钟把原本的 72 分代码调出来了。

删掉 freopen 注释，电脑黑屏。

所有人都会 T1，多数人都会 T2。

还是……输了吗。

原来 T1 就是反悔贪心。

原来 T2 只用保留原生成树的 n-1 条边即可。

原来 T4 可以把最后一维改成对 c 的限制。

原来我是个傻逼。