bzoj3105 新Nim游戏

题目大意：给定n堆火柴，第一二次取的时候可以取走任意堆，然后和普通的游戏一样，问怎样取能先手必胜，最小化第一次取的火柴数。

思路：第一次取走后，剩下的火柴中不存在一个子集异或和为0（用线性基判断这件事），贪心能取就取，总和减去剩下的就可以了。实现的时候我们是用别的数来异或当前为上为1的那个最大数，而不是反之。

#include
      
       #include
       
        #include
        
         #include
         
          #define maxnode 105#define LL long longusing namespace std;int a[maxnode]={
    0},ci[maxnode]={
    0},ins[50]={
    0};int main(){    int k,i,j,p;LL sum=0,ans=0;    scanf("%d",&k);    for (i=1;i<=k;++i) scanf("%d",&a[i]);    sort(a+1,a+k+1);    for (i=1;i<=k;++i) sum+=(ci[i]=a[i]);    for (i=k;i>=1;--i)    {        for (j=29;j>=0;--j)            if (a[i]&(1<
         
        
       
      

 

bzoj2460 元素

题目大意：给定n中矿石的编号和价值，求取出的矿石中不存在一个子集的编号异或和为0的最大价值。

思路：同上一题，贪心，不过这里是取异或和不为0的，还有一点：左移右移是int，这里的long long范围，所以要写成右移的形式。

#include
      
       #include
       
        #include
        
         #include
         
          #define maxnode 1005#define LL long long#define up 62using namespace std;struct use{    int val;LL id;}ai[maxnode]={
    0};int ins[maxnode]={
    0};int cmp(const use&x,const use &y){
    return x.val>y.val;}int main(){    int n,i,j,t,ans=0;scanf("%d",&n);    for (i=1;i<=n;++i) scanf("%I64d%d",&ai[i].id,&ai[i].val);    sort(ai+1,ai+n+1,cmp);    for (i=1;i<=n;++i)    {        for (j=up;j>=0;--j)            if ((ai[i].id>>j)&1)            {                if (!ins[j]){ins[j]=i;break;}                else ai[i].id^=ai[ins[j]].id;            }        if (ai[i].id) ans+=ai[i].val;    }    printf("%d\n",ans);}
         
        
       
      

 

bzoj2115 Xor（！！！）

题目大意：给定一张无向图，求从1～n的一条权值异或和最大的路径。

思路：每一种路径都可以看作是直接的路径和一些环的组合，所以我们可以找出所有的环（并不一定是所有的，但是要找出足够组合出所有环的小环，所以可以dfs，如果v访问过就是环，同时这个环的异或和就是disu^disv^vauv）。找到所有环和它们的权值后，要用线性基的方式，贪心算出答案。

#include
      
       #include
       
        #include
        
         #include
         
          #define maxm 50005#define maxe 200005#define LL long longusing namespace std;int point[maxm]={
    0},next[maxe]={
    0},en[maxe]={
    0},tot=0;LL dis[maxm]={
    0},va[maxe]={
    0},hu[maxe]={
    0},ins[maxe]={
    0};bool visit[maxm]={
    false};void add(int u,int v,LL vv){    next[++tot]=point[u];point[u]=tot;en[tot]=v;va[tot]=vv;    next[++tot]=point[v];point[v]=tot;en[tot]=u;va[tot]=vv;}void dfs(int u){    int i,j,v;visit[u]=true;    for (i=point[u];i;i=next[i]){        if (visit[v=en[i]]) hu[++hu[0]]=dis[u]^dis[v]^va[i];        else{dis[v]=dis[u]^va[i];dfs(v);}    }}void pre(){    int i,j,x;    for (i=1;i<=hu[0];++i){        for (j=60;j>=0;--j)            if ((hu[i]>>j)&1){                if (!ins[j]){ins[j]=i;break;}                else hu[i]^=hu[ins[j]];            }    }}int main(){    int n,m,i,j,u,v;LL vv,ans;    scanf("%d%d",&n,&m);    for (i=1;i<=m;++i){        scanf("%d%d%I64d",&u,&v,&vv);add(u,v,vv);    }dfs(1);pre();ans=dis[n];    for (i=60;i>=0;--i)        if (!((ans>>i)&1)&&ins[i]) ans^=hu[ins[i]];    printf("%I64d\n",ans);}
         
        
       
      

#include
      
       #include
       
        #include
        
         #include
         
          #define maxm 50005#define maxe 200005#define LL long longusing namespace std;int point[maxm]={
    0},next[maxe]={
    0},en[maxe]={
    0},tot=0;LL dis[maxm]={
    0},va[maxe]={
    0},hu[maxe]={
    0};bool visit[maxm]={
    false};void add(int u,int v,LL vv){    next[++tot]=point[u];point[u]=tot;en[tot]=v;va[tot]=vv;    next[++tot]=point[v];point[v]=tot;en[tot]=u;va[tot]=vv;}void dfs(int u){    int i,j,v;visit[u]=true;    for (i=point[u];i;i=next[i]){        if (visit[v=en[i]]) hu[++hu[0]]=dis[u]^dis[v]^va[i];        else{dis[v]=dis[u]^va[i];dfs(v);}    }}void pre(){    int i,j,x,st=1;    for (i=60;i>=0;--i){        for (x=0,j=st;j<=hu[0];++j)            if ((hu[j]>>i)&1){x=j;break;}        if (x){            for (j=1;j<=hu[0];++j)                if (j!=x&&((hu[j]>>i)&1)) hu[j]^=hu[x];            swap(hu[x],hu[st]);++st;        }    }}int main(){    int n,m,i,j,u,v;LL vv,ans;    scanf("%d%d",&n,&m);    for (i=1;i<=m;++i){        scanf("%d%d%lld",&u,&v,&vv);add(u,v,vv);    }dfs(1);pre();ans=dis[n];    for (i=hu[0];i;--i) ans=max(ans,ans^hu[i]);    printf("%lld\n",ans);}
         
        
       
      

 

bzoj2728 与非（！！！）

题目大意：定义一种新操作：A nand B(真值表如下：1 1 0;0 1 1;1 0 1;0 0 1)，问给定的n个数能通过这种运算得出[L,R]中的几个数。

思路：nand操作可以代替位运算所有操作，根据位运算的性质可以得到如果一些位置的01状态在每个数中都一样，那么这些位置运算后的状态对应一样（比如0010和1101从后数的1、3位一样，所以最后运算出来的1、3位要么x1x1要么x0x0），我们通过求出这些关联位置可以得到一组线性基（作为一组线性基的数，对于某一位，它们二进制上只有一个1），求关联位置的方法是一些位运算技巧：从高到低枚举没有出现过的二进制位，枚举每一个数x，如果这一位是1，就&x，如果是0，就&~x，这样最后是1的位置就是关联位置了。考虑计算[1~x]中能算出来的数的个数，用之前的线性基，数位dp，考虑这一位是0/1（但这一部分有一种比较好写的办法，如果当前的线性基i|已经选的<=x，给答案加上2^(tot-i)，表示这一个线性基不选，其他的有这么多种方案；然后选上这个线性基，再接着做）。

#include
      
       #include
       
        #include
        
         #include
         
          #define LL long long#define N 1005using namespace std;LL ai[N],ji[N];int tot=0;bool vi[N]={
    false};LL calc(LL x){    int i;LL ans=0,ci=0;    if (x==-1LL) return x;    for (i=1;i<=tot;++i)      if ((ci|ji[i])<=x){        ci|=ji[i];ans|=(1LL<<(tot-i));      }return ans;}int main(){    int n,i,j,k;LL l,r,now,cc;    scanf("%d%d%I64d%I64d",&n,&k,&l,&r);    for (i=1;i<=n;++i) scanf("%I64d",&ai[i]);    for (cc=(1LL<
          
           =0;--i){        if (vi[i]) continue;        for (now=cc,j=1;j<=n;++j){            if ((ai[j]>>i)&1LL) now&=ai[j];            else now&=~ai[j]&cc;        }ji[++tot]=now;        for (j=0;j<=i;++j)          if (now&(1LL<
          
         
        
       
      

 

bzoj4004 装备购买

题目大意：给定n个装备，每个装备有m个属性值（看做一个m维向量），选一些装备，如果一个装备能被已选的某些装备线性表出就不能选。问选最多装备的最小代价。

思路：可以贪心，所以就可以对m位用线性基做。（eps不能选的太小！！！）

#include
      
       #include
       
        #include
        
         #include
         
          #define N 505#define LD double#define eps 1e-5using namespace std;struct use{    LD m[N];int c;    bool operator<(const use&x)const{
    return c
          
           eps) return 1;    if (y-x>eps) return -1;    return 0;}int main(){    int n,m,i,j,q,ans=0,cnt=0;LD k;    scanf("%d%d",&n,&m);    for (i=1;i<=n;++i)      for (j=1;j<=m;++j) scanf("%lf",&ai[i].m[j]);    for (i=1;i<=n;++i) scanf("%d",&ai[i].c);    sort(ai+1,ai+n+1);    for (i=1;i<=n;++i){        for (j=m;j;--j){            if (cmp(ai[i].m[j],0.)==0) continue;            if (!vi[j]){vi[j]=i;break;}            else{                k=ai[i].m[j]/ai[vi[j]].m[j];                for (q=m;q;--q) ai[i].m[q]-=ai[vi[j]].m[q]*k;            }        }for (j=m;j;--j)          if (cmp(ai[i].m[j],0.)!=0) break;        if (j){++cnt;ans+=ai[i].c;}    }printf("%d %d\n",cnt,ans);}
          
         
        
       
      

 

bzoj4568 幸运数字

题目大意：给一棵树，求某条路径上的某些点权的异或和最大。

思路：倍增+线性基。倍增数组维护u向上2^i步的线性基，合并的时候暴力合并（因为线性基能表示出所有数，所以可以把一个线性基中的数看作所有数插入另一个）。查询的时候合并出链的线性基，贪心算答案。

#include
      
       #include
       
        #include
        
         #include
         
          #define N 20005#define up 16#define M 60#define LL long longusing namespace std;int point[N]={
    0},next[N<<1],en[N<<1],tot=0,fa[N][up],dep[N]={
    0};struct use{    LL nm[M];}xj[N][up],ci[2];LL ai[N];int in(){    char ch=getchar();int x=0;    while(ch<'0'||ch>'9') ch=getchar();    while(ch>='0'&&ch<='9'){        x=x*10+ch-'0';ch=getchar();    }return x;}LL lin(){    char ch=getchar();LL x=0LL;    while(ch<'0'||ch>'9') ch=getchar();    while(ch>='0'&&ch<='9'){        x=x*10LL+(LL)(ch-'0');ch=getchar();    }return x;}void add(int u,int v){    next[++tot]=point[u];point[u]=tot;en[tot]=v;    next[++tot]=point[v];point[v]=tot;en[tot]=u;}use merge(use x,use y){    int i,j;use a;a=x;    for (i=M-1;i>=0;--i){        if (!y.nm[i]) continue;        for (j=i;j>=0;--j){            if (!((y.nm[i]>>j)&1)) continue;            if (!a.nm[j]){a.nm[j]=y.nm[i];break;}            else y.nm[i]^=a.nm[j];        }    }return a;}void pre(int u,int ff){    int i,v;fa[u][0]=ff;dep[u]=dep[ff]+1;    for (i=M-1;i>=0;--i)        if ((ai[u]>>i)&1){xj[u][0].nm[i]=ai[u];break;}    for (i=1;i
          
           =0;--i)        if (!((ans>>i)&1)&&ci[0].nm[i]) ans^=ci[0].nm[i];    return ans;}LL geta(int u,int v){    int i;if (dep[u]
           
            =0;--i) if (dep[fa[u][i]]>=dep[v]){ ci[0]=merge(ci[0],xj[u][i]); u=fa[u][i]; } if (u==v){ ci[0]=merge(ci[0],xj[u][0]); return calc(); }for (i=up-1;i>=0;--i) if (fa[u][i]!=fa[v][i]){ ci[0]=merge(ci[0],xj[u][i]); ci[1]=merge(ci[1],xj[v][i]); u=fa[u][i];v=fa[v][i]; } ci[0]=merge(ci[0],xj[u][0]); ci[1]=merge(ci[1],xj[v][0]); u=fa[u][0]; ci[0]=merge(merge(ci[0],xj[u][0]),ci[1]); return calc();}int main(){ int n,m,i,u,v;n=in();m=in(); for (i=1;i<=n;++i) ai[i]=lin(); for (i=1;i
           
          
         
        
       
      

 

bzoj3569 DZY Loves Chinese II

题目大意：给定一张连通图，q个询问，每次删去k（k<=15）条边，问图是否连通。

思路：dfs出dfs树之后，如果树边和能覆盖这条树边的所有非树边同时删掉了，就是不连通。给非树边rand一个权值，树边的权值是所有覆盖它的非树边的权值的异或和，如果删掉边的权值中有一个子集异或和为0，就说明不连通（！！！）。

注意：给树边赋值的时候可以差分，一开始竟然暴力用每条非树边赋值。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define N 100005#define M 1000005#define up 31using namespace std;struct use{ int u,v,va,ir;}ed[M];int point[N],next[M],tot,ai[N],xj[up],bi[N]={ 0};bool vi[N]={ false};int in(){ char ch=getchar();int x=0; while(ch<'0'||ch>'9') ch=getchar(); while(ch>='0'&&ch<='9'){ x=x*10+ch-'0';ch=getchar(); }return x;}void add(int u,int v){ next[++tot]=point[u];point[u]=tot;ed[tot]=(use){u,v,0,0}; next[++tot]=point[v];point[v]=tot;ed[tot]=(use){v,u,0,0};}void dfs(int u){ int i,v;vi[u]=true; for (i=point[u];i;i=next[i]){ if (vi[v=ed[i].v]) continue; ed[i].ir=ed[i^1].ir=1; dfs(v); }}void pre(int u){ int i,v;vi[u]=true; for (i=point[u];i;i=next[i]){ if (vi[v=ed[i].v]) continue; pre(v); ed[i].va^=bi[v]; ed[i^1].va^=bi[v]; bi[u]^=bi[v]; }}bool judge(int x){ int i,j; memset(xj,0,sizeof(xj)); for (i=1;i<=x;++i){ for (j=up-1;j>=0;--j){ if (!((ai[i]>>j)&1)) continue; if (!xj[j]){xj[j]=ai[i];break;} ai[i]^=xj[j]; }if (!ai[i]) return true; }return false;}int main(){ int n,m,q,k,i,j,cnt=0,u,v;n=in();m=in(); for (tot=i=1;i<=m;++i){u=in();v=in();add(u,v);} q=in();dfs(1); for (i=2;i<=tot;i+=2) if (!ed[i].ir){ ed[i].va=ed[i^1].va=rand(); bi[ed[i].u]^=ed[i].va; bi[ed[i].v]^=ed[i].va; } memset(vi,false,sizeof(vi)); pre(1); for (i=1;i<=q;++i){ k=in(); for (j=1;j<=k;++j){ u=in()^cnt; ai[j]=ed[u<<1].va; }if (judge(k)) printf("Disconnected\n"); else{printf("Connected\n");++cnt;} }}
           
          
         
        
       
      

 

bzoj2844 albus就是要第一个出场

题目大意：求子集异或和不去重排序后，x这个数最早出现的下标。

思路：考虑求出每一位只有一个1的线性基共m个，有n个数，一共有2^n个异或和，2^m种异或和，每一种异或和中：对于那n-m个不作为线性基的数是可以随便取的，并且可以通过组合得到不同的异或和。所以每种异或和出现次数都是2^(n-m)（！！！）。这样就可以数位dp出<x的异或种数，*2^(n-m)+1就是答案了。

#include
      
       #include
       
        #include
        
         #include
         
          #define N 100005#define up 31#define p 10086using namespace std;int in(){    char ch=getchar();int x=0;    while(ch<'0'||ch>'9') ch=getchar();    while(ch>='0'&&ch<='9'){        x=x*10+ch-'0';ch=getchar();    }return x;}int ai[N],xj[up]={
    0},bi[up]={
    0};int mi(int x,int y){    int a=1;    for (;y;y>>=1){        if (y&1) a=a*x%p;        x=x*x%p;    }return a;}int main(){    int n,i,j,q,x,ans=0;n=in();    for (i=1;i<=n;++i){        ai[i]=in();        for (x=ai[i],j=up-1;j>=0;--j){            if (!((x>>j)&1)) continue;            if (!xj[j]){xj[j]=x;break;}            else x^=xj[j];        }    }for (i=up-1;i>=0;--i)        for (j=i-1;j>=0;--j)            if ((xj[i]>>j)&1) xj[i]^=xj[j];    q=in();    for (i=j=0;i
          
           =0;--i)        if (((q>>i)&1)&&xj[i]){            q^=xj[i];ans|=(1<