问题 : 分苹果【博弈】

问题 : 分苹果

时间限制: 1 Sec   内存限制: 128 MB  

给定一堆共n个苹果，两个人轮流进行如下操作：

1，将这一堆苹果分成两堆，每堆的苹果数目必须不同；

2，另一个人选择其中一堆作为新的堆，开始下一轮操作。

直到某个人不能满足要求输掉比赛，游戏结束。

假设两个人都足够聪明——总会选择对自己最优的方案。

比如说有3个苹果，第一个人只能选择分两堆1、2，

第二个人选有一个苹果的堆，该堆不能再分，输；

第二个人选有两个苹果的堆，该堆不能再分，输；

所以第一个人赢。

输入

第一行输入一个整数t，代表有t组测试数据（t <= 100）

接下来有t行，每行有一个整数n代表苹果数目。

保证：1 <= n <= 10000000。

输出

若第一个进行操作的人获得胜利输出1，反之输出0。

样例输入

3 2 3 4

样例输出

0 1 0 思路 ： 找规律。。 代码 #include<string.h> #include<stdio.h> #include<algorithm> #include<math.h> #include<queue> #include<stack> #define inf 0x3f3f3f #define M 10000000+10 #define mod 666666 using namespace std; int a[4]={0,0,0,1}; int b[3]={1,0,1}; int main() { int t; scanf("%d",&t); while(t--) { int n; scanf("%d",&n); if(n<4) printf("%d\n",a[n]); else printf("%d\n",b[(n-3)%3]); } return 0; }