生活随笔
收集整理的這篇文章主要介紹了
【 hdu3949 XOR】
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
從n個數(shù)中任選m(m>=1)個數(shù)異或起來，求所有可能的異或和的第k小值。
用到了0能不能被異或出來的問題。如果線性基的大小和原數(shù)組一樣,0是不能被異或出來的,否則可以。
在求k小值的時候要注意
?
#include<bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <cstdio>
#include <stdlib.h>
#include <ctime>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int maxn = 1e6 + 5;
using namespace std;
ll a[10005],m;
ll p[10005];
bool flag;
int cnt=0;
void init()
{memset(a,0,sizeof(a));memset(p,0,sizeof(p));cnt=0;flag=false;
}
void build(ll p)
{for(int x=62;x>=0;--x){if(p&ll(1ll<<x)){if(a[x]==0){a[x]=p;break;}p^=a[x];}}if(p==0) flag=true;
}
void rebuild()
{for(int i=62;i>=0;--i){if(a[i]==0)continue;//for(int j=i-1;j>=0;--j){if(a[j]==0)continue;if(a[i]&ll(ll(1<<j)))a[i]^=a[j];}}for(int i=0;i<=62;++i)if(a[i])p[cnt++]=a[i];
}
ll query_Kth(ll k)
{ll ret=0;if(flag) k--; if(k==0) return 0;if(k>=ll(1LL<<cnt))return -1;for(int i=62;i>=0;--i)if(k&ll(1ll<<i))ret^=p[i];return ret;
}
int main()
{int T,n;cin>>T;for(int ca=1;ca<=T;ca++){init();printf("Case #%d:\n",ca);cin>>n;for(int i=1;i<=n;i++){cin>>m;build(m);}rebuild();int t;cin>>t;while(t--){ll x;cin>>x;printf("%lld\n",query_Kth(x));}}return 0;
}
?
總結(jié)
以上是生活随笔為你收集整理的【 hdu3949 XOR】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
