10.19 比赛总结

ooliver 发布于 13 小时前 118 次阅读 OI

AI 摘要

拖了很久的10.19比赛总结来了：四道题从环链判定、树上二分，到随机异或+启发式合并，再到“爆草”冲榜，既有思路拆解，也有挂十分的翻车复盘。想看哪道题怎么过？往下看。

有一段时间没写总结了，不能再拖了。。。

26 NOIP 二十连测 day1 | 正睿 OI

题目 #3681 | 正睿 OI

根据每个人最多连两条边可以知道，最后的连通块要么是环、要么是链，那就简单了。

但是挂了十分，原因是当一个连通块没有产生贡献时，就不需要再删边了。

代码：

C++
#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N=1e6+5;
int n,m,k,ans1,ans2;
vector<int> g[N];
int fa[N],siz[N],sum[N],tag[N];

int find(int x){
    while(x!=fa[x]) x=fa[x]=fa[fa[x]];
    return x;
}

signed main(){
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++) fa[i]=i,siz[i]=1;
    for(int i=1,u,v;i<=m;i++){
        cin>>u>>v;
        int fu=find(u),fv=find(v);
        if(fu==fv){
            sum[fu]++;
            continue;
        }
        if(siz[fu]<siz[fv]) swap(fu,fv);
        fa[fv]=fu,siz[fu]+=siz[fv],sum[fu]+=sum[fv]+1;
    }
    for(int i=1;i<=n;i++){
        int f=find(i);
        if(tag[f]) continue;
        tag[f]=1;
        if(sum[f]==siz[f]&&siz[f]==k){
            ans1+=k;
            continue;
        }
        ans1+=siz[f]/k*k;
        if(siz[f]/k*k) ans2+=(siz[f]+k-1)/k-1+(sum[f]==siz[f]);
    }
    cout<<ans1<<" "<<ans2;
    return 0;
}

题目 #3683 | 正睿 OI

对于 $A$ 中的一条边 $(u,v)$（$u$ 是 $v$ 的祖先），总能在 $B$ 中对应一条链 $L$，且 $L_1=u,L_n=v$。

若一个点在图 $A$ 中 $v$ 子树内，那就把它标记为 $1$，反之标记为 $0$，那我们相当于是要在 $L$ 上找到一个为 $1$ 一个为 $0$ 的相邻的两个点。由于 $L$ 的两端是满足一个为 $1$ 一个为 $0$ 的，所以可以直接二分，保证二分区间的两个端点一个为 $1$ 一个为 $0$ 即可。

代码：

C++
#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N=2e5+5;
int n,idx;
int dfn[N],siz[N],depa[N],dep[N],fa[N][20];
pair<int,int> e[N];
vector<int> a[N],b[N];
map<pair<int,int>,int> mp;

void dfsa(int u,int f){
    dfn[u]=++idx,siz[u]=1,depa[u]=depa[f]+1;
    for(auto v:a[u]){
        if(v==f) continue;
        dfsa(v,u);
        siz[u]+=siz[v];
    }
}

void dfsb(int u,int f){
    fa[u][0]=f,dep[u]=dep[f]+1;
    for(int i=1;i<20;i++) fa[u][i]=fa[fa[u][i-1]][i-1];
    for(auto v:b[u]){
        if(v==f) continue;
        dfsb(v,u);
    }
}

int getlca(int u,int v){
    if(dep[u]<dep[v]) swap(u,v);
    for(int i=19;i>=0;i--)
        if(dep[fa[u][i]]>=dep[v])
            u=fa[u][i];
    if(u==v) return u;
    for(int i=19;i>=0;i--)
        if(fa[u][i]!=fa[v][i])
            u=fa[u][i],v=fa[v][i];
    return fa[u][0];
}

int jump(int u,int v,int lca,int x){
    int d=dep[u]-dep[lca],len=dep[u]+dep[v]-dep[lca]*2;
    if(x<=d){
        for(int i=0;i<20;i++)
            if((x>>i)&1)
                u=fa[u][i];
        return u;
    }
    else{
        x=len-x;
        for(int i=0;i<20;i++)
            if((x>>i)&1)
                v=fa[v][i];
        return v;
    }
}

void solve(int u,int v){
    if(depa[u]>depa[v]) swap(u,v);
    int lca=getlca(u,v),len=dep[u]+dep[v]-dep[lca]*2;
    int l=0,r=len;
    while(l+1<r){
        int mid=(l+r)>>1;
        int p=jump(u,v,lca,mid);
        if(dfn[p]>=dfn[v]&&dfn[p]<dfn[v]+siz[v]) r=mid;
        else l=mid;
    }
    cout<<mp[{jump(u,v,lca,l),jump(u,v,lca,r)}]<<"\n";
}

signed main(){
    freopen("trees.in","r",stdin);
    freopen("trees.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1,u,v;i<n;i++){
        cin>>u>>v;
        e[i]={u,v};
        a[u].push_back(v);
        a[v].push_back(u);
    }
    for(int i=1,u,v;i<n;i++){
        cin>>u>>v;
        b[u].push_back(v);
        b[v].push_back(u);
        mp[{u,v}]=mp[{v,u}]=i;
    }
    dfsa(1,0);
    dfsb(1,0);
    for(int i=1;i<n;i++) solve(e[i].first,e[i].second);
    return 0;
}

题目 #3682 | 正睿 OI

考虑给每个连通块一个随机权值，并记录一个点在所有图中所属连通块的权值的异或和，并同时记录这个点在多少个图中是连了边的。

考虑当一个点新连边时，如果这个点在连边后刚好在 $k$ 张图上都连了边，那就把这个点的异或和权值记录到哈希表中并更新答案，因为哈希表内所有相同异或和权值的点两两都能产生贡献。

连边时启发式合并即可，这里每张图的并查集必须要用动态的内存，否则会爆炸。

代码：

C++
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;

const int N=5e5+5;
int n,k,q;
long long ans;
int cnt[N];
ull vis[N];
unordered_map<ull,int> mp;
mt19937_64 rnd(rand());

struct dsu{
    unordered_map<int,int> fa,siz;
    unordered_map<int,ull> w;
    unordered_map<int,vector<int>> d;
    void newd(int x){
        if(fa.count(x)) return;
        fa[x]=x,siz[x]=1,d[x].push_back(x);
    }
    int find(int x){
        while(x!=fa[x]) x=fa[x]=fa[fa[x]];
        return x;
    }
    void remove(ull wis){
        ans-=1ll*mp[wis]*(mp[wis]-1)/2;
        mp[wis]--;
        ans+=1ll*mp[wis]*(mp[wis]-1)/2;
    }
    void add(ull wis){
        ans-=1ll*mp[wis]*(mp[wis]-1)/2;
        mp[wis]++;
        ans+=1ll*mp[wis]*(mp[wis]-1)/2;
    }
    void merge(int x,int y){
        newd(x),newd(y);
        int fx=find(x),fy=find(y);
        if(fx==fy) return;
        if(siz[fx]>siz[fy]) swap(fx,fy),swap(x,y);
        if(siz[fy]==1){
            w[fy]=rnd(),fa[fx]=fy,siz[fy]+=siz[fx];
            d[fy].push_back(x);
            cnt[x]++,cnt[y]++;
            vis[x]^=w[fy],vis[y]^=w[fy];
            if(cnt[x]==k) add(vis[x]);
            if(cnt[y]==k) add(vis[y]);
        }
        else if(siz[fx]==1){
            fa[fx]=fy,siz[fy]+=siz[fx];
            d[fy].push_back(x);
            cnt[x]++,vis[x]^=w[fy];
            if(cnt[x]==k) add(vis[x]);
        }
        else{
            fa[fx]=fy,siz[fy]+=siz[fx];
            for(int i:d[fx]){
                d[fy].push_back(i);
                vis[i]^=w[fx]^w[fy];
                if(cnt[i]==k){
                    remove(vis[i]^w[fx]^w[fy]);
                    add(vis[i]);
                }
            }
        }
    }
}g[N];

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>k>>q;
    while(q--){
        int id,x,y;
        cin>>id>>x>>y;
        g[id].merge(x,y);
        cout<<ans<<"\n";
    }
    return 0;
}

题目 #3684 | 正睿 OI

受到题解的小点的处理方法的启发，尝试直接就这么草一下，结果草过去了，甚至榜上有名，故再次庆祝一下。

爆草代码：

C++
#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N=1e5+5,M=18;
int n,q,a[N],lg[N],mn[M][N],mx[M][N];
vector<int> p[N];
map<pair<int,int>,int> mp;

int qmn(int l,int r){
    int k=lg[r-l+1];
    return min(mn[k][l],mn[k][r-(1<<k)+1]);
}

int qmx(int l,int r){
    int k=lg[r-l+1];
    return max(mx[k][l],mx[k][r-(1<<k)+1]);
}

int getl(int x,int y,int z){
    int l=1,r=y,res=y;
    while(l<=r){
        int mid=(l+r)>>1;
        if(qmn(mid,y)>=x&&qmx(mid,y)<=z) res=mid,r=mid-1;
        else l=mid+1;
    }
    return res;
}

int getr(int x,int y,int z){
    int l=y,r=n,res=y;
    while(l<=r){
        int mid=(l+r)>>1;
        if(qmn(y,mid)>=x&&qmx(y,mid)<=z) res=mid,l=mid+1;
        else r=mid-1;
    }
    return res;
}

int solve(int x,int y){
    if(x>y||p[x].empty()||p[y].empty()) return 0;
    if(x==y){
        int ans=0;
        for(int i=0;i<(int)p[x].size();){
            int j=i;
            while(j+1<(int)p[x].size()&&p[x][j+1]==p[x][j]+1) j++;
            int len=j-i+1;
            ans+=len*(len+1)/2;
            i=j+1;
        }
        return ans;
    }
    int u=x,v=y;
    if(p[u].size()>p[v].size()) swap(u,v);
    int ans=0,lp=0;
    for(int i=0;i<(int)p[u].size();i++){
        int w=p[u][i];
        int l=getl(x,w,y),r=getr(x,w,y);
        l=max(l,lp+1);
        lp=w;
        if(l>w) continue;
        auto it=lower_bound(p[v].begin(),p[v].end(),w);
        int nv=(it!=p[v].end()?*it:n+1);
        int lv=(it!=p[v].begin()?*prev(it):0);
        int tot=(w-l+1)*(r-w+1);
        int a1=max(0ll,w-max(l,lv+1)+1);
        int a2=max(0ll,min(r,nv-1)-w+1);
        ans+=tot-a1*a2;
    }
    return ans;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>q;
    for(int i=2;i<=n;i++) lg[i]=lg[i/2]+1;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        p[a[i]].push_back(i);
        mn[0][i]=mx[0][i]=a[i];
    }
    for(int j=1;j<M;j++) for(int i=1;i+(1<<j)-1<=n;i++){
        mn[j][i]=min(mn[j-1][i],mn[j-1][i+(1<<(j-1))]);
        mx[j][i]=max(mx[j-1][i],mx[j-1][i+(1<<(j-1))]);
    }
    while(q--){
        int x,y;
        cin>>x>>y;
        if(mp.count({x,y})) cout<<mp[{x,y}]<<"\n";
        else{
            int r=solve(x,y);
            mp[{x,y}]=r;
            cout<<r<<"\n";
        }
    }
    return 0;
}