题解 小 Q 与异或
牛客练习赛? DIV1!
给你异或方程组的一些方程解,要求构造出异或方程组的全部解
性质一:
如果有两个方程右端点相同而解值不相同,则方程组不存在解
性质二:异或的逆元为其本身
利用性质二可通过x^y=z ->x^y^y逆=z^y逆 -> x=z^y逆 ->x=z^y解逆元方程
情况一:区间右端点相等但x值不相等 输出-1
情况二:异或逆元为0才能使异或方程成立 违反题目要求 输出-1
但情况二除非给你两组右端点差值为1且x值相同,否者是必定能构造出来的,因为x的范围为1e9,而答案数组的范围为2e10,所以在没有区间约束的情况下可以使用2^31和2^30左右横跳,无论给你什么x值因为小于目前的异或和,所以必定不会使异或逆元为0,即必定是存在解的
#include<stdio.h> #include<algorithm> #include<math.h> using namespace std; const int N=1e6+5; struct node { int r; int val; }e[1000005]; struct cmp { bool operator()(const node&t1,const node&t2) { if(t1.r!=t2.r) return t1.r<t2.r; return t1.val<t2.val; } }; long long ans[1000005]; int main() { long long che=pow(2,31); int n,m,flag=0,count=1; scanf("%d%d",&n,&m); for(int i=0;i<m;i++) { scanf("%d%d",&e[i].r,&e[i].val); } sort(e,e+m,cmp());//先排个序,按递增右端点性质通过递推处理区间 int old=0,arr=0,old2=0; long long bas;long long s=0;//bas 当前异或方程的解 s 异或方程的总异或和 for(int i=1;i<e[0].r;i++)//处理前边界 { bas=che; ans[arr++]=che; s^=che; old=i; old2=bas; if(count==1)//左右横跳填充 { count=0; che/=2; } else { count=1; che*=2; } } for(int i=0;i<m;i++) { int t=e[i].r; if(t==old&&old2==e[i].val) continue; else if(t==old&&old2!=e[i].val) { flag=1; break; } if(arr==0) { s=bas=ans[arr++]=e[i].val; if(bas==0)//处理第一位为0的情况 { flag=1; break; } } else { if(t-old>1)//左右横跳填充区间缝隙 { for(int j=0;j<t-old-1;j++) { bas=che; s^=bas; ans[arr++]=che; if(count==1) { count=0; che/=2; } else { count=1; che*=2; } // printf("%lld\n",bas); } bas=s^e[i].val; s=e[i].val; if(bas==0) { flag=1; break; } ans[arr++]=bas; } else { bas=s^e[i].val; s=e[i].val; if(bas==0) { flag=1; break; } ans[arr++]=bas; } } // printf("%lld\n",bas); old2=e[i].val; old=e[i].r; } if(flag==1) { printf("-1\n"); return 0; } for(int i=0;i<arr;i++) { printf("%lld ",ans[i]); } for(int i=arr;i<n;i++) //左右横跳填充右区间 { printf("%lld ",che); if(count==1) { count=0; che/=2; } else { count=1; che*=2; } } printf("\n"); } /* 5 4 1 5 2 4 3 15 4 62 5 3 1 2 2 6 2 4 5 3 3 4 3 4 4 6 6 3 5 4 5 4 5 4 6 1 3 0 */