【整理】XOR：从陌生到头晕

 一：解决XOR常用的方法：

 在vjudge上面输入关键词xor，然后按照顺序刷了一些题。

然后大概悟出了一些的的套路：

  1.    常用的有贪心，主要是利用二进制的一些性质，即贪心最大值的尽量高位取1。
  2.    然后有前缀异或和，和普通前缀和一样，可以快速得到一段区间的异或和。
  3.    当然在一颗树里面也常用前缀异或和，得到根节点到每个节点的前缀异或和，然后，两个点的前缀异或和在异或，可以得到两个点之间路线的异或和。     因为LCA到根的公共部分可以抵消（感谢Lzh提醒）。
  4.    Trie树，可以快速在数组里找自己的最大异或。
  5.    这种题，当然少不了分块，随机应变吧。

                                 -------------------------------我是分界线-----------------------------------

题意：给出一棵树，在树上找出一条路径，使得路径伤的边的异或值最大。
思路：dfs得到根到节点的异或前缀和，然后把每个点的异或前缀和插入字典树中，就可以按套路，在字典树里找最大异或了。
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxm=200010;
const int maxn=3000000;
int Laxt[maxm],Next[maxm],To[maxm],val[maxm],cnt,Xor[maxm];//dfs
int ch[maxn][2],tot,ans,b[40],n;//trie
int q_pow(int a,int x){ int res=1;while(x){if(x&1) res*=a;x>>=1;a*=a;} return res;}
int read()
{
    int res=0; char c=getchar();
    for(;c>'9'||c<'0';c=getchar());
    for(;c<='9'&&c>='0';res=res*10+c-'0',c=getchar()) ;
    return res;
}
void init()
{
    memset(Laxt,0,sizeof(Laxt));
    memset(Xor,0,sizeof(Xor));
    memset(ch,0,sizeof(ch));
    cnt=tot=ans=0;
}
void add(int u,int v,int x)
{
    Next[++cnt]=Laxt[u];
    Laxt[u]=cnt;
    To[cnt]=v;
    val[cnt]=x;
}
void dfs(int u,int pre,int x)
{
    for(int i=Laxt[u];i;i=Next[i]){
        if(To[i]!=pre){
            Xor[To[i]]=x^val[i];
            dfs(To[i],u,Xor[To[i]]);
        }
    }
}
void insert(int x)
{
    int Now=0; 
    for(int i=0;i<=31;i++) { b[i]=x&1;x>>=1;}
    for(int i=31;i>=0;i--){
        if(!ch[Now][b[i]]) ch[Now][b[i]]=++tot;
        Now=ch[Now][b[i]];
    }
}
void find(int x)
{
    int Now=0,tmp=0;
    for(int i=0;i<=31;i++){ b[i]=x&1; x>>=1; }
    for(int i=31;i>=0;i--){
        if(ch[Now][b[i]^1]) Now=ch[Now][b[i]^1],tmp+=q_pow(2,i);
        else Now=ch[Now][b[i]];
    } ans=max(ans,tmp);
}
void build()
{
    for(int i=1;i<=n;i++) insert(Xor[i]);
    for(int i=1;i<=n;i++) find(Xor[i]);
}
int main()
{
    while(~scanf("%d",&n)){
        init();  int u,v,x;
        for(int i=1;i<n;i++){        
            u=read();v=read();x=read();    
            u++;v++;
            add(u,v,x); add(v,u,x);
        }
        dfs(1,0,0); build();
        printf("%d
",ans);
    } return 0;
}
View Code
 题意： 给定L，R。求L<=X1,X2,X3...<=R，使得X1^X2^X3...最大异或。
 思路： 可以选的数大于大于两个，先求最大的n，使得2^n<=R, 如果还可以异或一个，那么异或(2^n)-1就好了。(2^n)xor(2^n-1) =2^(n+1)-1。
       一定是最大的。比如2^=10000, n=4，10000 xor 01111 = 11111；不可能还有不这个大的了,毕竟n=4是上界； 当然只能选一个的时候，
       就选本身R就好了。当然，为了避免卡精度问题（比如CF就hack我了，mmp），pow函数最好比较一下，这里太懒，算了。
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int main()
{
    int a,b,ans,L,R;
    while(~scanf("%d%d",&L,&R)){
        if(L==R) printf("%d
",L);
        else {
            int a=log2(R);
            a=q_pow(2,a);
            printf("%d
",a+a-1);
        }
    } return 0;
}
View Code

  •     HDU 4825：Xor Sum  字典树

题意： 给出n个数a[]，然后给出m次问题，给出Y，求a[]里面的X，使得X xor Y最大。
思路： 如果找一个数的最大异或，当然我们需要从高位到低位(已转化为二进制)，尽可能不同。
      那么我们从高位到低位表示一个数X，并且存入字典树中，结尾节点记录X（不同的数结尾肯定不同）。
      对于询问，从高位到地位先尽可能从兄弟边走。
      这棵Trie树高度为32，复杂度在接受范围内。
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=3000010;
inline int read()
{
    int res=0;char x=getchar();while(x<'0'||x>'9') x=getchar();
    while(x>='0'&&x<='9'){ res=res*10+x-'0';x=getchar();}return res;
}
int q_pow(int a,int x){ int res=1;while(x){ if(x&1) res*=a; x>>=1; a=a*a;} return res; }
struct TREE
{
    int ch[maxn][2],cnt,num[maxn];
    void init() { memset(ch,0,sizeof(ch));cnt=0;}
    void insert(int s[],int val)
    {
        int Now=0;
        for(int i=31;i>=0;i--){
            if(!ch[Now][s[i]]) ch[Now][s[i]]=++cnt;
            Now=ch[Now][s[i]];
        }   num[Now]=val;
    }
    int query(int s[])
    {
        int Now=0;
        for(int i=31;i>=0;i--){
            if(ch[Now][s[i]^1]) Now=ch[Now][s[i]^1];
            else Now=ch[Now][s[i]];
        }   return num[Now];
    }
}Tree;
int main()
{
    int T,n,m,x,tx,a[32],Case=0;
    scanf("%d",&T);
    while(T--){
        printf("Case #%d:
",++Case);
        scanf("%d%d",&n,&m);
        Tree.init();
        for(int i=1;i<=n;i++){
             scanf("%d",&x);tx=x;
             for(int j=0;j<=31;j++) {
                 a[j]=x%2; x>>=1;
             } Tree.insert(a,tx);
        }
        for(int i=1;i<=m;i++) {
             scanf("%d",&x);
             for(int j=0;j<=31;j++) {
                 a[j]=x%2; x>>=1;
             } printf("%d
",Tree.query(a));
        } 
    }return 0;
}
View Code

          (和上一题差不多，就不说了)

题意：  给定数列a[],和m个询问 Q(L,R),回答每个询问中有多少对(L<=i<=j<=R) ，使得异或为k。
思路：  异或转化为前缀和处理。然后就差不多交给分块处理了。 分块的时候记录个数，记录区间信息，具体的代码里面去感受。
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define ll long long
using namespace std;
const int maxn=100010;
int a[maxn],pre[maxn],num[1<<20],n,m,k,sqrtn;
struct Query{
    int id,l,r;  ll ans;
}q[maxn];
bool cmp(const Query a,const Query b)
{
    if(a.l/sqrtn==b.l/sqrtn) return a.r<b.r;
    return a.l<b.l;
}
bool cmp2(const Query a,const Query b)
{
    return a.id<b.id;
}
int main()
{
     scanf("%d%d%d",&n,&m,&k);
     sqrtn=(int)sqrt(n);
     for(int i=1;i<=n;i++) {
          scanf("%d",&a[i]);
          pre[i]=pre[i-1]^a[i];
     }
     for(int i=0;i<m;i++){
         scanf("%d%d",&q[i].l,&q[i].r);
         q[i].id=i;
     }
     sort(q,q+m,cmp);
     int l=1,r=1;
     num[pre[1]]++;num[0]++;
     ll cur=(a[1]==k?1:0);
     for(int i=0;i<m;i++)
     {
        while(r<q[i].r){
            cur+=num[pre[r+1]^k];
            r++;
            num[pre[r]]++;
        }
        while(l<q[i].l){
            num[pre[l-1]]--;
            cur-=num[pre[l-1]^k];
            l++;
        }
        while(l>q[i].l){
            cur+=num[pre[l-2]^k];
            num[pre[l-2]]++;
            l--;
        }
        while(r>q[i].r){
            num[pre[r]]--;
            cur-=num[pre[r]^k];
            r--;
        }
        q[i].ans=cur;
     }
     sort(q,q+m,cmp2);
     for(int i=0;i<m;i++) printf("%lld
",q[i].ans);
     return 0;
}
View Code
题意：现在对对于这个题，求a<=X<=b，c<=Y<=d，使XxorY最大（不同位数最多）。 
思路：从高位向地位，能取不同则取不同。
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cmath>
using namespace std;
long long  a,b,c,d,x,y,t1,t2,ans;
int main()
{
    long long i,j,T;
    scanf("%lld",&T);
    while(T--){
        ans=x=y=0;
        scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
        for(i=62;i>=0;i--){
             t1=x+(1LL<<i);t2=y+(1LL<<i);
             if(t1<=b&&t2-1>=c) {
                    x=t1;ans+=(1LL<<i);
             }
             else if(t2<=d&&t1-1>=a){
                    y=t2;ans+=(1LL<<i);
             }
             else if(t1-1>=a&&t2-1>=c){
                    continue;
             }
             else if(t1<=b&&t2<=d){
                    x=t1;y=t2;
             }
        }
        printf("%lld
",ans);
    }
    return 0;
}
View Code
问题：  有2*n-1个袜子，叫你找出不能配对的那个袜子。
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
#include<memory.h>
using namespace std;
char s[10],c;
int main()
{
    int n;
    while(~scanf("%d
",&n)){
        for(int i=0;i<=7;i++) s[i]='';
        for(int i=1;i<2*n;i++){
            for(int j=0;j<8;j++){
                c=getchar();
                s[j]=s[j]^c;
            }
        }
        printf("%s",s);
    }
    return 0;
}
View Code

  • NBUT1615：XorXor 异或的性质

问题：求所有区间异或和的异或和。
思路：由于异或满足交换律，偶数次异或的数字可以怼掉。所以只需要求出每个数字是出现奇数次还是偶数次即可。
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    int T,n,i,x,ans;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n); ans=0;
        for(i=1;i<=n;i++){
            scanf("%d",&x);
            if((i*(n+1-i))&1) ans^=x;
        } printf("%d
",ans);
    } return 0;
}
View Code

  • CodrChef：Bear and Xor of Sums 

题意：问所有的区间和的异或和。
思路：和上一题不同，这里有加法。
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/hua-dong/p/8244954.html