NOIP2024 游记

· · 生活·游记

11.23 NFLSPC#7

NFLSPC 和 zifan 组队。今年没啥有意思的题目，体验也比较差，所以不写游记了。很期待明年 lexiyvv 的 NFLSPC。

11.25~11.28

模拟赛没有一场打的好的。周四最后一场，T3 想到笛卡尔树之后就是容易的，第 n 次被笛卡尔树爆了/kk

补题补的也不算多，感觉这段时间有点摆。

11.29

由于 D407 要用作考场（10^8 跑 700ms 的机器也能用？），所以我们暂时到 D601 训练。上午写了建造军营并 vp 了其他人 duel 的几个题（顺便推个好题：CF1098D Eels）。没有打板子，感觉几乎用不到，kmp 也已经搞明白了。

晚上看了一些组合数学和数论，学了 Johnson 和 SPFA，睡觉前水了一会 B 站。

11.30

由于考场就在我们学校，所以我睡到了 6:30，不过还是到的有点早。吃早饭的时候看了一下数论。

7:40 左右到达学校，在一楼排队，看到了很多同学。xzc 和 pmd 在讨论冬日绘版。8:00 不到就上楼了，我在 D405-31。

试机的时候喝了半杯水，于是索性把剩下半杯也喝完，重新接了一杯。打了快读快写，从下发文件里偷看到了题目名称，于是建了文件夹和四题的代码。剩下 20min 没事干，调了中文输入法，在四题的代码最后都写了一遍《做个文明中国人》的歌词。

8:25 下发了密码，但是解压会出错，只能看到 assign1.ans 的 4\n3\n0。于是监考老师先下发了 pdf，并宣布延时 3min。

先看 T1。糊了一个贪心，很快过了小样例，这时大样例还没下发。T2 感觉比 T1 简单，快写完的时候看到大样例有了，于是先测了 T1。诶我怎么错了这么多？感觉这场要寄。还好我错的中有一个小的数据，改了代码，但还是没过。

又写了一发，这回只错了第 10 个点。果断写了一个拍子，暴力是随机交换一百万次。拍的过程中过了 T2 的大样例。回来看 T1，发现挂在了第 85 个点上。这时已经 9:30 了。

仔细想了一下，感觉不能只记录 cnt，必须记录 1 的位置，于是开了两个 queue 维护，通过了大样例。已经过去了 1h30min。

突然感觉很想上厕所，快要憋不住了，于是看了 T3。很快就注意到了一个重要结论：一个点周围的所有边，一定连成一条链，于是会了 k=1。快速写完并过了样例 1 和 3。

然后思考为啥 k>1 不能直接 \times k，原因是会算重。套路地上了容斥，然后问题转化为，钦定一些边的度数为 2，求方案数。考虑这些边的端点构成的虚树，注意到如果一个点连出的某条边属于这个虚树，那么这条边一定是这个点周围的边连成的链的端点之一。到这里就差不多了，虚树一定是链形态的，然后树形 dp，把容斥系数写进 dp 里面就可以了。

40min 通过 T3 小样例，大样例有些报段错误，其它的能过。由于我不会开栈空间，所以写了 dfs 序倒序 dp，通过了其余的大样例。

剩下有 2h 多一点做 T4。T4 首先想到了区间 lca 的通用套路，于是树和链就没有区别了，只需要特判 k=1 即可。发现二分之后的判定可以主席树维护，但是复杂度是双 log，n\le 5\times 10^5，2s，感觉不像正解。50min 通过了大样例，最后一个样例跑了 4.9s，开 O2 2.9s。

目前 T4 只有 52pts，不过剩下的时间还比较多。还是和 CSP 一样选择了卡常而不是优化复杂度，于是 st 表改了线段树（因为访问次数很少），改了快读快写，写了树剖 lca，并用 \max dep_i 代替了 n 作为二分上界，以及一堆小优化，最终只从 2.9s 卡到了 2.7s。后来加上了特殊性质 B 的 12pts，也写了线段树。

最后 30min 也没啥可写的，写了一个可以自动计算代码字节数的程序，方便我结束前临时调错。重新测了四题的大样例，这次开了 -O2 -std=c++14 -static，没报 CE。还有一点时间，简单地记了一下 assign.cpp，方便破解压缩包。

结束之后发现很多人 T4 写的都是双 log，而且做法有很多，包括我写的二分+主席树、cdq 分治、dsu on tree、整体二分。pmd 写了单 log，他讲的做法还包含笛卡尔树。果然，又被笛卡尔树爆了，哈哈。

wmh 也通过了 T4，做法似乎和 pmd 差不多。这次的程序公示换了一种加密方法，szx 说不能像上次那样明文攻击了。唉，必须得等一段时间了。

下周一回归 whk，还有一周就是月考/fendou。