CF1722G Even-Odd XOR

· · 题解

CF1722G Even-Odd XOR

【题目大意】

给定整数 n，请你构造一个长为 n 且每个元素都是在 [0,2^{31}) 范围内的整数数列，满足：

若有多组解，你可以输出任意一组。

注意到题目的限制非常松，意味着可能各种各样的算法都能通过。于是我们不妨考虑随机化，对前 n-2 个位置的数随机赋 [0,2^{31}) 内的权值，赋值的同时记录奇数位置和偶数位置上的异或和，然后按照 n 的奇偶性把两个异或和分别放在 n-1 位置和 n 位置即可。

然后考虑数列中元素互不相同的限制，只需要用 map 记录某个数是否出现过即可。如果当前的权值已经出现过则重新随机一个权值。如果最后奇数位置和偶数位置的异或和相等，则考虑修改第 n-2 个数使异或和变得不等。如果异或和在原序列中出现过，则将两个异或和都异或上某个随机数即可。

由于数列长度只有 n，而值域远远大于 n，所以在赋值过程中出现冲突的概率很小，造成的额外计算也很少，所以时间复杂度约为 O(n) ，可以稳定通过。

// 这份代码并未考虑奇偶位上异或和相等的情况
// 具体实现与题解中略有不同
#include <bits/stdc++.h>
using namespace std;
unordered_map<int,int> mp;
const int mod=2147483647;
const int N=2e5+10;
int val[N];
int main(){
    mt19937 rnd(time(0));
    // 不建议使用 rand() 随机性较差
    // 值域也很小 远不能达到随机化的随机要求
    int t;cin>>t;
    while (t--){
        int n,val1=0,val2=0;cin>>n;
        mp.clear();
        for (int i=1;i<=n-2;i++){
            int x=rnd()%mod+1;
            while (mp[x]) x=rnd()%mod+1;
            val[i]=x;mp[x]=1;
            if (i&1) val1^=x;else val2^=x;
        }int t=0;
        while (mp[val1]||mp[val2]){
            t++;val1^=t;val2^=t;
        }
        if (n&1) val[n-1]=val2,val[n]=val1;
        else val[n-1]=val1,val[n]=val2;
        for (int i=1;i<=n;i++) cout<<val[i]<<' ';
        cout<<endl;
    }return 0;
}