NOIP2024 & 退役记

XiaoLe_MC · 2024-11-30 23:08:37 · 生活·游记

11.29

在机房训练的最后一天

做了点儿彩色绿题，学了下 2-sat，打了会儿板子，把 D 盘收拾了一下，带走了所有东西。

默念：不考高精，不考大模拟……不考拉插……

11.30

高二了，退无可退

6.30 起床，吃的饺子。

8:00 赶到考场。同学已经在了，西工大附中还是很有牌面的，拉了个大横幅 ccf noip2024 考点。

8.25 左右进的考场，机况很好，键盘很屎，比 csp 好在左右有个挡板，不过地方贼小，胳膊都伸不开，演草纸没地方放，难受。

8.30 开题，浏览一遍，发现没有天天。

看 T1， WC 有点吓人。瞪了 10min 没思路。然后陆陆续续听见贼多敲键盘的声音，你们是不是都会了啊？！直接慌掉了。然后思路就有了。维护出来所有连续的 1 的段，然后对每个 1 段开桶，统计在这个段里对应的有多少 0,1。然后对每个点打上标记，看这个点属于哪一个段。然后一位一位遍历匹配，如果两个字符串的这个位置的所属段都有标记，并且对应桶里都有 1 或者都有 0，那就把 1 或 0 分别减掉 1，如果一个在段里一个不在，那就对标不在段里的那个字符。大样例直接放过去了。40min搞定。

我左边的那个哥们在吃手。

看 T2，发现没读懂题。然后翻了翻 T3T4，还是滚回来做T2吧。艰难的理解完题意之后，初步推断每一位上是不受任何影响的，我们称有一元关系的位置为关键位置，然后如果有两个相邻的关键位置那就 \times [v(v-1)+1 ]，没有的话就 \times v^2，测个大样例，被 129600 卡了。我们称两个最近关键位置之间形成的段为一段，那么这一段里的贡献并不是上述那样。尝试分解了一下 129600 的质因数，发现有一个 5 在里面，这个 5 肯定是加出来的，那么尝试使用 dp。考虑在这么一段里 dp，令 f_{i,1} 表示如果这个位置是关键点并且形成的段长为 i-1 的方案数，f_{0,i} 表示这个位置不是关键点并且段长为 i-1 并且段末端是关键位置的方案数，那么有：

矩阵快速幂优化即可。也是出了 129600。

我左边的那个哥们在吃手。

还有 1h，打了T4暴力，唐氏没想到预处理，然后 <=5000 的点没吃上。打了个 T3 骗分，似乎挂掉了。

不知为甚我的 dev 会在编译之后未响应一段时间，仅限暴力代码会这样。

然后再 “乌邦图” 里跑了，没问题，就填表打包了。