云南省建设学校网站,网页版微信无法登录,龙岩人自己的网站,wordpress3.9界面中文【acwing210 异或运算】
题意#xff1a;
给定你由N个整数构成的整数序列#xff0c;你可以从中选取一些#xff08;甚至一个#xff09;进行异或#xff08;XOR#xff09;运算#xff0c;问所有能得到的不同的结果中第k小的结果是多少。
题解#xff1a;
把所有数…【acwing210 异或运算】
题意
给定你由N个整数构成的整数序列你可以从中选取一些甚至一个进行异或XOR运算问所有能得到的不同的结果中第k小的结果是多少。
题解
把所有数插入线性基把k二进制分解然后把1对应的位置xor起来注意这样是从第0小0开始数需要特判0是否能够被xor出来insert失败可以的话需要–k。
代码 #includebits/stdc.h
#define reg register
using namespace std;
typedef long long ll;
const int MN60;
ll a[61],tmp[61];
bool flag;
void ins(ll x){for(reg int iMN;~i;i--)if(x(1lli))if(!a[i]){a[i]x;return;}else x^a[i];flagtrue;
}
bool check(ll x){for(reg int iMN;~i;i--)if(x(1lli))if(!a[i])return false;else x^a[i];return true;
}
ll qmax(ll res0){for(reg int iMN;~i;i--)resmax(res,res^a[i]);return res;
}
ll qmin(){if(flag)return 0;for(reg int i0;iMN;i)if(a[i])return a[i];
}
ll query(ll k){reg ll res0;reg int cnt0;k-flag;//flag1说明有0所以要求第k-1位 if(!k)return 0;//a[i]只有最高位为1for(reg int i0;iMN;i){for(int ji-1;~j;j--)if(a[i](1llj))a[i]^a[j];if(a[i])tmp[cnt]a[i]; }if(k(1llcnt))return -1;for(reg int i0;icnt;i)if(k(1lli))res^tmp[i];//把1对应的位置xor起来 return res;
}
int main(){int t;cint;for(int k1;kt;k){int n;ll x;printf(Case #%d:\n,k);scanf(%d,n);memset(a,0,sizeof(a));memset(tmp,0,sizeof(tmp));flag0;for(int i1;in;i)scanf(%lld,x),ins(x);int q;cinq;while(q--){cinx;printf(%lld\n,query(x));} }return 0;
}
