POJ1143:Number Game(状态压缩)

Description

Christine and Matt are playing an exciting game they just invented: the Number Game. The rules of this game are as follows. 
The players take turns choosing integers greater than 1. First, Christine chooses a number, then Matt chooses a number, then Christine again, and so on. The following rules restrict how new numbers may be chosen by the two players: 

  • A number which has already been selected by Christine or Matt, or a multiple of such a number,cannot be chosen. 
  • A sum of such multiples cannot be chosen, either.

If a player cannot choose any new number according to these rules, then that player loses the game. 
Here is an example: Christine starts by choosing 4. This prevents Matt from choosing 4, 8, 12, etc.Let’s assume that his move is 3. Now the numbers 3, 6, 9, etc. are excluded, too; furthermore, numbers like: 7 = 3+4;10 = 2*3+4;11 = 3+2*4;13 = 3*3+4;… are
also not available. So, in fact, the only numbers left are 2 and 5. Christine now selects 2. Since 5=2+3 is now forbidden, she wins because there is no number left for Matt to choose. 
Your task is to write a program which will help play (and win!) the Number Game. Of course, there might be an infinite number of choices for a player, so it may not be easy to find the best move among these possibilities. But after playing for some time, the
number of remaining choices becomes finite, and that is the point where your program can help. Given a game position (a list of numbers which are not yet forbidden), your program should output all winning moves. 
A winning move is a move by which the player who is about to move can force a win, no matter what the other player will do afterwards. More formally, a winning move can be defined as follows. 

  • A winning move is a move after which the game position is a losing position. 
  • A winning position is a position in which a winning move exists. A losing position is a position in which no winning move exists. 
  • In particular, the position in which all numbers are forbidden is a losing position. (This makes sense since the player who would have to move in that case loses the game.)

Input

The input consists of several test cases. Each test case is given by exactly one line describing one position. 
Each line will start with a number n (1 <= n <= 20), the number of integers which are still available. The remainder of this line contains the list of these numbers a1;…;an(2 <= ai <= 20). 
The positions described in this way will always be positions which can really occur in the actual Number Game. For example, if 3 is not in the list of allowed numbers, 6 is not in the list, either. 
At the end of the input, there will be a line containing only a zero (instead of n); this line should not be processed.

Output

For each test case, your program should output "Test case #m", where m is the number of the test case (starting with 1). Follow this by either "There’s no winning move." if this is true for the position described in the input file, or "The winning moves are:
w1 w2 … wk" where the wi are all winning moves in this position, satisfying wi < wi+1 for 1 <= i < k. After this line, output a blank line.

Sample Input

2 2 5
2 2 3
5 2 3 4 5 6
0

Sample Output

Test Case #1
The winning moves are: 2

Test Case #2
There’s no winning move.

Test Case #3
The winning moves are: 4 5 6

Source

Mid-Central European Regional Contest 2000
题意:两人玩游戏,有1些列数,1旦选了某些数字,那末这些数字的倍数和这些数字通过相加能组成的数字都不能选了,当轮到某个人选的时候,没有数字可以选了,那末这个人就必输
思路:以状态紧缩记录枚举所有情况来进行搜索便可
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <math.h>
#include <algorithm>
using namespace std;
#define ls 2*i
#define rs 2*i+1
#define up(i,x,y) for(i=x;i<=y;i++)
#define down(i,x,y) for(i=x;i>=y;i–)
#define mem(a,x) memset(a,x,sizeof(a))
#define w(a) while(a)
#define LL long long
const double pi = acos(⑴.0);
#define Len 200005
#define mod 19999997
const int INF = 0x3f3f3f3f;
#define exp 1e⑹

int cas = 1;
int n,a[25],dp[600000],ans[25],len;

int getnum(int s[])
{
int ret = 0,i;
for(int i = 2;i<=20;i++)
{
if(s[i])
ret|=1;
ret<<=1;
}
return ret;
}

int dfs(int s[],int st)
{
int cpy[25],i,j;
memcpy(cpy,s,25*sizeof(int));
cpy[st] = 0;
for(i = 2; i+st<=20; i++)
{
if(!cpy[i])
cpy[i+st] = 0;
}
int ss = getnum(cpy);
if(dp[ss]!=0)
{
if(dp[ss]>0) return 1;
else return 0;
}
up(i,2,20)
{
if(cpy[i] && !dfs(cpy,i))
{
dp[ss] = 1;
return 1;
}
}
dp[ss] = ⑴;
return 0;
}

int main()
{
int i,j,k;
mem(dp,0);
w((scanf("%d",&n),n))
{
mem(a,0);
up(i,1,n)
{
scanf("%d",&k);
a[k] = 1;
}
int s = getnum(a);
len = 0;
up(i,2,20)
{
if(a[i] && !dfs(a,i))
ans[len++] = i;
}
printf("Test Case #%d
",cas++);
if(len)
{
printf("The winning moves are:");
up(i,0,len⑴)
printf(" %d",ans[i]);
}
else
{
printf("There's no winning move.");
dp[s] = ⑴;
}
printf("

");
}

return 0;
}

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » POJ1143:Number Game(状态压缩)

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡