@xiaoziyao 2021-05-13T13:30:02.000000Z 字数 19948 阅读 1108

HNOI2021游记

考试总结

HNOI2021联合省选，A卷。

前言

由于本菜鸡在NOIP2020考出了 $90+100+30+45=265$ 的分数（虽然比很多人成绩低了不知道多少），在HN有一个好看的名次，所以格外看重这次把NOIP作为 $40\%$ 的联合省选，结果省选因为个人原因也没有太好看的分数，还是有一些遗憾的。。。

为什么省选不考字符串、数论和分块啊！！！

AFO了，希望中考大捷，也希望各位在OI这条路上可以走得更远！

4月10日 Day 1

$404$ 机房，和同学都分开了，有一种不祥的预感。

带了一大袋零食去考试，在考前写了个manacher与广义SAM练手，手感挺好。

一遍输对密码，有了一个好的开始！

T1：诶，这道题怎么和我之前做的一道题很像呀，要反悔贪心吗？

首先胡了一个找差值的贪心上去，然后样例都没过，原因是最大值可以变成最小值，所以构造了一组比较强的数据：

5 5
11 13 15 17 9
1 2 3 4 5

想了一下反悔贪心没有想到。

突然发现最终的答案一定会形成一个区间，而且区间长度最小，因此直接想到排序+尺取法，5min rush完了代码，再调了调细节，一遍过大样例。

#include<stdio.h>
#include<algorithm>
#define inf 1000000001
using namespace std;
const int maxn=1000005;
int n,m,ans;
int a[maxn],b[maxn],vis[maxn];
pair<int,int>c[maxn<<1];
inline int get(int x){
    return x>n? x-n:x;
}
int main(){
    freopen("card.in","r",stdin);
    freopen("card.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]),c[i].first=a[i],c[i].second=i;
    for(int i=1;i<=n;i++)
        scanf("%d",&b[i]),c[n+i].first=b[i],c[n+i].second=n+i;
    sort(c+1,c+1+2*n);
    int l=1,r=0,cnta=0,cnt=0;
    while(cnt<n||cnta<n-m){
        r++;
        if(c[r].second<=n)
            cnta++;
        if(vis[get(c[r].second)]==0)
            cnt++;
        vis[get(c[r].second)]++;
    }
    ans=c[r].first-c[l].first;
    while(l<2*n&&r<=2*n){
        if(c[l].second<=n)
            cnta--;
        vis[get(c[l].second)]--;
        if(vis[get(c[l].second)]==0)
            cnt--;
        l++;
        while(cnt<n||(r<=2*n&&cnta<n-m)){
            r++;
            if(c[r].second<=n)
                cnta++;
            if(vis[get(c[r].second)]==0)
                cnt++;
            vis[get(c[r].second)]++;
        }
        if(r>2*n)
            break;
        ans=min(ans,c[r].first-c[l].first);
    }
    printf("%d\n",ans);
    return 0;
}

花30min写了个指数级暴力，然后还写了个拍子拍上了，然后去厕所（

拍了几千组数据出了问题，发现是数据生成器写错了，改了一下就继续拍下去了。（最后拍了一两万组 $n=20$ 的数据）

T2：看了好久，感觉和做过的另一道题很像，然后发现并不可以这样做。

想了想差分之类能不能构造出一些特殊的地方，然后发现并不能。

然后想了一下高斯消元，发现是 $O((nm)^3)$ ，想了想能不能带状高斯消元优化，发现并不会写带状高斯消元，然后就放弃了。

想了想差分约束，发现加法不好做差分约束，想到了直接给某些数带上负号，也就是直接黑白染色黑色为正白色为负，然后坐了坐感觉要把黑色和白色放在一起，又rush了好久发现不能构建一个含有 $3$ 个未知量的不等式约束，然后就没想下去了。

考后补充：实际上可以直接把式子列出来，对一个整体进行差分约束，然后就做完了。

发现第一档部分分不会做，然后果断写第二档部分分。

第二档部分分想了好久，发现很简单：设第一行为 $x$ ，那么之后每一行都可以表示出来，然后可以约束 $x$ 取值范围，随便选一个数就好了。

第三档部分分想到了2-SAT：rush了一个2-SAT然后发现似乎不能约束某些 $2\times2$ 的方格至少有 $1$ ，然后就注释掉了。

考后juju说只需要建虚点就可以了。（我果然是图论废物）

#include<stdio.h>
#include<vector>
#define inf 10100000000
using namespace std;
const int maxn=305,maxt=maxn*maxn*2;
int T,n,m,e,ff,fff,ffff;
int a[maxn][maxn],b[maxn][maxn],c[maxn][maxn];
//int scc,all,top;
//int stk[maxt],vis[maxt],bel[maxt],p[4];
//vector<int>v[maxt],rv[maxt];
inline int getpos(int x,int y){
    return (x-1)*m+y;
}
/*inline void add(int x,int y){
    printf("ADD(%d,%d)\n",x,y);
    v[x].push_back(y),rv[y].push_back(x);
}
void dfs(int x){
    vis[x]=1;
    for(int i=0;i<v[x].size();i++)
        if(vis[v[x][i]]==0)
            dfs(v[x][i]);
    stk[++top]=x;
}
void rdfs(int x,int c){
    vis[x]=1,bel[x]=c;
    for(int i=0;i<rv[x].size();i++)
        if(vis[rv[x][i]]==0)
            rdfs(rv[x][i],c);
}*/
void dfs(int x,int y){
    if(x==1){
        if(y>n)
            x++,y=1;
        else{
            for(int i=0;i<=b[x][y]&&(y==1||i<=b[x][y-1]);i++){
                a[x][y]=i;
                dfs(x,y+1);
                if(ff)
                    return ;
            }
        }
    }
    if(y==1){
        if(x>n){
            int F=0;
            for(int i=2;i<=n;i++)
                for(int j=2;j<=m;j++){
                    a[i][j]=b[i-1][j-1]-a[i-1][j-1]-a[i][j-1]-a[i-1][j];
                    if(a[i][j]<0||a[i][j]>1000000){
                        F=1;
                        break;
                    }
                }
            if(F==0)
                ff=1;
            return ;
        }
        for(int i=0;i<=b[x][y]&&i<=b[x-1][y];i++){
            a[x][y]=i;
            dfs(x+1,y);
            if(ff)
                return ;
        }
    }
}
int main(){
    freopen("matrix.in","r",stdin);
    freopen("matrix.out","w",stdout);
    scanf("%d",&T);
    while(T--){
        int flg01=1,flag=0;
        ff=fff=ffff=0;
        scanf("%d%d",&n,&m);
        for(int i=1;i<n;i++)
            for(int j=1;j<m;j++){
                scanf("%d",&b[i][j]);
                flg01|=(b[i][j]==0||b[i][j]==1);
                fff|=(b[i][j]==0);
                ffff|=(b[i][j]==4000000);
            }
        if(fff){
            puts("YES");
            for(int i=1;i<=n;i++)
                for(int j=1;j<=m;j++)
                    printf("0%c",j==m? '\n':' ');
            continue;
        }
        if(ffff){
            puts("YES");
            for(int i=1;i<=n;i++)
                for(int j=1;j<=m;j++)
                    printf("1000000%c",j==m? '\n':' ');
            continue;
        }
        if(n==2){
            for(int i=1;i<m;i++)
                for(int j=1;j<n;j++)
                    c[i][j]=b[j][i];
            for(int i=1;i<m;i++)
                for(int j=1;j<n;j++)
                    b[i][j]=c[i][j];
            swap(n,m),flag=1;
        }
        if(m==2){
            int lst=0,minn=0,maxx=2000000;
            for(int i=1;i<n;i++){
                if(i&1){
                    minn=max(minn,b[i][1]-lst-2000000);
                    maxx=min(maxx,b[i][1]-lst);
                    lst=b[i][1]-lst;
//                  0<=b[i][1]-lst-x<=2e6
                }
                else{
                    minn=max(minn,lst-b[i][1]);
                    maxx=min(maxx,lst-b[i][1]+2000000);
                    lst=b[i][1]-lst;
//                  0<=b[i][1]-lst+x<=2e6
                }
            }
            if(minn>maxx){
                puts("NO");
                continue;
            }
            lst=minn;
            a[1][1]=lst/2,a[1][2]=lst-lst/2;
            for(int i=1;i<n;i++){
                lst=b[i][1]-lst;
                a[i+1][1]=lst/2,a[i+1][2]=lst-lst/2;
            }
        }
        else{
            dfs(1,1);
            if(ff==0){
                puts("NO");
                continue;
            }
        }
/*      if(flg01){
            int flg=0;
            for(int i=1;i<n;i++)
                for(int j=1;j<m;j++){
                    p[0]=getpos(i,j),p[1]=getpos(i+1,j);
                    p[2]=getpos(i,j+1),p[3]=getpos(i+1,j+1);
                    if(b[i][j]==0)
                        for(int k=0;k<=3;k++)
                            add(p[k]+n*m,p[k]);
                    else for(int k=0;k<=3;k++)
                            for(int c=0;c<=3;c++)
                                if(k!=c)
                                    add(p[k]+n*m,p[c]);
                }
            all=2*n*m;
            for(int i=1;i<=all;i++)
                if(vis[i]==0)
                    dfs(i);
            for(int i=1;i<=all;i++)
                vis[i]=0;
            for(int i=all;i>=1;i--)
                if(vis[stk[i]]==0)
                    rdfs(stk[i],++scc);
            for(int i=1;i<=n*m;i++)
                if(bel[i]==bel[n*m+i]){
                    flg=1;
                    break;
                }
            if(flg){
                puts("NO");
                continue;
            }
            puts("YES");
            for(int i=1;i<=n*m;i++)
                printf("%d%c",(bel[i]<bel[n*m+i]),i%m==0? '\n':' ');
            for(int i=1;i<=all;i++)
                vis[i]=bel[i]=0,v[i].clear();
            scc=e=top=0;
            continue;
        }*/
        if(flag){
            for(int i=1;i<=n;i++)
                for(int j=1;j<=m;j++)
                    c[j][i]=a[i][j];
            for(int i=1;i<=m;i++)
                for(int j=1;j<=n;j++)
                    a[i][j]=c[i][j];
            swap(n,m);
        }
        puts("YES");
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                printf("%d%c",a[i][j],j==m? '\n':' ');
    }
    return 0;
}

T3：考场上画了好久图，找了好久性质，硬生生一个性质都找不出来，发现自己图论能力过于单薄，吐了。

做T3的时候顺带把T1的拍子改成验证极限数据用时，发现几百组极限数据只有一组到了 $0.9s$ 。

//I ball ball you.
#include<stdio.h>
const int maxn=1005,maxm=200005;
int n,m,e,stp;
int xx[maxm],yy[maxm],ans[maxm],start[maxn],to[maxm],then[maxm],vis[maxn],ban[maxn];
inline void add(int x,int y){
    then[++e]=start[x],start[x]=e,to[e]=y;
}
int dfs(int x,int t,int stp){
    if(ban[x]==1)
        return 0;
    if(x==t)
        return 1;
    vis[x]=stp;
    for(int i=start[x];i;i=then[i]){
        int y=to[i];
        if(vis[y]!=stp&&dfs(y,t,stp))
            return 1;
    }
    return 0;
}
int f(int x){
    int res=0;
    for(int i=1;i<=x;i++)
        if(dfs(x,i,++stp)&&dfs(i,x,++stp))
            res++,ban[i]=1;
    for(int i=1;i<=n;i++)
        ban[i]=0;
    return res;
}
int calc(){
    int res=0;
    for(int i=1;i<=n;i++){
        int now=f(i);
        res+=now;
    }
    return res;
}
int main(){
    freopen("graph.in","r",stdin);
    freopen("graph.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
        scanf("%d%d",&xx[i],&yy[i]);
    ans[m]=n;
    for(int i=m;i>=1;i--){
        add(xx[i],yy[i]);
        ans[i-1]=calc();
    }
    for(int i=0;i<=m;i++)
        printf("%d%c",ans[i],i==m? '\n':' ');
    return 0;
}

回家后打了一下板子：

4月11日 Day 2

又带了一大袋零食去考场，一遍输对密码，针不戳。（这个时候珂怜的xzy没有发现这实际上是一个上午噩梦的开始）

T1：审了一下题，想了想能不能建自动机匹配，发现似乎做不到/dk，然后想了想倍增，没想到什么做法。

然后直接树分块！

在树上撒 $\sqrt{n}$ 个关键点，每个点与其祖先里的关键点距离为 $\sqrt{n}$ ，然后发现可以把询问的路径分成 $4$ 个散块和 $2$ 个整块，散块暴力跳（记得把 $lca$ 到另一端的路径反向，我因为反向调了一个多小时），整块可以预处理第 $i$ 个关键点跳到祖先关键点这一条链，从位置 $j$ 开始匹配能匹配到哪里，不难发现（我想了十几分钟）可以用并查集维护所有位置同时进行匹配，同样还要反过来做一遍。

具体地，可以把整块对应的链上权值序列当成一个普通的序列，与长度为m的串进行匹配，然后对于每个位置可以维护它在匹配的过程中到了哪一个位置，不难发现把相同的位置在匹配的过程中会不断合并，那么直接上并查集就好了。

时间复杂度为： $O(n\sqrt{n}+m\sqrt{n}\alpha(n)+q\sqrt{n})$ ，常数极大，大样例要跑 $4s$ 。

算了一下，林林总总花了 $3$ 个多小时刚T1吧，结果最后的成绩还是那么丢人/ll。

正解就是我首先排除的倍增/ll。

#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
const int maxc=50005,maxn=200005,maxm=maxn<<1,maxk=25,maxt=1005;
int n,m,c,e,Q,tot,S,qtot;
int p[maxc],w[maxn],start[maxn],to[maxm],then[maxm],dep[maxn],fore[maxn][maxk],ok[maxn],P[maxn],q[maxn],qq[maxn],keyfa[maxn],pos[maxn],res[maxt][maxc],f[maxc],size[maxc],nowans[maxc],flag[maxc],revres[maxt][maxc];
inline int cmp(int a,int b){
    return dep[a]>dep[b];
}
inline void add(int x,int y){
    then[++e]=start[x],start[x]=e,to[e]=y;
}
void dfs(int x,int last){
    fore[x][0]=last,dep[x]=dep[last]+1;
    for(int i=1;i<=20;i++)
        fore[x][i]=fore[fore[x][i-1]][i-1];
    for(int i=start[x];i;i=then[i]){
        int y=to[i];
        if(y==last)
            continue;
        dfs(y,x);
    }
}
int lca(int a,int b){
    if(dep[a]<dep[b])
        a+=b,b=a-b,a-=b;
    for(int i=20;i>=0;i--)
        if(dep[fore[a][i]]>=dep[b])
            a=fore[a][i];
    if(a==b)
        return a;
    for(int i=20;i>=0;i--)
        if(fore[a][i]!=fore[b][i])
            a=fore[a][i],b=fore[b][i];
    return fore[a][0];
}
void solve(int x,int last,int key){
    if(x!=1&&ok[x]){
        keyfa[x]=key;
        key=x;
    }
    for(int i=start[x];i;i=then[i]){
        int y=to[i];
        if(y==last)
            continue;
        solve(y,x,key);
    }
}
int cnt1,cnt2,cnt3;
int tmp1[maxn],tmp2[maxn],tmp3[maxn];
int query(int x,int y,int id){
    int z=lca(x,y);
    if(1ll*(dep[x]+dep[y]-2*dep[z]+1)*Q<=400000000){
        int RES=1;
        for(int j=x;j!=z;j=fore[j][0])
            if(RES<=c&&p[RES]==w[j]){
                RES++;
                if(RES>c)
                    return c;
            }
        qtot=0;
        for(int j=y;j!=z;j=fore[j][0])
            qq[++qtot]=j;
        qq[++qtot]=z;
        for(int j=qtot;j>=1;j--)
            if(RES<=c&&p[RES]==w[qq[j]]){
                RES++;
                if(RES>c)
                    return c;
            }
        return RES-1;
    }
    int RES=1;
    while(ok[x]==0&&x!=z){
        if(RES<=c&&p[RES]==w[x]){
            RES++;
            if(RES>c)
                return c;
        }
        if(id==1)
            printf("BF_x_up %d res=%d\n",x,RES);
        x=fore[x][0];
    }
    while(x>0&&dep[keyfa[x]]>=dep[z]){
        if(id==1)
            printf("sqrt_x %d res=%d\n",x,res[ok[x]][RES]);
        if(RES<=c){
            RES=res[ok[x]][RES];
            if(RES>c)
                return c;
        }
        x=keyfa[x];
    }
    while(x!=z){
        if(RES<=c&&p[RES]==w[x]){
            RES++;
            if(RES>c)
                return c;
        }
        if(id==1)
            printf("BF_x_to_z %d res=%d\n",x,RES);
        x=fore[x][0];
    }
    if(RES<=c&&p[RES]==w[z]){
        RES++;
        if(RES>c)
            return c;
    }
    if(id==1)
        printf("BF_z %d\n",z);
    cnt1=cnt2=cnt3=0;
    while(ok[y]==0&&y!=z)
        tmp1[++cnt1]=y,y=fore[y][0];
    while(y>0&&dep[keyfa[y]]>=dep[z])
        tmp2[++cnt2]=y,y=keyfa[y];
    while(y!=z)
        tmp3[++cnt3]=y,y=fore[y][0];
    for(int i=cnt3;i>=1;i--){
        if(id==1)
            printf("BF_z_to_y %d res=%d\n",tmp3[i],RES);
        if(RES<=c&&p[RES]==w[tmp3[i]]){
            RES++;
            if(RES>c)
                return c;
        }
    }
    for(int i=cnt2;i>=1;i--){
        if(id==1)
            printf("sqrt_y %d res=%d\n",tmp2[i],revres[ok[tmp2[i]]][RES]);
        if(RES<=c){
            RES=revres[ok[tmp2[i]]][RES];
            if(RES>c)
                return c;
        }
    }
    for(int i=cnt1;i>=1;i--){
        if(id==1)
            printf("BF_y_down %d res=%d\n",tmp1[i],RES);
        if(RES<=c&&p[RES]==w[tmp1[i]]){
            RES++;
            if(RES>c)
                return c;
        }
    }
    return RES-1;
}
int find(int x){
    return f[x]==x? x:f[x]=find(f[x]);
}
void merge(int a,int b){
    a=find(a),b=find(b);
    if(size[a]>size[b])
        a+=b,b=a-b,a-=b;
    f[a]=b,size[b]+=size[a];
}
int main(){
    freopen("gem.in","r",stdin);
    freopen("gem.out","w",stdout);
    scanf("%d%d%d",&n,&m,&c);
    for(int i=1;i<=c;i++)
        scanf("%d",&p[i]),pos[p[i]]=i;
    for(int i=1;i<=n;i++)
        scanf("%d",&w[i]),P[i]=i;
    for(int i=1;i<n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y),add(y,x);
    }
    dfs(1,0),sort(P+1,P+1+n,cmp);
    S=sqrt(n),ok[1]=++tot,q[tot]=1;
    if(n>1000)
        S=200;
    for(int i=1;i<=n;i++){
        int x=P[i],y=x,flg=ok[y];
        while(dep[x]-dep[y]<S&&flg==0)
            y=fore[y][0],flg|=(ok[y]);
        if(flg==0)
            ok[y]=++tot,q[tot]=y;
    }
    solve(1,0,1);
    for(int i=1;i<=tot;i++){
        int x=q[i];
        for(int j=1;j<=c;j++)
            f[j]=j,size[j]=1,nowans[j]=j,flag[j]=j;
        qtot=0;
        //nowans[startpos]=nowpos flag[nowpos]=find(all startpos)
        for(int j=x;j!=keyfa[x];j=fore[j][0]){
            qq[++qtot]=j;
            int now=pos[w[j]],fnow=find(flag[now]);
            if(fnow==0)
                continue;
            flag[nowans[fnow]]=0;
            nowans[fnow]++;
            if(nowans[fnow]>c)
                continue;
            int r=flag[nowans[fnow]];
            if(r==0)
                flag[nowans[fnow]]=fnow;
            else merge(fnow,r),flag[nowans[fnow]]=fnow;
        }
        for(int j=1;j<=c;j++){
            res[i][j]=nowans[find(j)];
//          printf("res[%d][%d]=%d\n",i,j,res[i][j]);
        }
        for(int j=1;j<=c;j++)
            f[j]=j,size[j]=1,nowans[j]=j,flag[j]=j;
        for(int k=qtot;k>=1;k--){
            int j=qq[k],now=pos[w[j]],fnow=find(flag[now]);
            if(fnow==0)
                continue;
            flag[nowans[fnow]]=0;
            nowans[fnow]++;
            if(nowans[fnow]>c)
                continue;
            int r=flag[nowans[fnow]];
            if(r==0)
                flag[nowans[fnow]]=fnow;
            else merge(fnow,r),flag[nowans[fnow]]=fnow;
        }
        for(int j=1;j<=c;j++){
            revres[i][j]=nowans[find(j)];
//          printf("revres[%d][%d]=%d\n",i,j,revres[i][j]);
        }
    }
    scanf("%d",&Q);
    for(int i=1;i<=Q;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        printf("%d\n",query(x,y,0));
    }
    return 0;
}

T2：由于在全力刚T1，因此T2只写了个爆搜，最后竟然还写挂了 $15pts$ ，丢人。

#include<stdio.h>
const int maxn=15;
int n,m,fir;
int a[maxn],used[maxn],p[maxn];
long long ans;
inline int max(int a,int b){
    return a>b? a:b;
}
void dfs(int x,int rk1,int sum,int val,int add){
    if(sum>m)
        return ;
    if(x>n){
        ans++;
        return ;
    }
    for(int i=1;i<=n;i++)
        if(used[i]==0){
            used[i]=1,p[x]=i;
            int v=val+(i>rk1),ad=max(add,v-a[i]);
            dfs(x+1,i,sum+ad,v,ad);
            used[i]=0;
        }
}
int main(){
    freopen("ranklist.in","r",stdin);
    freopen("ranklist.out","w",stdout);
    scanf("%d%d",&n,&m);
    a[0]=-1;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        if(a[i]>a[fir])
            fir=i;
    }
    dfs(1,fir,0,a[fir],0);
    printf("%lld\n",ans);
    return 0;
}

T3：写了个 $O(qn^2)$ 的丢人暴力走人/kk。

实际上可以直接上 $\text{bitset}$ 优化做到更优复杂度的，但是刚T1去了，就没加上去。

#include<stdio.h>
#include<vector>
using namespace std;
const int maxn=3005,maxm=maxn<<1,maxk=25;
int n,m,q,e,stp;
int start[maxn],to[maxm],then[maxm],fa[maxn],size[maxn],dep[maxn],g[maxn][maxn],vis[maxn],flg[maxn],fore[maxn][maxk];
inline void add(int x,int y){
    then[++e]=start[x],start[x]=e,to[e]=y;
}
void dfs(int x){
    size[x]=1,fore[x][0]=fa[x];
    for(int i=1;i<=20;i++)
        fore[x][i]=fore[fore[x][i-1]][i-1];
    for(int i=start[x];i;i=then[i]){
        int y=to[i];
        fa[y]=x,dep[y]=dep[x]+1;
        dfs(y),size[x]+=size[y];
    }
}
int lca(int a,int b){
    if(dep[a]<dep[b])
        swap(a,b);
    for(int i=20;i>=0;i--)
        if(dep[fore[a][i]]>=dep[b])
            a=fore[a][i];
    if(a==b)
        return a;
    for(int i=20;i>=0;i--)
        if(fore[a][i]!=fore[b][i])
            a=fore[a][i],b=fore[b][i];
    return fore[a][0];
}
void get(int x,int B){
    if(x==B)
        return ;
    vis[x]=stp;
    for(int i=start[x];i;i=then[i]){
        int y=to[i];
        if(vis[y]==stp)
            continue;
        get(y,B);
    }
}
int main(){
    freopen("dominator.in","r",stdin);
    freopen("dominator.out","w",stdout);
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
    }
    if(m==n-1)
        dfs(1);
    for(int i=1;i<=n;i++){
        stp++,get(1,i);
        for(int j=1;j<=n;j++)
            g[i][j]|=(vis[j]!=stp);
    }
    for(int i=1;i<=q;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        if(m==n-1){
            if(lca(x,y)!=fa[y])
                printf("%d\n",size[x]);
            else puts("0");
            continue;
        }
        int res=0;
        add(x,y);
        for(int j=1;j<=n;j++){
            stp++,get(1,j);
            for(int k=1;k<=n;k++)
                flg[k]|=((vis[k]!=stp)^g[j][k]);
        }
        for(int j=1;j<=n;j++)
            res+=flg[j],flg[j]=0;
        start[x]=then[e],e--;
        printf("%d\n",res);
    }
    return 0;
}

测了一下民间数据，只有 $100+30+20+80+45+30=305$ ，fst了60分，远低于人均水平/ll

orz民间数据吊打我的juju。

总结一下，还是考试的时候很多思路没有完全成型，或者被hack掉就直接开始写了，因此浪费了大量时间，也导致拿部分分的时间不够。

同样还因为我的思维还不够强，因此很多部分分都没有较成熟的思路，也因此fst。

最后这个难看的分数也或多或少和我最后几天的颓废没有良好的状态有关系吧。

「随风凋零的，是某人从未打算实现的空想，还是落入海面继续下沉的烟花」

不管怎么样，我们都有光明的未来！

附赠负数天数的做题记录：

3月17日 Day -23

做了一道有意思的交互题CF1364E X-OR。

复习树剖。人老了，以前15分钟的树剖已经要30分钟了。

把弦图mcs算法板子打了一遍过了两道板题：P3196 [HNOI2008]神奇的国度,P3852 [TJOI2007]小朋友

在u群问了noi2020翻修道路的中文题解，然后看不懂。

CF891C Envy：有意思的 $\text{MST}$ 题

3月18日 Day -22

中午划水的时候写了一个树上简单博弈P5801 [SEERC2019]Game on a Tree

复习树剖写了一道板题P4312 [COI2009] OTOCI，调了好久，然后就卡到最优解第一名了。

复习fhq-treap。虽然忘光了，打一遍就想起来了：P3369 【模板】普通平衡树,P6136 【模板】普通平衡树（数据加强版），然后做非模板题一道都做不出来。。。

3月19日 Day -21

UVA1711 Catering：上下界网络流水题

下午lk讲了博弈论，竟然自己做出一道题，《震惊！初三废物xzy竟然会做博弈论》AT3727 [ARC087C] Prefix-free Game。

CF142B Help General：打"General"

P6560 [SBCOI2020] 时光的流逝：博弈

P7419 「PMOI-2」参天大树：dp分类讨论题，有点意思

3月20日 Day -20

P4466 [国家集训队]和与积：做一道莫反来保持手感

$\sum_{i=1}^n\sum_{j=1}^{i-1}[\gcd(i,j)=1]\sum_{d=1}^{\lfloor\frac{n}{i}\rfloor}[i+j\mid d]$

$=\sum_{i=1}^{\sqrt{n}}\sum_{j=1}^{i-1}\lfloor\frac{\lfloor\frac{n}{i}\rfloor}{i+j}\rfloor\sum_{k\mid\gcd(i,j)}\mu(k)$

$=\sum_{k=1}^{\sqrt{n}}\mu(k)\sum_{i=1}^{\lfloor\frac{\sqrt{n}}{k}\rfloor}\sum_{j=1}^{i-1}\lfloor\frac{\lfloor\frac{n}{ik}\rfloor}{ik+jk}\rfloor$

$=\sum_{k=1}^{\sqrt{n}}\mu(k)\sum_{i=1}^{\lfloor\frac{\sqrt{n}}{k}\rfloor}\sum_{j=1}^{i-1}\lfloor\frac{\lfloor\frac{n}{ik^2}\rfloor}{i+j}\rfloor$

可以 $O(\sqrt{n}\log n)$ 枚举 $k,i$ ，然后整除分块枚举 $j$ 统计答案。

复杂度不会证。

3月21日 Day -19

P5544 [JSOI2016]炸弹攻击1：模拟退火，这么套路的题一点意思都没有

P4212 外太空旅行：随机化求最大团的无趣题

P5239 回忆京都：水题

P4930 [PA2013]Euler，欧拉函数+搜索，Solution！

3月22日 Day -18

日报挂上去了，但是@上了我的小号，非常尬。

P4424 [HNOI/AHOI2018]寻宝游戏：myy毒瘤题，蛮好玩的

3月23日 Day -17

P5292 [HNOI2019]校园旅行：myy毒瘤题Ⅱ，也是好玩的题目

P3344 [ZJOI2015]幻想乡 Wi-Fi 搭建计划：有点套路的结论题

日报改过来了耶！

达成成就：2天内大号小号均上洛谷日报

3月24日 Day -16

CF1188D Make Equal：有意思的思维题，好毒呀

AT2374 [AGC014B] Unplanned Queries：简单结论题

AT2363 [AGC012C] Tautonym Puzzle：有意思的构造题

P7446 [Ynoi2007] rfplca：lxl的毒瘤分块，写了好久，然后发现题解复杂度假了，调题目调到不想写博客了

终于绑定了SPOJ了，感谢NSObject的帮助！然后交了两道题：SP106 BINSTIRL - Binary Stirling Numbers,SP3734 PERIODNI - Periodni

3月25日&3月26日 Day -15&-14

第一次月考，划了两天水。

3月27日 Day -13

SP20173 DIVCNT2 - Counting Divisors (square)：老毒瘤题了，硬生生卡了好久空间。。。

写一下推柿子过程吧：

$\sum_{i=1}^n d(i^2)=\sum_{i=1}^n\prod_{j=1}^{s_i}(2k_{i,j}+1)\ \ \ \ \ \ \ \ \ \ (i=\prod_{j=1}^{s_i}p_{i,j}^{k_{i,j}})$

$=\sum_{i=1}^n\sum_{S\in\{i\mid1\leqslant i\leqslant k\}}2^{|S|}\prod_{j\in S}k_{i,j}$

$=\sum_{i=1}^n\sum_{j\mid i}\mu^2(j)=\sum_{i=1}^n(\sigma\cdot \mu^2)(i)$
然后可以用类似杜教筛的方法筛出

$\sigma$ 和

$\mu^2$ 的前

$10^8$ 项，然后写个整除分块，整除分块里求

$\sigma$ 和

$\mu^2$ 就用打出的表和

$O(\sqrt{n})$ 算法结合就好了。

$\sum_{i=1}^n\sigma(i)=\sum_{i=1}^n\lfloor\frac{n}{i}\rfloor$

$\sum_{i=1}^n\mu^2(i)=\sum_{i=1}^{\sqrt{n}}\mu(i)\lfloor\frac{n}{i^2}\rfloor$

复杂度是 $O(n^{\frac{2}{3}})$

CF568E Longest Increasing Subsequence：复杂dp题，有点套路呀

SP7001 VLATTICE - Visible Lattice Points：反演裸题

P6860 象棋与马：有意思的杜教筛

P6810 「MCOI-02」Convex Hull 凸包：反演裸题

CF1491F Magnets：有一点点意思的交互题

3月28日 Day -12

P5307 [COCI2019] Mobitel：改变枚举状态的经典题+整除分块

P3579 [POI2014]PAN-Solar Panels：整除分块水题

CF354C Vasya and Beautiful Arrays：直接暴力，发现暴力的复杂度为调和级数

P2135 方块消除=UVA10559 方块消除 Blocks：区间dp套路题（由于状态里有一些改变，所以也可以划分到费用提前里就很离谱）

复习了一下费用提前，然后要写的例题一直咕咕咕。

UVA11134 传说中的车 Fabled Rooks：经典贪心题，直接行列分开

CF616E Sum of Remainders：整除分块细节题

CF963B Destruction of a Tree：有意思的构造题

CF276D Little Girl and Maximum XOR：XOR性质题，直接贪心

P3496 [POI2010]GIL-Guilds：水题

CF475D CGCDSSQ：利用了 $\gcd$ 的性质的普通题

P4184 [USACO18JAN]Sprinklers P：基础dp优化，Solution

3月29日 Day -11

再次尝试调试SP1526 RSORTING - Ranklist Sorting，没有调出来

P7451 [THUSCH2017] 杜老师：dls/se，线性基套路题+结论题，Solution

划了一天水诶。。。

3月30日 Day -10

AT5697 [AGC041F] Histogram Rooks：笛卡尔树上背包dp+容斥套容斥的大毒瘤题，Solution

3月31日 Day -9

P5556 圣剑护符：一个线性基结论题

P5438 【XR-2】记忆：神仙推柿子题，不会分析复杂度

P6162 [Cnoi2020]四角链：熬夜把这道题做完了，是一个基础的第二类斯特林数组合意义题

4月1日 Day -8

初三弱鸡终于开始停课了！感动！

P2495 [SDOI2011]消耗战：复习了虚树板子题

P5680 [GZOI2017]共享单车：虚树基础题，感觉两个算法硬生生拼凑在一起特别没有美感

CF1320E Treeland and Viruses：虚树上dp

CF571A Lengthening Sticks：小学奥数题

P6298 齿轮：基础容斥

hh讲了ds，然后越讲越偏，越讲越偏。。。

P6965 [NEERC2016]Binary Code：trie树优化建图细节sb题，调不出来

4月2日 Day -7

CF424C Magic Formulas：改变顺序，然后直接暴力

P3293 [SCOI2016]美味：01trie板子题调了亿个小时

P4592 [TJOI2018]异或：套路题，直接类似主席树一样差分

P6018 [Ynoi2010] Fusion tree：Ynoi/se，其实就是01trie交换子树的小trick

P6031 CF1278F Cards 加强版：推柿子sb题，只觉得非常精神污染，Solution，顺便水了个弱化版CF1278F Cards

P2480 [SDOI2010]古代猪文：同余类数学综合题，复习了一下一些数学

4月3日 Day -6

P5298 [PKUWC2018]Minimax：线段树合并优化dp，利用线段树合并的性质

P5327 [ZJOI2019]语言：ZJOI神仙题/se，利用一个结论然后直接上线段树合并

P6773 [NOI2020] 命运：打同步赛的时候没写/kk，其实是一道线段树合并优化dp好题，Solution

P5903 【模板】树上 k 级祖先：长剖板子

CF1009F Dominant Indices：dsu on tree板子

CF715C Digit Tree：dsu on tree有意思的题，Solution

P5904 [POI2014]HOT-Hotels 加强版：长剖优化dp

4月4日 Day -5

P5113 Sabbat of the witch：屑分块题，快爬，调不出来

猛的发现博弈论还没复习，赶紧搞一下博弈论。

AT3939 [ARC091D] Strange Nim：博弈论+根号分治好题

CF1147C Thanos Nim：有点意思的猜不变量博弈论

CF15C Industrial Nim：博弈论+结论题

$\oplus_{i=0}^{i-1}=\begin{cases}x&x\equiv 0\pmod 4\\1&x\equiv1\pmod4\\x+1&x\equiv2\pmod4\\0&x\equiv3\pmod 4\end{cases}$

P4643 [国家集训队]阿狸和桃子的游戏：有意思的思维题，把边权转化为点权

CF36D New Game with a Chess Piece：分类讨论博弈论（双倍经验SP7602 CF36D - New Game with a Chess Piece）

打愚人节比赛！

T171038 温故而知新：不会有人不会百度bv转av吧，不会吧？不会吧？

T173329 A+B Problem：看到A+B，直接粘P1601 A+B Problem（高精）的代码，直觉发现不要换行

T173878 买书送团队：做了好久的狗屎题，一开始直接上直线解析式，最后问了ykw才发现这是分段函数

T173049 驹草盛开的万年积雪：首先让hzr听出几个地方，然后直接调整一下就过了，据hzr说在这之后就单曲循环这首歌停不下来了（

T173046 风神的神德：首先把图片down下来，然后改成zip，然后再瞎搞一下就发现了T124363 风神的神德，然后由于私人题目可以看到错误信息，所以可以试出答案，再看回来，发现两题空间限制不同，一个32M一个16M，由于洛谷设置空间会直接四舍五入，所以可以猜测输出31.25%（考场没想到）

UVA1482 Playing With Stones：结论题

P2575 高手过招：阶梯博弈

P3480 [POI2009]KAM-Pebbles：阶梯博弈

P4279 [SHOI2008]小约翰的游戏：Anti-SG，直接上结论（双倍经验：UVA1566 John）

AT2307 [AGC010F] Tree Game：就是个树上dp，似乎以前做过？

CF1221E Game With String：分类讨论好题

CF388C Fox and Card Game：基础博弈论

4月5日 Day -4

P5305 [GXOI/GZOI2019]旧词：好玩的树剖，其实就是P4211 [LNOI2014]LCA的加强版

P6374 「StOI-1」树上询问：LCA简单题

CF1498E Two Houses：竞赛图水题

SP9507 MARIO2 - Mario and Mushrooms：Raney引理板子题，Solution

CF1498A GCD Sum：简单题

CF1498F Christmas Game：有意思的阶梯博弈+换根dp

P1495 【模板】中国剩余定理(CRT)/曹冲养猪：CRT板子题

P4720 【模板】扩展卢卡斯：exLucas板子题，调了好久

P3846 [TJOI2007] 可爱的质数/【模板】BSGS：BSGS板子题

P4884 多少个1？：BSGS+简单转换

P2183 [国家集训队]礼物：exLucas板子题

P4861 按钮：BSGS板子题

打月赛！

P7478 StickSuger：不会有人不会做T1吧？不会吧？不会吧？直接贪就对了！

P7479 至曾是英雄的您：真的有绿题的必要吗？直接搜每个空位置的连通块就好了。

P7480 Reboot from Blue：难度骤增，不会做，爬了。。。

首先想到一个dp思路，但是不难发现还可以倒着走一段距离加油然后再去终点。

然后考虑了这一点之后又发现可以反复横跳，但是不难发现转移是从油价高到油价低的，因此直接 $O(n^2)$ dp。（这是考场思路）

看到绝对值不会优化了，其实很简单，只需要用 $\text{set}$ 存下dp值直接转移就好了。

P7481 梦现时刻：不想做的狗屎题，考场思路：固定 $a$ ，发现给 $F(a,b)$ 每一项配上 $x^i$ 次方的式子可以通过卷积得到： $(\sum_k\frac{x^k}{k!})(\sum_{k}\frac{(n-a)^{\underline i}x^k}{k})$ ，然后直接上NTT。