2026牛客寒假营 第三场 补题笔记

I. BenzenE

Statement

$n \le 2\times 10^5$，给定数组 $a_i,b_i\in[0,2^{30})$，要求对每个 $i$ 选 $c_i=a_i$ 或 $b_i$ 使得 $c_1\oplus\cdots\oplus c_n=0$。无解时输出 $-1$ 。

Solution

异或线性基

Code

const int N = 1e5+100;
int n,a[N],b[N],c[N],ans[N];
bool use[N]={};
int p[32];
void solve(){
    cin>>n;
    for(int i=0;i<=31;i++)p[i]=0;
    int A=0;
    for(int i=0;i<=n;i++){
        use[i]=0;
    }
    for(int i=1;i<=n;i++){
        cin>>a[i];
        A^=a[i];
    }
    for(int i=1;i<=n;i++){
        cin>>b[i];
    }
    if(A==0){
        for(int i=1;i<=n;i++){
            cout<<a[i]<<" ";
        }
        cout<<'\n';
        return;
    }
    for(int i=1;i<=n;i++){
        c[i]=a[i]^b[i];
    }
    int cnt=0,idx[32]={},con[32]={};
    for(int i=1;i<=n;i++){
        int x=c[i];
        int cur=(1ll<<cnt);
        for(int d=31;d>=0;d--){
            if(x&(1ll<<d)){
                if(p[d]==0){
                    p[d]=x;
                    con[d]=cur;
                    idx[cnt++]=i;
                    break;
                }else{
                    x^=p[d];
                    cur^=con[d];
                }
            }
        }
    }
    int ans_con=0;
    for(int d=31;d>=0;d--){
        if(A&(1ll<<d)){
            if(!p[d]){
                cout<<-1<<'\n';
                return;
            }
            ans_con^=con[d];
            A^=p[d];
        }
    }
    for(int i=0;i<cnt;i++){
        if(ans_con&(1<<i)){
            use[idx[i]]=1;
        }
    }
    for(int i=1;i<=n;i++){
        if(use[i])cout<<b[i]<<" ";
        else cout<<a[i]<<" ";
    }
    cout<<'\n';
}

E. 躯树の墓守

Statement

构造一个 $n$ 点 $m$ 边、边权恰为 $1\sim m$ 且互不相同的简单连通无向图，使其最小生成树边权和恰好为 $k$。$1\le n\le 2\times 10^5,\ n-1\le m\le \min(2\times 10^5,\frac{n(n-1)}{2}),\ 1\le k\le 10^9$ 。

Solution

Code

const int N = 200005;
void solve(){
    cin>>n>>m>>k;
    int sum=0;
    for(int i=1;i<=n-1;i++){
        sum+=i;
        e[i]=i;
    }
    e[n]=1e9;
    for(int i=1;i<=n;i++){
        used[i]=0;
    }
    for(int i=1;i<=m;i++){
        in[i]=0;
    }
    if(sum>k){
        cout<<"NO"<<'\n';
        return;
    }
    int cur=n-1;
    while(sum<k){
        while(cur>0&&
            (e[cur]>=m||e[cur]==e[cur+1]-1||cur*(cur-1)<2*e[cur])
        )cur--;
        if(cur<=0){
            cout<<"NO"<<'\n';
            return;
        }
        e[cur]++;sum++;
    }
    for(int i=1;i<=n-1;i++){
        in[e[i]]=1;
    }
    int cnt=1,remain=0;
    vector<pair<int,int>> ans;
    auto add_edge=[&](int u,int v){
        ans.push_back({u,v});
    };
    int t=2;
    for(int i=1;i<=m;i++){
        if(in[i]){
            add_edge(1,++cnt);
            remain+=cnt-2;
        }else{
            if(!remain){
                cout<<"NO"<<'\n';
                return;
            }
            while(used[t]==t-2){
                if(t==cnt)t=2;else t++;
            }
            add_edge(t,used[t]+2);
            used[t]++;
            remain--;
        }
    }
    cout<<"YES"<<'\n';
    for(int i=0;i<m;i++){
        auto p=ans[i];
        cout<<p.first<<" "<<p.second<<" "<<i+1<<'\n';
    }
}