B. Mainak and Interesting Sequence

思路：要想存在构造方法，则数组a中除了最大数外的其它数出现次数都必须是偶数

证明：假设数x出现了奇数次，令y为数组中恰好比x大的数，即y>x且不存在t，使得y>t>x，因为x不是最大数，因此这样的y一定存在。令P(y)为数组中小于y的所有数的异或值，则有题意可知P(y)=0，又因为0=P(y)=P(x)⊕x=0⊕x=x且x>0，因此矛盾，所以x必须出现偶数次

证完后就很容易构造答案了

代码：

void slove(){
   int n,m;
   cin>>n>>m;
   if(n>m){
    cout << "NO" << endl;
    return;
   }
   if(n&1){
    cout << "YES" << endl;
    _for(i,0,n-1)cout << 1 << " ";
    cout << m-n+1 << endl;
   }
   else{
    if(m&1)cout << "NO" << endl;
    else{
        cout << "YES" << endl;
        _for(i,0,n-2)cout << 1 << " ";
        int tem=(m-n+2)/2;
        cout << tem << " " << tem << endl;
    }
   }
}

D. Edge Split

思路： 如果不成环的话,那么每条边都会使连通分量数减去一,所以我们的目标是不让构造出的两个图里出现环.

首先我们构造出任意一个生成树把生成树边全部染成红色,然后最多剩下三条边,如果这些边没有成环直接输出答案即可.

如果成环,我们就把剩下的边里任选一条染成红色,其它保持蓝色，但是这样红色的图里就会有环了,我们还要删除红色图中的环.我们可以选择刚才这条边的任意一个端点,把与这个端点有关的所有边染成蓝色（除了环上刚被染成红色的边）.因为题目确认没有重边,所以染成蓝色的边一定不会生成新环.

其实只有恰好m=n+2的时候才会出现环

代码：

const int N = 200010;

int p[N];

int find(int x){
    if(p[x]!=x)p[x]=find(p[x]);
    return p[x];
}

void slove(){
   int n,m;
   cin>>n>>m;
   _fore(i,1,n)p[i]=i;
   int cnt[n+1];
   mm(cnt,0);
   int res[m];
   mm(res,0);
   vector<pair<int,int>> v;
   vector<int> vv;
   _for(i,0,m){
    int a,b;
    cin>>a>>b;
    v.pb({a,b});
    if(find(a)!=find(b)){
        p[find(a)]=find(b);
        res[i]=1;
    }
    else{
        cnt[a]++,cnt[b]++;
        vv.pb(i);
    }
   }
   int sum=0;
   _fore(i,1,n){
    if(cnt[i]==2)sum++;
   }
   if(sum==3){
    int tem=vv[0];
    res[tem]=1;
    int a=v[tem].first;
    _for(i,0,m){
        if(i==tem)continue;
        if(v[i].first==a||v[i].second==a){
            res[i]=0;
        }
    }
   }
   _for(i,0,m)cout << res[i];
   cout << endl;
}