首页 > 代码库 > sgu To xor or not to xor

sgu To xor or not to xor

题意:从n个数中,选择一些数,使得异或最大。

 1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define ll __int64 5 using namespace std; 6  7 ll c[110][110]; 8 int n; 9 ll cc;10 11 void gauss()12 {13     int i,j;14     ll ans=0;15     for(int r=0; r<61; r++)16     {17         c[r][n]=1;18         for(i=0; i<r; i++)19         {20             for(j=0; j<n; j++)21             {22                 if(c[i][j])23                     break;24             }25             if(j<n&&c[r][j])26             {27                 for(; j<=n; j++)28                 {29                     c[r][j]^=c[i][j];30                 }31             }32         }33         for(i=0; i<n; i++)34         {35             if(c[r][i]) break;36         }37         if(i<n||(i==n&&!c[r][n]))38         {39             ans|=1ll<<(60-r);40         }41     }42     printf("%I64d\n",ans);43 }44 45 int main()46 {47     while(scanf("%d",&n)!=EOF)48     {49         for(int i=0; i<n; i++)50         {51             scanf("%I64d",&cc);52             for(int j=60; j>=0; j--)53             {54                 c[60-j][i]=(cc>>j)&1;55             }56         }57         gauss();58     }59     return 0;60 }
View Code