首页 > ACM题库 > HDU-杭电 > HDU 4672-Present Day, Present Time[解题报告]HOJ
2015
09-17

HDU 4672-Present Day, Present Time[解题报告]HOJ

Present Day, Present Time

问题描述 :

Sangxin and Bicycle play games everyday, but no matter what they play, Sangxin always loses. Sangxin found that there is no chance to beat Bicycle even playing dice.
One day, Sangxin came up with a brand new game with stones. In this game there are n piles of stones and m recycling centers, each pile of stones has Ai stones and each recycling center could process exactly Bi (which is pre-assigned) stones at a time. Sangxin and Bicycle operate by turns. Each turn the player must pick one piles of stones and recycle some stones in that pile. Note that they can use recycling centers unlimited times in one turn. The one couldn’t do anything during his turn loses.
After thinking a while Sangxin thought the game is too easy and appended a weird rule: After someone’s turn if there are no way to completely recycle any pile of stones, he loses immediately.
Now, given the initial state of the game, Sangxin wants to know that who will win. Assume they will play in optimal strategy. The players’ name and who will play first is given.

输入:

The input contains several test cases, terminated by EOF. Most of test cases are rather small.
Each case has 4 lines, the first line contains two integer n (1 ≤ n ≤ 100000) and m (1 ≤ m ≤ 100), which denotes the number of stone piles and recycling centers. The second line contains two string (length not greater than 20 and contains only lowercase letters) indicating the players’ name. The first player in that line plays first. The third line contains n integers, i-th denotes Ai (1 ≤ Ai ≤ 1000000000) and next line contains m integer, i-th denotes Bi(1 ≤ Bi ≤ 100).

输出:

The input contains several test cases, terminated by EOF. Most of test cases are rather small.
Each case has 4 lines, the first line contains two integer n (1 ≤ n ≤ 100000) and m (1 ≤ m ≤ 100), which denotes the number of stone piles and recycling centers. The second line contains two string (length not greater than 20 and contains only lowercase letters) indicating the players’ name. The first player in that line plays first. The third line contains n integers, i-th denotes Ai (1 ≤ Ai ≤ 1000000000) and next line contains m integer, i-th denotes Bi(1 ≤ Bi ≤ 100).

样例输入:

3 2
sangxin bike
1 2 3
2 3
3 1
bike sangxin
3 4 9
1

样例输出:

bike
bike

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
#define INF 10005
#define inf 0x0f0f0f0f

using namespace std;
int F[INF], N[INF*10], M[105];
int Pre_dp(int m)
{
	memset(F, 0xef, sizeof(F));
	sort(M+1, M+m+1);
	F[0]=0;
	for (int i=1; i<=m; i++)
		for (int j=M[i]; j<INF; j++)
				F[j]=max(F[j], F[j-M[i]]+1);
	return M[1];
}
int SG(int n, int m)
{
	if (F[n]<-inf) return -1;
	return F[n]+m;
}
int _SG(int n, int mi)
{
	if (n<INF) return SG(n, 0);
	int m=(n-INF)/mi;
	if (n-=m*mi, n>=INF) n-=mi, m++;
	return SG(n, m);
}
char str[2][50];
int main()
{
	//freopen("1.txt", "r", stdin);
	int n, m;

	while (~scanf ("%d %d", &n, &m))
	{
		scanf("%s %s" , str[0], str[1]);
		for (int i=1; i<=n; i++) scanf("%d", &N[i]);
		for (int i=1; i<=m; i++) scanf("%d", &M[i]);
		int sg=0, mi=Pre_dp(m), now, flag=0;
		for (int i=1; i<=n; i++)
			if (now=_SG(N[i], mi), now==-1) flag=1;
			else sg^=now;
		if (flag) puts(str[1]);
		else printf("%s\n", sg?str[0]:str[1]);
	}
}