【构造】CF1722G

╰半夏微凉° 2024-03-16 11:57 45阅读 0赞

[Problem - G - Codeforces][]

题意：

![c5ed1ae450694022a778b31201f3262d.png][]

思路：

关于异或的构造，可以通过改进一个位置来满足全局的条件

对于这道题，我们可以先构造一个0~N-1的排列，然后改最后一个位置的值来控制全局的异或和

直接令a\[N-1\]为前面的异或和即可

但是这样会导致一个问题：数列中元素有可能重复

具体地说，a\[N-1\]异或了之后，值可能比N-1小，这样就一定和前面某个数重复了

为了使a\[N-1\]一定不重复，可以让它或上(1<<20)

为了使得异或的条件满足，需要给前面某个数也或上(1<<20)

那么给a\[0\]或上(1<<20)

但是还需要特判一种情况，那就是当a\[N-1\]=0时，a\[N-1\]又会和a\[0\]重复，因此需要特判一下，如果a\[N-1\]=0，给a\[1\]或上(1<<20)即可

Code：

#include <bits./stdc++.h>
    
    using namespace std;
    
    const int mxn=2e5+10;
    const int mxe=2e5+10;
    
    int N;
    int a[mxn];
    
    void solve(){
        cin>>N;
        int sum=0;
        for(int i=0;i<N-1;i++){
            a[i]=i;
            sum^=i;
        }
        a[N-1]=sum;
        if(a[N-1]<N-1){
            if(a[N-1]==0){
                a[1]|=(1<<20);
            }else{
                a[0]|=(1<<20);
            }
            a[N-1]|=(1<<20);
        }
        for(int i=0;i<N;i++) cout<<a[i]<<" \n"[i==N-1];
    }
    int main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int T=1;
    	cin>>T;
    	while(T--)solve();
    	return 0;
    }

[Problem - G - Codeforces]: https://codeforces.com/contest/1722/problem/G
[c5ed1ae450694022a778b31201f3262d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/154464ff6a7b44ecaa9ddff1b3d74351.png