NOIp 2025 游记

· · 生活·游记

做了下 t1。是不是选枚举有多少个选奇数次就做完了。10min 通过。

做 t2。这是人啊？我不会 t2？注意到范围是 5000，所以可能是 dp？先刻画贪心策略，什么时候错大概就是只需要考虑最后两个选上的 1 和没选上的 2？

好像可以同时枚举这俩，朴素算是 O(n^3)，做了一下，发现可以用范德蒙德啥的做到 O(n^2)。测了下过了。做了 1 个小时，心里慌得一匹。

做 t3。哇，不会 O(poly(n))。开 t4。

编 q=1 编了一万年之后，我发现可以分治。然后发现：

int f(int l,int r,int k){
    if(r-l+1<k)return 0;
    int mid=l+r>>1;
    return f(l,mid,k)+f(mid+1,r,k)+k;
}

运行量级不超过 1e5？可能是 O(n) 的？

然后胡了一个很变态的做法。按照以 2 为底的对数分成 \log 个块，预处理一下，散块重新跑分治，于是就写了 O(n\log^2 n+nq)。大样例 2.8s。

曾经有一个选手告诉过我，ST 表交换 开城 int st[20][maxn] 比 int st[maxn][20] 会快。改了一下，1.3s。感觉做的有点慢啊。润 t3。

思考了一下发现三次方十分简单。记录一下 mex 和用了几个数。感觉状态可以简省，写了一发过不了 tree3。然后发现是错了。紧急冲了个三方。

不挂的话应该是：100+100+48+100=348？