2015
04-16

Alice and Bob

Alice and Bob are very smart guys and they like to play all kinds of games in their spare time. The most amazing thing is that they always find the best strategy, and that’s why they feel bored again and again. They just invented a new game, as they usually did.
The rule of the new game is quite simple. At the beginning of the game, they write down N random positive integers, then they take turns (Alice first) to either:
1. Decrease a number by one.
2. Erase any two numbers and write down their sum.
Whenever a number is decreased to 0, it will be erased automatically. The game ends when all numbers are finally erased, and the one who cannot play in his(her) turn loses the game.
Here’s the problem: Who will win the game if both use the best strategy? Find it out quickly, before they get bored of the game again!

The first line contains an integer T(1 <= T <= 4000), indicating the number of test cases.
Each test case contains several lines.
The first line contains an integer N(1 <= N <= 50).
The next line contains N positive integers A1 ….AN(1 <= Ai <= 1000), represents the numbers they write down at the beginning of the game.

The first line contains an integer T(1 <= T <= 4000), indicating the number of test cases.
Each test case contains several lines.
The first line contains an integer N(1 <= N <= 50).
The next line contains N positive integers A1 ….AN(1 <= Ai <= 1000), represents the numbers they write down at the beginning of the game.

3
3
1 1 2
2
3 4
3
2 3 5

Case #1: Alice
Case #2: Bob
Case #3: Bob

1、把A堆 的两个石子合并。加入到B堆。

2、把B堆的石子减1

3、把A堆的一个石子加入的B堆

4、把A堆的石子减1

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
using namespace std;
int dp[59][50009];
int dfs(int z,int s)
{
if(dp[z][s]!=-1) return dp[z][s];
if(z==0) return dp[z][s] = s&1;
if(z==1) return dp[1][s]=1;
if(s==1) return dp[z][s] = dfs(z+1,0);
dp[z][s] = 0;
if(!dfs(z-1,s)) dp[z][s] = 1;///直接拿走1个的
if(s>1&&!dfs(z,s-1)) dp[z][s] = 1;
if(s>1&&!dfs(z-1,s+1)) dp[z][s] = 1;
if(z>1&&!dfs(z-2,s?s+3:s+2)) dp[z][s] = 1;///合并之后加入s里
return dp[z][s];
}
int main()
{
freopen("in.txt","r",stdin);
int cas,T=1,n;
scanf("%d",&cas);
memset(dp,-1,sizeof(dp));
while(cas--)
{
scanf("%d",&n);
int z=0,s=0,t=0;
for(int i=0;i<n;i++)
{
scanf("%d",&t);
if(t==1) z++;
else s+=t+1;
}if(s>1) s--;
printf("Case #%d: %s\n",T++,dfs(z,s)?"Alice":"Bob");
}
return 0;
}


1. 海雌狐战斗机雷达操作员不给风挡不知道是什么想法，做成海毒液那样能增加很多阻力么？！看这设计，估计和3V轰炸机一个德行：飞行员有弹射座椅，煤坑里的雷达操作员没有，出事之后飞行员嗖一声走了，剩下雷达操作员心中十万草泥马奔腾而过。

2. 思路二可以用一个长度为k的队列来实现，入队后判断下队尾元素的next指针是否为空，若为空，则出队指针即为所求。

3. 第一句可以忽略不计了吧。从第二句开始分析，说明这个花色下的所有牌都会在其它里面出现，那么还剩下♠️和♦️。第三句，可以排除2和7，因为在两种花色里有。现在是第四句，因为♠️还剩下多个，只有是♦️B才能知道答案。