NOIP 2024 游记

· · 生活·游记

DAY -1

不想上课，旷了一天，机房睡觉。

DAY 0

还是旷课。

上午还是比较疲惫，看了板子，想了会儿 NOIP 常考的树、图、dp，不想做题，继续睡觉。

欸？听说能中午回家，果断逃离学校，很闲，正好有时间去看初中老师。

跟老教练聊了很多，正好有社团课，被抓去教学弟学妹（也是被叫学长了。

看望了各科老师，还是很热情的。

晚上不想碰电脑，那就，打电动！

DAY 1

睡到被叫醒，好困，整理了一下，出发。

还是半小时前进了考场，然后坐着发呆。

开考了，发现vscode还是不会用，罢了。

T1是啥？字串？好像跟字串没啥关系，两两交换相当于重排，贪心匹配就行了，可以证明这样做就是最优的。 30min 过了大样例。

T2看了会儿，第一想法是dp，然后就沉浸在定义和推式子之中， 30min 后发现我一直在求 a,b,v 三者不同取值的方案数，然而题目让求 a,b 的方案数，简直错光了。换了思路，对相邻两已知数求之间 a,b 的方案数，发现答案之间互不干扰，相乘即可，一个容斥就对完了。共 1h 花费。

T3一看树型dp，推了式子，直接码 O(nk) ，发现只能过 k=1 的点，原来有算重复的，先想 k=2 的怎么做，发现好像跑第2条的时候把第1条标记一下，然后特殊计算一下就行了，然而事情好像并没有我想的那么简单，莽了 1h 好像出大事了，完全不对，只能开 T4 了。

T4第一感觉比T3简单，找祖先不就是找dfn序最大的且在点到根的路径上的点吗，先敲了个树剖把 O(n^2) 的搞定了，考虑优化，想到了主席树然而好像并没什么用，想莫队和分块的暴力，发现卡不过去，考虑链的部分，（有这么多部分分一看就是很接近正解了）然后就是一顿乱搞，但并没有搞出来。

剩 30min ，此时感觉我好像就只能打最基础的暴力分，好像每个人都能拿到，其他的性质啥的根本发现不了。虽然让自己冷静了下来，但并不能拿到后续的分数。

听大佬讲说T4链的部分可以二分，但我并没有想到，那就这样吧，跟今年 CSP-S 差不多，剩的时间总是挺多，但总是拿不到后面的分数，还是太菜了。

最终预计得分： 100+100+24+20=244 pts