首页 > ACM题库 > HDU-杭电 > HDU 2999-Stone Game, Why are you always there?[解题报告]HOJ
2014
02-24

HDU 2999-Stone Game, Why are you always there?[解题报告]HOJ

Stone Game, Why are you always there?

问题描述 :

“Alice and Bob are playing stone game…”
“Err…. Feel bored about the stone game? Don’t be so, because stone game changes all the time!”
“What the hell are they thinking for?”
“You know, whenever Alice is trying to make fun of Bob, she asked him to play stone game with him.”
“Poor Bob… What’s the rule today?”
“It seems Alice only allows some fixed numbers of continuous stones can be taken each time. And they begin with one string of stones.”
“A string? Formed as a circle or a line?”
“A line.”
“Well, I think I may help Bob with that.”
“How?”
“I may tell him to skip this round if he has no chance to win.”
“Good idea maybe, I mean, Alice always let Bob play first, because she think herself is smart enough to beat Bob no matter how.”
“Yes, she’s actually right about herself. Let me see if Bob has a chance to win…”
……

输入:

There are multiple test cases, for each test case:
The first line has a positive integer N (1<=N<=100).
The second line contains N positive integers, a1, a2 … an, separated by spaces, which indicate the fixed numbers Alice gives.
The third line, a positive integer M. (M<=1000)
Following M lines, one positive integer K (K<=1000) each line. K means in this round, the length of the stone string.

输出:

There are multiple test cases, for each test case:
The first line has a positive integer N (1<=N<=100).
The second line contains N positive integers, a1, a2 … an, separated by spaces, which indicate the fixed numbers Alice gives.
The third line, a positive integer M. (M<=1000)
Following M lines, one positive integer K (K<=1000) each line. K means in this round, the length of the stone string.

样例输入:

3
1 5 1
1
1

样例输出:

1

#include <cstdlib> 
#include <cctype> 
#include <cstring> 
#include <cstdio> 
#include <cmath> 
#include <algorithm> 
#include <vector> 
#include <string> 
#include <iostream> 
#include <sstream> 
#include <map> 
#include <set> 
#include <queue> 
#include <stack> 
#include <fstream> 
#include <numeric> 
#include <iomanip> 
#include <bitset> 
#include <list> 
#include <stdexcept> 
#include <functional> 
#include <utility> 
#include <ctime>
using namespace std;
ifstream fin("aa.txt");
#define MAX(a,b) ((a) > (b) ? (a) : (b))
#define MIN(a,b) ((a) < (b) ? (a) : (b))
#define MEM(a,b) memset((a),(b),sizeof(a))
#define BLANK(a) for(int i = 0; i < (a); i ++) printf(" ")
const int N = 1001;
int a[N];
int sg[N];
int tmp[N];
int n,m,k;
int mex(int x)
{
	if(sg[x] >= 0) return sg[x];
	
	MEM(tmp,0);
	for(int i = 0; i < n; i++)
	{
		for(int j = x-a[i]; j >= 0; j--)
		{
			tmp[mex(j)^mex(x-a[i]-j)] = 1;
		}
	}
	for(int i = 0; ; i ++)
	{
		if(!tmp[i])
		{
			return sg[x] = i;
		}
	}
}
int main()
{
	
	while(scanf("%d",&n) !=EOF)
	{
		for(int i = 0; i < n; i++)
			scanf("%d",&a[i]);
		int cnt = 1;
		sort(a,a+n);
		for(int i = 1; i < n; i++)
		{
			if(a[i] != a[i-1])
			{
				a[cnt++] = a[i];
			}
		}
		n = cnt;
		MEM(sg,-1);
		sg[0] = 0;
		scanf("%d",&m);
		while(m--)
		{
			scanf("%d",&k);
			if(mex(k))
				puts("1");
			else
				puts("2");
		}
	}
	return 0;
}