首页 > 代码库 > 【bzoj3150】 cqoi2013—新Nim游戏
【bzoj3150】 cqoi2013—新Nim游戏
www.lydsy.com/JudgeOnline/problem.php?id=3105 (题目链接)
题意：在第一个回合中，第一个游戏者可以直接拿走若干个整堆的火柴。可以一堆都不拿，但不可以全部拿走。第二回合也一样，第二个游戏者也有这样一次机会。从第三个回合（又轮到第一个游戏者）开始，规则和Nim游戏一样。问是否有先手必胜策略。
Solution
动态维护线性基。拟阵证明？我也不会，请自行百度。
代码：
// bzoj3105#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<cmath>#define LL long long#define inf 2147483640#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std;const int maxn=110;int bin[32];int a[maxn],b[32],n;bool cmp(int a,int b) { return a>b;}int main() { bin[0]=1;for (int i=1;i<31;i++) bin[i]=bin[i-1]<<1; scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&a[i]); sort(a+1,a+1+n,cmp); LL ans=0,tot=0; for (int i=1;i<=n;i++) tot+=a[i]; for (int i=1;i<=n;i++) { int tmp=a[i]; for (int j=30;j>=0;j--) if (a[i]&bin[j]) { if (!b[j]) {b[j]=i;break;} else a[i]^=a[b[j]]; } if (a[i]) ans+=tmp; } if (ans!=0) printf("%lld\n",tot-ans); else printf("-1"); return 0;}
【bzoj3150】 cqoi2013—新Nim游戏
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。