首页 > 代码库 > BZOJ3759: Hungergame

BZOJ3759: Hungergame

2024-11-17 03:26:38   202人阅读

题目：http://www.lydsy.com/JudgeOnline/problem.php?id=3759

题解：只想到了两种情况必胜，没有推广T_T

先说一下我想到了两种情况：

1）异或和为0  我们一次打开所有的就成了普通的nim游戏。

2）存在n-1的元素的自己异或和为0，那我们把这n-1个箱子打开，然后另一个人如果打开另一个，就成了nim，否则我们把这n-1堆取完，然后它打开我们取完。如果它中途打开了，我们下一步就把最后这堆取完，最终还是我们赢。

正解是必胜的充要条件是存在异或和为0的非空子集。

如何证明？我还是搬运题解吧T_T

http://blog.csdn.net/popoqqq/article/details/41519895

Orz POPOQQQ

代码：

技术分享
 1 #include<cstdio> 2  3 #include<cstdlib> 4  5 #include<cmath> 6  7 #include<cstring> 8  9 #include<algorithm>10 11 #include<iostream>12 13 #include<vector>14 15 #include<map>16 17 #include<set>18 19 #include<queue>20 21 #include<string>22 23 #define inf 100000000024 25 #define maxn 200000+526 27 #define maxm 200000+528 29 #define eps 1e-1030 31 #define ll long long32 33 #define pa pair<int,int>34 35 #define for0(i,n) for(int i=0;i<=(n);i++)36 37 #define for1(i,n) for(int i=1;i<=(n);i++)38 39 #define for2(i,x,y) for(int i=(x);i<=(y);i++)40 41 #define for3(i,x,y) for(int i=(x);i>=(y);i--)42 43 #define for4(i,x) for(int i=head[x],y=e[i].go;i;i=e[i].next,y=e[i].go)44 45 #define for5(n,m) for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)46 47 #define mod 100000000748 49 using namespace std;50 51 inline int read()52 53 {54 55     int x=0,f=1;char ch=getchar();56 57     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}58 59     while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}60 61     return x*f;62 63 }64 int a[100],b[100],n;65 inline bool gauss()66 {67     memset(b,0,sizeof(b));68     for1(i,n)69     {70      for3(j,30,0)71       if(a[i]>>j&1)72       {73           if(!b[j]){b[j]=a[i];break;}74           else a[i]^=b[j];75       }76      if(!a[i])return 1; 77     }78     return 0;79 }80 81 int main()82 83 {84 85     freopen("input.txt","r",stdin);86 87     freopen("output.txt","w",stdout);88 89     int T=read();90     while(T--)91     {92        n=read();93        for1(i,n)a[i]=read();94        puts(gauss()?"Yes":"No");95     }96 97     return 0;98 99 }
View Code

 

BZOJ3759: Hungergame


联系
我们