NOIP2025 游寄

· · 生活·游记

Day0

前往 SY，打板子，摆摆摆。

Day1

进考场，T1 可以直接贪心做，30min 写完。

遍历题目，T2 是神秘计数，T3 感觉不可做，T4 数据结构。

旁边的人怎么开始敲键盘了？冷静下，先想 T2，转化了下变成用 x 个 1 或 2 和 y 个 0 或 1 凑出 m-2 的方案数。

直接组合数是 O(n^3) 的，但 dp 好像复杂度就对了？遂直接写。

由于要访问 m-2，于是特判了 m=1 的情况。(伏笔1)

由于双指针要访问 n+1，想起去年 noip T2 多测未清空，导致访问 n+1 挂了 10 pts，于是赶紧加上多册清空。(伏笔2)

写了一半发现 dp 复杂度假了，并且较为难写，于是直接重构换成组合数写法，O(n^3) 大样例跑了 0.4s，应该有 92 pts。

考虑优化，要推这样一个东西。

f(n,m)= \sum\limits_{i=0}^n \tbinom{n}{i} \tbinom{m}{w-n-i}

这我熟啊，考前刚做过 梦现时刻，似乎可以代数推导，但 noip T2 真的这么难吗？不管了，还剩 2.5h，我推推推推推。

然后直接似了，润去 T3。

到这里心态已经不对了，T3 只打了暴搜，T4想了个 O(qn^2)，能过 AB 性质，然后就结束了。

出考场询问群友 T2 推式子。

yeyou26：这不是范德蒙德卷积吗？

我：？

红温红温红温红温红温红温红温红温。

怎么晚上云斗直接出榜了？我草 T2 咋挂没了，场上大样例全过了啊？。

查了下是特判 m=1 直接跳过了多测清空，两年 noip T2 挂一个地方也是神人了。

期望：100+[32,92]+8+[30,40]=[170,240]

这下薛定谔的分数了。

[upd on 12.3] 没挂。