noip2025游记

· · 生活·游记

这次到场感觉状态还行，没有很头晕之类的。

到场测了下速，取模 5\times 10^8 好像 3s，左右，不知道这个速度算快还是不快，直接认为 ccf 机子速度是这个的 2 倍。

赛前敲了个自动开文件 diff 的和一个对拍器，然后摆到了开考。

先开的 T1，看起来和之前做的 cf edu 上的贪心差不多，只不过那个是长度可能为 1 或 2 或 3，直接如果后两个 1 比 2 好就取一个 1，否则取一个 2，取不了 2 再取 1。

写了几分钟，在开考 15min 时过掉了所有大样例。

开 T2，发现这个过程和 T1 是相同的，发现不合法的情况只有类似于 121 然后取两个 1 不如取 2 且只剩下 2 的钱。然后考虑直接枚举类似的东西，也就是枚举第一个 1 的位置，2 的位置，和第二个 1 的位置，然后组合计数一下 O(n^3)。

写了 20min 发现没过大样例的第一个，即 n=5 的点，比较难办，静态调了 20+min 调不出来，于是写 O(2^n) 暴力跑一下，发现也是错的，说明不是 121 的东西，遂改写 O(4^n) 暴力打了一下错的东西的样子出来，发现可以是 12221 类东西，思考一下发现只要改改组合的式子就行了，可以通过一些大样例，然后第三个东西的分界位置可以双指针，于是就做到了 O(n^2)，测了下大样例都过了，此时过去 2h，感觉 T2 是个绿题，有点倒闭了。

开 T3，发现和图灵杯中级组 T3 很像，这玩意直接延后钦定就行了，但是我没写过 mex 延后钦定，怕调不出来，先打了个 O(3^nn) 暴力，写了挺久（30min 左右）。

看看 T4，发现是数据结构，似乎不太好做，直接想暴力，发现 O(tn+qn\log t) 预处理单调队列+区间 max 就已经可以拿 45 分了（t 是所有会被查询的长度的数量），但是发现好像不太好做这个区间 max，想了一亿年发现似乎 O(tn+qtn) 就可以拿 40 了，果断抛弃这 5 分直接写，在 3.5 h 左右过掉了所有大样例，感觉在这么基础的暴力上花 1h 还是太唐了。

回来看 T3，发现直接 O(n^3) 有 60 分，直接开写，发现不会转移，发现会 O(n^5) 转移，然后由于树上背包这是 O(n^4) 的，做一个前缀优化就是 O(n^3) 的了，那继续写，一遍过大样例，舒服了。离结束还有 30min，感觉不能获得更多的分了。

给每题看了看文件，然后给 T4 stl deque 换成了手写的，就结束了。

赛后发现 T3 O(n^3)，只有 48。查分 T3 挂了 8 分，原因是

int u[360][360][360],sz[360],u1[360][360];

怎么去年省选后每场 OI 赛制的比赛必有一个及其唐诗的错误。

最后是 100+100+40+40=280，没进队线。