许昌建网站的公司在哪条路,seo关键词排名优化教程,如果你想了解信息,班级网站如何去建设思路#xff1a;
#xff0c;则有#xff0c;也就是说只要知道A1就可以求任意A。由于A是升序排列#xff0c;所以对于任意#xff0c;二进制所包含1的最高位第k位来说#xff0c;表明与第k位相反#xff0c;要大一些#xff0c;所以它的第k位为1#xff0c;的第k位为… 思路
则有也就是说只要知道A1就可以求任意A。由于A是升序排列所以对于任意二进制所包含1的最高位第k位来说表明与第k位相反要大一些所以它的第k位为1的第k位为0例如Bi10对应的二进制数为1010最高位1就是第3位所以就能确定Ai1的第三位为1Ai的第三位为0类似这样操作就能找出A中很多确定的值不确定的位根据k去判断。为了方便计算我们的是要去预处理b的前缀异或,然后解出a1就能得出为了找到a1的某些确定值我们同样的去找bi最高位1为第k位然后记录s[i]的第k位的值因为要使a[i1]的第k位为1由于那么只要记录下si就能根据a1的值得到ai1的第k位为1而且若出现多次相同的最高位1前缀异或值必须相等否则矛盾输出-1。
对于未知位可以把这些未知位紧贴看成一个二进制数使此二进制的值为k-1就是所求字典序第k小的值。例如k3,a11x1x0,x代表未知将两个未知位紧贴xx,让它的值为2也就是二进制表示10就是字典序第三小的值所以a111100。
#includebits/stdc.h
using namespace std;
int s[1000005];
int a[1000005];//第i位上是否为1
int a1[1000005];//第i位上为1的前i-1位异或和
int main()
{int T;cinT;int h0;//最高位 while(T--){int n,k;cinnk;memset(a,0,sizeof(a));memset(a1,0,sizeof(a1));int flag1;int a230;//所包含的最高位不能超过30 for(int i1;in;i){int b;cinb;s[i1]s[i]^b;if(b0)continue;h0;while(b){h;b/2; }h-1;//相同最高位1的前缀异或值相同 if(a[h]((s[i]h)1)!a1[h]) flag0;if(!a[h])a2-1;a[h]1;a1[h](s[i]h)1; }if(flag0||(1a2)k)cout-1endl;else {int a110;k-1;int cnt0;//确定a1 for(int i0;i30;i){//根据最高位1的前缀异或确定a1的对应位的值。 if(a[i])a11|(a1[i]i);else{int m((kcnt)i)i;//未知位根据k的二进制数分配 a11|m;cnt;}}for(int i1;in;i){coutint(a11^s[i]) ;}coutendl; }}
}
