首页 > 代码库 > BZOJ 3105：[cqoi2013]新Nim游戏
BZOJ 3105：[cqoi2013]新Nim游戏
BZOJ 3105：[cqoi2013]新Nim游戏
题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3105
题目大意：在传统的Nim取石子游戏中做了改变：两人刚开始可以取走任意堆石子（不包括全部）后进行传统游戏，问先手能否必胜，若必胜求出刚开始最少取多少石子。
线性基
传统Nim游戏先手必胜的前提条件为$a_0 \lxor a_1 \lxor a_2 \lxor ... \lxor a_{n-1} \neq 0$.
故若欲使新Nim游戏先手必胜，则需保证先手刚开始取完后剩下的元素线性无关.
而问最少取多少石子，只需将原数列降序排序，贪心构造极大线性无关组.
代码如下：
1 #include <cstdio> 2 #include <algorithm> 3 #define MAX_BASE 30 4 using namespace std; 5 typedef long long ll; 6 ll n,a[105],b[105]; 7 bool cmp(ll a,ll b){ 8 return a>b; 9 }10 ll cal(){11 ll ans=0;12 for(int i=0;i<n;++i){13 ll t=a[i];14 bool f=0;15 for(int j=MAX_BASE;j>=0;--j){16 if(a[i]>>j&1){17 if(b[j])a[i]^=b[j];18 else{19 b[j]=a[i];20 f=1;21 for(int k=j-1;k>=0;--k)if(b[k]&&(b[j]>>k&1))b[j]^=b[k];22 for(int k=j+1;k<=MAX_BASE;++k)if(b[k]>>j&1)b[k]^=b[j];23 break;24 }25 }26 }27 if(f)ans+=t;28 }29 return ans;30 }31 int main(void){32 ll sum=0,ans;33 scanf("%lld",&n);34 for(int i=0;i<n;++i){35 scanf("%lld",&a[i]);36 sum+=a[i];37 }38 sort(a,a+n,cmp);39 ans=cal();40 for(int i=0;i<n;++i)41 printf("%lld\n",b[i]);42 printf("%lld\n",sum-ans);43 }
BZOJ 3105：[cqoi2013]新Nim游戏
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。