CSP-S2022游记&几句话题解

grass8cow · 2022-10-29 22:59:09 · 个人记录

摘要：/kel

游记：

DAY0

上了两节英语和一节语文。英语课中途去做核酸，做完了回来发现啥都听不懂了，乐。

然后和Eray和black_trees一起竞速打模板，win麻了，很快乐。

中午和同学一起小卖部买冰红茶，卖完了，买了甚么青梅绿茶?

然后发现三瓶里就我的冻成一块冰了。

尝试物理砸，砸完发现成了碎冰冰，更不可喝了。

下午继续打板子，涉及到图论后被black_trees薄纱了/kk

打板子打烦了，开始一起vp远古 ARC。AK了，很快乐。

晚上甚至还在做题，6。做了CF1149C和AGC028D，都挺好的题。

最后在床上巨大睡不着！还是太紧张了！

DAY1

睡到早上 9 点。

早上起来之后背了几首刚学的励志诗长精神。

然后来学校，打了边双，点双，割点，缩点的板子，感觉自己特别不会tarjan发明的东西。

当时就感觉今天要考图论？虽然最后并没有用到什么相关算法。

因为快乐带手机，所以趁 teacher 不在开了把 phigros 。垃圾手机，火球in 和 Another me 都只打了 90w 。

在校车上看以前参加集训的题，还是有一些忘了的（

反正就特别心虚，因为 CF+考前两场模拟赛都打得稀碎。

和康神互斥。大膜坤皇。

到考场之后面到了神 Mea！然后和 KOT 和 AK_OIer 都面了。哎，身在两校，相见是困难的事。和 KOT 和 毛嗑儿 合了影。大家可以猜猜我是哪个。

感觉这个七中教学楼和机房都薄纱成外啊。结果碰到键盘之后就流汗黄豆了，从键盘来讲成外强得多（

然后开题。今年密码好简单啊（ future2022吧我记得。UPD:经 Eray 提醒，是 belief2022 /jy

见到 T1 ，感觉特别懵，不是很会。这个选 4 个点感觉就要枚举 B,C 啊，但一时没想到怎么处理互不相同。

遂看 T2 。一眼鉴定为纯纯的水题，十多分钟写完了。回来看 T1 ，想了 5min ，发现维护前三大值就行了，也是十多分钟写完了。

这个时候已经过了差不多 1h 了？

开了 T3，题读了巨久，感觉题特啰嗦。

没什么思路啊。今年目标是 250+，然后看到暴力就有 60，还是挺开心的。

然后继续想，一开始想的是统计有没有点没出边，应该很好做。

想到要线段树分治，很激动，本来想直接冲的。深吸一口气冷静下来，发现并不能做。感觉这次虽然感冒了，但头脑很清醒，没有傻冲。

然后又想到根号分治，但还是不太能维护。

转而思考这个巨大严的限制有什么意义。突然脑中飘过了 PKUSC2022 的 D2T2。然后一下子就迸出来了 xor-hashing 这个词。

发现 4 个操作都巨好维护，5 min 就写完了。

这是还剩 2h ，选择了先拍 T1T2T3，发现 T3 不好造数据就没拍。拍完还剩 1h45min。

看 T4 ，发现就是个对标保卫王国的憨憨 ddp +倍增 题。

先打了个 k=1 。然后开始冲。

细节想烦了，体现在离路径长度为 2 的点本不需要统计的。于是写得巨长无比，但因为很紧张写得巨快。0.5h 3.7k 传说。

但是有屁用，调不出来啊，过不了样例 2 。

就瞪着代码一行一行看，看了很久。此时我心态已经爆炸了，感觉戴着口罩简直难以呼吸，就直接挂脖子上了。

然后整个人僵在那里，特别绝望。

发现了 3,4 个错吧，最憨的错还是有一个地方写了 swap(d[u],d[v]) 。

最后过了样例 2，然后一口气接着过了样例 3,4 ，一个个 找不到差异 冒出来，愉悦到了极点，简直是绝处逢生的快感。

此时只剩 10 min 了！把代码拉虚拟机上测了一圈，没有 CE 。

走出考场。发现自己呼吸急促，手脚都麻了，站都站不稳，走路一摇一摆。但是愉悦溢满了！

在校车上和 mzx 唱西海情歌，以及跟他学一些 中V 的歌。然后歌圣 xy 来了，还是他更会唱一些。

带着耳机看番，发现垃圾手机耗电太快了，想到还得坐地铁就没看了/kk。

美餐了一顿，9点才吃完回家。测了一通 Infoj 的数据，没挂，开心。

感觉今天这个分还是有点梦幻，运气爆棚了，把 NOIP 的 RP 用光了属于是！

终于把游记写完了！开始快乐看番捏！

题解：

T1

对于每一个点 u ，计算点权最大的三个点，满足 dis(u,v)\le k+1,dis(1,v)\le k+1 。

然后枚举 B,C ,3^2 枚举即可。复杂度 O(n^2) 。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
bool di[2510][2510];
int n,m,K;
int head[2510],to[20100],nxt[20100],c;
void add(int u,int v){
    to[++c]=v,nxt[c]=head[u],head[u]=c;
}
queue<int>q;
int d[2510];
ll a[2510];
int mx[2510][3];
int main(){
    freopen("holiday.in","r",stdin);
    freopen("holiday.out","w",stdout);
    scanf("%d%d%d",&n,&m,&K);
    for(int i=2;i<=n;i++)scanf("%lld",&a[i]);
    for(int i=1,u,v;i<=m;i++){
        scanf("%d%d",&u,&v);
        add(u,v),add(v,u); 
    }
    for(int s=1;s<=n;s++){
        memset(d,0,sizeof(d));
        d[s]=1;
        while(!q.empty())q.pop();
        q.push(s);
        while(!q.empty()){
            int u=q.front();
            q.pop();
            di[s][u]=1;
            if(d[u]-1==K+1)continue;
            for(int i=head[u];i;i=nxt[i])if(!d[to[i]])
                d[to[i]]=d[u]+1,q.push(to[i]);
        }
    }
    for(int i=2;i<=n;i++){
        for(int j=1;j<=n;j++)if(i!=j&&di[i][j]&&di[j][1]){
            for(int k=0;k<3;k++)if(a[j]>a[mx[i][k]]){
                for(int k2=2;k2>k;k2--)mx[i][k2]=mx[i][k2-1];
                mx[i][k]=j;break;
            }
        }
    }
    ll ans=0;
    for(int i=2;i<=n;i++)for(int j=i+1;j<=n;j++)if(di[i][j]){
        for(int k=0;k<3;k++)if(mx[i][k])
            for(int k2=0;k2<3;k2++)if(mx[j][k2]){
                int A=mx[i][k],B=i,C=j,D=mx[j][k2];
                if(A!=D&&A!=C&&B!=D)
                ans=max(ans,a[A]+a[B]+a[C]+a[D]);
            }
    }
    return printf("%lld",ans),0;
}

T2

RMQ ，计算区间正/负数最大/小值以及是否有 0 ，5^2 枚举即可，复杂度 O(n\log n)

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m,q;
ll a[2][101000];
const ll I=2e9,II=2e18;
struct qq{
    ll mi0,mi1,mx0,mx1;
    bool yk;
};
qq operator + (const qq &e,const qq &b){
    qq c;
    c.mi0=min(e.mi0,b.mi0);
    c.mi1=min(e.mi1,b.mi1);
    c.mx0=max(e.mx0,b.mx0);
    c.mx1=max(e.mx1,b.mx1);
    c.yk=e.yk|b.yk;
    return c;
}
struct SGT{
    qq t[401000];
    inline void build(int ty,int p,int l,int r){
        if(l==r){
            ll z=a[ty][l];
            t[p].yk=(z==0);
            if(z<0)t[p].mi0=t[p].mx0=z;
            else t[p].mi0=I,t[p].mx0=-I;
            if(z>0)t[p].mi1=t[p].mx1=z;
            else t[p].mi1=I,t[p].mx1=-I;
            return;
        }
        int mid=(l+r)>>1;
        build(ty,p<<1,l,mid),build(ty,p<<1|1,mid+1,r);
        t[p]=t[p<<1]+t[p<<1|1];
    }
    inline qq ask(int p,int l,int r,int x,int y){
        if(x<=l&&r<=y)return t[p];
        int mid=(l+r)>>1;
        if(y<=mid)return ask(p<<1,l,mid,x,y);
        if(x>mid)return ask(p<<1|1,mid+1,r,x,y);
        return ask(p<<1,l,mid,x,y)+ask(p<<1|1,mid+1,r,x,y);
    }
}T[2];
vector<ll>cl (qq e){
    vector<ll>b;
    if(e.yk)b.push_back(0);
    if(e.mi0!=I)b.push_back(e.mi0);
    if(e.mi1!=I)b.push_back(e.mi1);
    if(e.mx0!=-I)b.push_back(e.mx0);
    if(e.mx1!=-I)b.push_back(e.mx1);
    return b;
}
int main(){
    freopen("game.in","r",stdin);
    freopen("game.out","w",stdout);
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=n;i++)scanf("%lld",&a[0][i]);
    for(int i=1;i<=m;i++)scanf("%lld",&a[1][i]);
    T[0].build(0,1,1,n),T[1].build(1,1,1,m);
    for(int i=1,l1,r1,l2,r2;i<=q;i++){
        scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
        qq e=T[0].ask(1,1,n,l1,r1),b=T[1].ask(1,1,m,l2,r2);
        vector<ll>x,y;
        x=cl(e),y=cl(b);
        ll ans=-II;
        for(ll j:x){
            ll now=II;
            for(ll k:y)now=min(now,j*k);
            ans=max(ans,now);
        }
        printf("%lld\n",ans);
    }
    return 0;
} 

T3

xor-hashing 。

对每一个点随机赋一个值，维护所有边 (u,v) 的 a_u 异或和即可。

发现条件等价于边数为 n ，以及异或和为所有 a_i 的异或和。

发现操作不难维护，复杂度 O(n+m+q) 。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m,sz[500100],su[501000];
ll a[501000],ot[500100],on[501000];
ll bigrand(){int A=rand(),B=rand();return ((1ll*A)<<30)^(1ll*B);}
int main(){
    freopen("galaxy.in","r",stdin);
    freopen("galaxy.out","w",stdout);
    srand(time(0));
    scanf("%d%d",&n,&m);
    ll all=0;
    for(int i=1;i<=n;i++)a[i]=bigrand(),all^=a[i];
    int sum=m;ll al=0;
    for(int i=1,u,v;i<=m;i++){
        scanf("%d%d",&u,&v);
        al^=a[u],ot[v]^=a[u],on[v]^=a[u],sz[v]++,su[v]++;
    }
    int q;scanf("%d",&q);
    for(int i=1,op,x,y;i<=q;i++){
        scanf("%d%d",&op,&x);
        if(op==1){
            scanf("%d",&y);
            on[y]^=a[x],al^=a[x];
            su[y]--,sum--;
        }
        if(op==3){
            scanf("%d",&y);
            on[y]^=a[x],al^=a[x];
            su[y]++,sum++;
        }
        if(op==2){
            al^=on[x],on[x]=0;
            sum-=su[x],su[x]=0;
        }
        if(op==4){
            al^=on[x],on[x]=ot[x],al^=on[x];
            sum+=sz[x]-su[x],su[x]=sz[x];
        }
        if(sum==n&&all==al)printf("YES\n");
        else printf("NO\n");
    }
    return 0;
} 

T4

倍增，矩阵维护 dp ，套路题。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,Q,K;
ll a[201000];
vector<int>g[201000];
int f[201000][20],d[201000];
ll ds[201000];
void dfs(int x){
    for(int v:g[x])if(f[x][0]!=v){
        f[v][0]=x,d[v]=d[x]+1;
        ds[v]=ds[x]+a[v];
        for(int i=1;i<20;i++)f[v][i]=f[f[v][i-1]][i-1];
        dfs(v);
    }
}
int lca(int u,int v){
    if(d[u]<d[v])swap(u,v);int a=d[u]-d[v];
    for(int i=19;i>=0;i--)if((a>>i)&1)u=f[u][i];
    if(u==v)return u;
    for(int i=19;i>=0;i--)if(f[u][i]!=f[v][i])u=f[u][i],v=f[v][i];
    return f[u][0];
}
void pts16(){
    for(int u,v,i=1;i<=Q;i++){
        scanf("%d%d",&u,&v);int lc=lca(u,v);
        printf("%lld\n",ds[u]+ds[v]-ds[lc]-ds[f[lc][0]]);
    }
}
const ll I=1e18;
struct qq{
    ll a[3][3];
}w1[201000][20],w2[201000][20];
void cl(qq &x){
    for(int i=0;i<K;i++)for(int j=0;j<K;j++)x.a[i][j]=I;
}
qq mul(qq a,qq b){
    qq c;cl(c);
    for(int k=0;k<K;k++)for(int i=0;i<K;i++)for(int j=0;j<K;j++)
        c.a[i][j]=min(c.a[i][j],a.a[i][k]+b.a[k][j]);
    return c;
}
int id[201000][3][3];
ll val[201000][3][3];
ll wW[201000][3];
ll ex1(int x,int v,int d){
    if(id[x][d][0]!=v)return val[x][d][0];
    return val[x][d][1]; 
}
ll ex2(int x,int v1,int v2,int d){
    if(id[x][d][0]!=v1&&id[x][d][0]!=v2)return val[x][d][0];
    if(id[x][d][1]!=v1&&id[x][d][1]!=v2)return val[x][d][1];
    return val[x][d][2]; 
}
void dfs2(int x){
    val[x][0][0]=a[x],id[x][0][0]=x;
    for(int v:g[x])if(v!=f[x][0]){
        dfs2(v);
        for(int i=1;i<K;i++){
            ll os=val[v][i-1][0];
            for(int j=0;j<3;j++)if(!id[x][i][j]||os<val[x][i][j]){
                for(int k=2;k>j;k--)id[x][i][k]=id[x][i][k-1],val[x][i][k]=val[x][i][k-1];
                val[x][i][j]=os,id[x][i][j]=v;
                break;
            }
        }
    }
    if(f[x][0]){
        wW[x][1]=a[f[x][0]];
        wW[x][2]=ex1(f[x][0],x,1);
        if(f[x][1])wW[x][2]=min(wW[x][2],a[f[x][1]]);
    }
}
void dfs3(int x){
    for(int v:g[x])if(v!=f[x][0]){
        cl(w1[v][0]);
        for(int i=0;i<K;i++)for(int j=0;j<K;j++)if(i+j+1<=K)
        w1[v][0].a[i][j]=min(w1[v][0].a[i][j],ex1(x,v,j));
        for(int i=0;i+1<K;i++)w1[v][0].a[i][i+1]=0;
        w2[v][0]=w1[v][0];
        for(int i=1;i<20;i++)if(f[v][i])w1[v][i]=mul(w1[v][i-1],w1[f[v][i-1]][i-1]),w2[v][i]=mul(w2[f[v][i-1]][i-1],w2[v][i-1]);
        dfs3(v);
    }
}
void pts84(){
    dfs2(1);dfs3(1);
    for(int u,v,ee=1;ee<=Q;ee++){
        scanf("%d%d",&u,&v);
        if(d[u]<d[v])swap(u,v);
        int lc=lca(u,v);
        qq now;cl(now);now.a[0][0]=a[u];
        if(lc==v){
            int kb=d[u]-d[v]-1,o=u;
            for(int j=19;j>=0;j--)if((kb>>j)&1) 
                now=mul(now,w1[o][j]),o=f[o][j];
        }
        else{
            int o=u,kb=d[u]-d[lc]-1;
            for(int j=19;j>=0;j--)if((kb>>j)&1)
                now=mul(now,w1[o][j]),o=f[o][j];
            int ou=o;
            o=v,kb=d[v]-d[lc]-1;
            qq p2;bool az=0;
            for(int j=19;j>=0;j--)if((kb>>j)&1){
                if(!az)p2=w2[o][j],az=1;
                else p2=mul(w2[o][j],p2);
                o=f[o][j];
            }
            if(!az){
                cl(p2);
                for(int i=0;i<K;i++)p2.a[i][i]=0;
            }
            o=v,kb=d[v]-d[lc]-1;
            for(int j=19;j>=0;j--)if((kb>>j)&1)o=f[o][j];
            int ov=o;
            ll r[3]={a[lc],I,I};
            for(int i=1;i<K;i++)r[i]=min(ex2(lc,ou,ov,i),wW[lc][i]);
            qq ks;cl(ks);
            for(int i=0;i+1<K;i++)ks.a[i][i+1]=0;
            for(int i=0;i<K;i++)for(int j=0;j<K;j++)if(i+j+1<=K)
                ks.a[i][j]=min(ks.a[i][j],r[j]);
            now=mul(now,ks);
            now=mul(now,p2);
        }
        ll ans=I;
        for(int i=0;i<K;i++)ans=min(ans,now.a[0][i]);
        printf("%lld\n",ans+a[v]);
    }
}
int main(){
    freopen("transmit.in","r",stdin);
    freopen("transmit.out","w",stdout);
    scanf("%d%d%d",&n,&Q,&K);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    for(int u,v,i=1;i<n;i++){
        scanf("%d%d",&u,&v);
        g[u].push_back(v),g[v].push_back(u);
    }
    for(int i=1;i<=n;i++)for(int j=0;j<3;j++)for(int k=0;k<3;k++)val[i][j][k]=I;
    for(int i=1;i<=n;i++)for(int j=0;j<3;j++)wW[i][j]=I;
    ds[1]=a[1];dfs(1);
    if(K==1)pts16();
    else pts84();
    return 0;
}