NOIP-2024 游记暨北师大附中半日游

Day -？

顺利考完期中后又回到了停课的生涯，期中前的停课时间内我自我感觉进步还是挺大的，怎么说总之经历了许多波折之后又停上了课，进行了为期两周的集训时光。

这两周几乎是每天都在高强度中进行的，当感觉自己压力大的时候不妨听听音乐

晚上的时候高二学长 shs 和 wz 经常过来一起学习，同时有 NicoDafaGood 老师的讲解，我的水平正在迅速提升。

在 Day0 的下午，和 shs, zrj, 02Ljh vp了台中的一场 ICPC 。圆满完成。~~我是功臣~~

早上和 CSP 那天早上一样，妈妈做的意面和两个鸡蛋，很早来到北师大附中，路上用手机在 oiwiki 上复习了下 tarjan，优势在我。

在学校门口遇到了喝豆浆的 zrj，我俩就一块进入考场，期间还遇到了 lyt。

到了考场之后十分紧张，毕竟是从来没有到达的环境，打开显示器，输入 Linux 的密码之后下载试题，静待考试开始。

在考试之前观看了大样例，发现 edit 这道题好像是输入四个长度为 n 的 01 字符串，最后输出一个结果，后面三道题就不好说，没有什么特殊性值了。

美好的时光总是短暂的。

开始考试后，我旁边的一个小胖便开始极速的“砸击”键盘，这是没有夸张的，sbj 在他面前也只是不值一提。明明是静音的键盘却被他砸出安塞腰鼓的感觉。

也许是我习惯了 sbj 的敲击键盘的方式吧，他的行为并没有对我造成过多影响。

思考了 20 分钟后想出了 T1 正解。贪心的正确性我虽然没有证明出来，但是我的直觉告诉我这是对了，我便把这个思路打了出来。发现大样例跑得飞快，还过了，就火急火燎的去看 T2，这时候时间已经过去了 70 分钟。

接着 T2 的话一开始想到了一个 O(n) 的 DP，但是一看样例范围 n 有 1e9，果断放弃 DP 的想法，去想正解。

关注到由于答案求的是方案数，所以说一个位置只需要知道是否通过 c_i,d_i 确定了或者不确定即可，所以说 d_i 到底是多少根本就不重要。

观察到 m 只有 1e5 的数量级，因此考虑对每个确定的数之间进行统计，最后将所有数相乘起来即可。

分类讨论？

如果把确定的数用 1 来表示，不确定的数用 0 来表示的话，原数组就可以转化为一个形如 000100011....01000 的式子（就是将问题抽象化），之后考虑开始 00...01 和中间所有的 100...001 和最后的 10...000 部分即可。

时间复杂度 O(mlogn+mlogm)，跑得飞快。

但是这道题花费了我不少时间，我先是对着一个假思路调了半天，后面有对着没有 *(v-1) 的代码调了半天。我实在头开始发油的时候上了次厕所，吃了两块巧克力，不停的暗示自己能做出来这道题，回来之后便调出来了。

看一眼时间，四个半小时就剩下半个多小时了。

看一眼 T3，能拿 12 分，快拿！最后在还剩下十分钟的时候拿到了 12 分。

检查了输入输出，便提交了代码。优势在我！

问了学长和同龄人，好像都比我高？ /xd

身边的好多学长在考完 NOIP 之后都退役了，我也难免迎来退役的那天，但是我们终归有最好的路等待着我们去前行，加油吧少年！

最后用我的主页个性签名结束这篇游记：岁月因青春慨然以赴而更加美好，世间因少年挺身向前而更加瑰丽！

Ciallo～(∠・ω< )⌒★