联合省选2026游记

· · 生活·游记

记录一下自己的唐氏操作：

选手在NOIP里距离队线20分，作为高二老登的选手有点慌。但是自信人生二百年，选手带着老子天下第一的心进入了考场。

D1T1

十分钟秒了，于是开始写正解，写着写着感觉是 O(n^3)，后面发现一个有序点对最多算一次，复杂度 O(n^2)，半个小时后通过了大样例，此时选手发现他应该拿出循环内的快速幂，但选手选择了先上厕所平复心情。

选手平复心情后回到座位，忘记了拿出快速幂这件事。

for(int v:e[u])if(v!=fa){
        // int res=power(dp[v][h[v]],p-2);
        for(int i=s-h[v];~i;--i){
            g[i]=f[u][i+h[v]];
            for(int j=1;j<=h[v];++j){
                g[i]-=g[i+j]*dp[v][h[v]-j]%p;
            }
            g[i]=(g[i]%p+p)%p*power(dp[v][h[v]],p-2)%p;
            // g[i]=(g[i]%p+p)%p*res%p;
            for(int j=1;j<=h[v];++j){
                dp[u][j+1]+=dp[v][j]*j%p*inv[i+j]%p*g[i]%p;
                ans+=dp[v][j]*i%p*g[i]%p*inv[i+j]%p*sz[v]%p;
            }
        }
        for(int i=s-h[v];~i;--i)g[i]=0;
    }

注释是修改内容，复杂度成功退化。

CCF青天老爷没有卡我，感谢老爷。

D1T2

读完题就会 O(nk^22^n) 了，紧接着发现状态数只有 n，于是优化到了 O(n^2k^2)，突然想到放KMP自动机上，于是优化到了 O(nk^2)，选手此时获得了 75pts。

紧接着，选手发现了选手的状态里的第三维只有 2\sqrt k，于是选手优化到了 O(nk\sqrt k)，吗？

选手以为自己稳了，于是看向了下一题。

赛后：

挂了15分，为什么呢？

for(sh i=0;i<=n;++i){
        ch[i][0]=ch[i][1]=fail[i]=ed[i]=0;
        add[i][0]=add[i][1]=adv[i]=0;
        for(sh j=0;j<=m;++j)for(sh k=0;k<=m;++k)vis[i][j][k][0]=vis[i][j][k][1]=0;
    }

选手清空打了 O(nk^2)，但是越界无任何错误。

选手挂了15分。

D1T3

选手 3h 获得了 16分。

出来有点破防，因为感觉 D1T2 是人均题。

出场，发现没几个会，似乎能win（此时不知道会挂）。

第一天考完

D2T1

什么CF风格题目，半小时秒了。

保险起见测了 10 以内全排列，果不其然通过了，选手不管了。

D2T2

什么神秘题目，选手思考十分钟，选手不会 n=8，选手润了。

D2T3

这是什么空集空集空集，选手认真读题，发现不需要管后代只需要管儿子，而这是一个树哈希算法。

于是可以建图 O(n) 求出定根大小关系，可以此时复杂度 O(n(n+m))。

选手思考了一下，发现用直径两端作为根可以得到所有树的情况，考虑到树哈希，可以用类似字符串哈希的算法进行比较大小，利用优先队列求出排名，同时可以使用权值线段树和主席树，利用启发式合并解决询问。

可以解决 o_x=0 的所有情况，结合随机数据暴力枚举长度应该可以获得 64 的高分。

选手开始写了。

选手写出10K代码后发现过不去第二个样例，此时十二点过。

选手发现以直径为根是错误的，选手紧急写了一个 O(\sum |Son|^2) 的建图，并改变策略只打随机的数据，12\sim 14 听天由命，但选手认为不会造菊花卡。

选手发现启发式合并需要改成换根。

选手修修补补写到了 一点一十三通过了 ox=0 的大样例。

选手很激动，选手忘记测菊花以至于忘写了菊花，选手忘记测 ox=1 的大样例了，选手以为自己是log^2能过，并没有意识到距离是根号而不是 Log，选手应该将数据结构换成分块才可以稳定通过。

选手选择了去写 D2T2 的 n=8。

D2T2

选手利用最后半小时写 n=8 失败了，考后才知道应该思考如何算答案。

选手出来稍微讨论了下，选手估分376.

day 5

出分了。

选手获得了353的分数，少了d1t2的15分和d2t3的8分，是为什么呢？

是因为选手唐啊。

幸好大概（可能）不影响选手进队，选手狗运。