《ACM国际大学生程序设计竞赛题解I》—

《ACM国际大学生程序设计竞赛题解I》——6.10

Pku 1143：

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.

题目大意：两个人玩零和博弈游戏，轮流选取[2,20]的整数，最终没有数字可选的玩家输。而数字无法被选有如下的两条限制：

(1) 选过的数字不能再选，其整数倍的数字也不能再选。

(2) 不能选的数字的和不能被选择。

现在给出游戏过程中某个某个状态<i,j,k…>表示当前i、j、k…还可以选，那么请编程输出当前状态下的所有必胜策略。如果不存在，则输出对应的语句。

分析：其实这道题和之前我们探讨过的一道博弈问题非常的类似，可以说在整体的思维上是一致的。我们从特殊的情形来分析然后逐步进行推广。如果给出的状态是<2,4>,那么显然必胜数(就是当前状态游戏选择该数会引导出必胜策略，下面都简称为必胜数)是2。如果给出的状态是<2,3,4>，显然必胜数是4。很容易看到，对于小规模的状态时，我们非常容易判断，那么对于较大规模的状态，我们依据前后状态的转移关系(一个是状态参数关系的转移，另一个则是博弈NP态的转移)，可以通过递归缩减状态规模的方法来判断当前状态是否存在必胜态。

以上是对于这道问题一个整体思维的分析，下面我们面临的问题是如何编程来模拟实现这个基于递归的计算过程。

数据结构：

首先我们需要一种结构来记录某种状态<i,j,k…>，为了编程的方便，我们用一个整数num来记录，但是我们从二进制的角度去解读这个整数num，举个例子来说，对于状态<2,3,4>，即表示二进制数从右边开始，第2、3、4位是1，即有num = 14.

其次我们看到这个递归搜索的过程可能在后面输入的时候进行重复计算，因此这里应该采用记忆化搜索的策略，这里我们用map[num]来表示状态num(基于上一段我们说过的转化)的胜负态。

状态转移：

状态参数之间的转移：假设这里我们给出了一个状态num0，<a1,a2,a3…>，现在我们需要做的是依次取走a1、a2、a3…所形成的状态num1、num2、num3中的胜负态是怎样的。那么这里我们面临这样一个问题，从num0出发，我们如何得到num1、num2、num3这些状态参数呢？我们当然要从题目要求当中提取信息——取走a1会导致a1的整数倍、a1和其余不可取的数字的和变成不可取，这便是状态转移的关键。

博弈NP态的转移：这一点是非常重要的，因为我们最终要看的就是这种状态到底存不存在必胜策略，这里我们需要知道的是，从一个大规模问题递归搜索胜负态的时候，对于某条状态路径num0->num1->num2…，其胜负态一定是交替的，即N->P->N->P…这一点基本对于所有的二元零和博弈都适用。

进一步基于编程化的思考：

那么通过上面的分析，我们看到一个整体渐渐清晰的思维轮廓，基于状态参数之间的转移关系和二元博弈自身胜负态的转移关系，我们能够实现递归求解，但是在具体的编程中，我们应该如何实现呢？

一个最困难的点就是状态参数之间的转移，这里我们要运用到巧妙的位运算，首先假设一个问题情境，对于状态num0，我们拿走整数i，将生成的状态用num1记录。我们用j记录i的整数倍，那么num0 | 1 << j所表示的二进制数将能够表征状态num1所有不能取的数字，即如果数字k在状态num1中不能取，则num1的二进制表示中自右往左第k+1位是0.下面我们要做的应该是保留那些能够取的数字，我们通过一个整数2^(j-1) – 1来得到状态num0中小于j的数字，然后二者做‘|’运算，在于num0做‘&’运算，即可得到num1.

即num1 = num0 & ((num0 | 1 << j)| 2^(j-1) - 1)，这是这道题的状态参数转移式字。

而对于NP态的转移方程，设map[num]记录状态num的胜负态(map[num] = 1表示面临当前状态的玩家有必胜态，否则map[num] = 0)，num1,num2,num3…numi是num0的下一个状态，则有如下的胜负态转移方程：

map[num0] = (1 - map[num1]) | (1 – map[num2]) |(1 – map[num3] ) | … |(1 – map[numi]).

基于这个层面的分析，便可以编程实现了。

简单的参考代码如下：

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 1048575;//总状态数

int Map[maxn];
int mask[20];
int judge(int num)
{
    int i , j;
     if(Map[num] == -1)
     {
         Map[num] = 0;
         for(i = 2;i <= 20;i++)//遍历当前状态可能取走数的所有情况
         {
             if((num & mask[i]))//整数i在当前状态可以取
             {
                   int temp = num;
                   j = i;
                   while(j <= 20)
                   {
                       temp &= (((num | 1) <<j) | (mask[j] - 1)); //位运算，<<优先于 | ，这里应该加小括号
                       j += i;
                   }

                   int Win = 1 - judge(temp);
                   if(Win == 1)
                        Map[num] += mask[i];
             }
         }
     }

     return Map[num];
}

int main()
{
    mask[1] = 0;
    Map[0] = 0;
     for(int i = 1;i < 20;i++)
          mask[i + 1]  = 1 << i;
          memset(Map,-1,sizeof(Map));
     int n;
     int tt = 1;
     while(scanf("%d",&n) != EOF)
    {
         if(n == 0)  break;

        int a = 0;
        for(int i = 1;i <= n;i++)
        {
            int temp;
            scanf("%d",&temp);
            a |= mask[temp];//对于初始状态的重构
        }
    printf("Test Case #%d
",tt++);
    int answer = judge(a);
    if(answer == 0)
              printf("There's no winning move.
");
    else
       {
            printf("The winning moves are:");
            answer /= 2;
             for(int i = 2;i <= 20;i++)
             {
                 if(answer%2 == 1)
                       printf(" %d",i);

                       answer >>= 1;
                       if(answer == 0)
                           break;
             }
             printf("
");
       }
      printf("
");
    }
}