uva 10561 sg定理

Problem C Treblecross Input: Standard Input

Output: Standard Output

Time Limit: 4 Seconds

Treblecross is a two player game where the goal is to get three X in a row on a one-dimensional board. At the start of the game all cells in the board is empty. In each turn a player puts a X in an empty cell, and if that results in there being three X next to each other, that player wins.

Given the current state of the game, you are to determine if the player to move can win the game assuming both players play perfectly. If so, you should also print all moves that will eventually lead to a win.

Consider the game where the board size is 5 cells. If the first player puts a X at position three (in the middle) so the state becomes ..X.., he will win the game as no matter where the other player puts his X, the first player can get three X in a row. If, on the other hand, the first player puts the X in any other position, the second player will win the game by putting the X in the opposite corner (for instance, after the second player moves the state might be .X..X). This will force the first player to put an X in a position so the second player wins in the next move.

Input

The input begins with an integer N (N<100), the number of states that will follow. Each state is represented by a string on a line by itself. The string will only contain the characters '.' and 'X'. The length of the string (the size of the board) will be between 3 and 200 characters, inclusive. No state will contain three X in a row.

Output

For each case, first output WINNING or LOSING depending on if the player to move will win or lose the game. On the next line, output in increasing order all positions on the board where the player to move may put an X and win the game. The positions should be separated by a blank, and be in increasing order. The leftmost position on the board is 1.

Sample Input Output for Sample Input

.....

X.....X..X.............X....X..X

.X.X...X

...............................................

WINNING

LOSING

WINNING

1 12 15 17 20 24 28 31 33 36 47

题目大意：有n个格子排成一行，其中一些格子里面有字符X。两个选手轮流操作，每次选一个空格，在里面放字符X。如果此时有3个连续的X出现，则该玩家获得胜利。

你的任务是判断先手必胜还是必败，若必胜则，输出所有毕生策略（第一步）。

分析：

遍历每个能操作的位置

（1）若先手走一步后已出现3个连续的X，则此操作为必胜策略。

（2）不能一步定胜负的情况。先手选择一步后，遍历后手的操作。

1：若后手一步能达到3个连续的X，则先手的操作不是必胜策略。

2：第一个操作跟第二个操作都不能判定胜负，求sg函数。

一段全是空白的格子，把X放在任意一个位置，它的右边两个格子跟左边的两个格子（存在的格子）谁去放谁输。每位选手都是用最优的策略，所以X附近的这几个为禁区，拆分为子游戏的时候属于禁区的格子直接不要。

整个游戏，可以看成若干子游戏。g(x)=mex{g(x-3),g(x-4),g(x-5),g(1) xor g(x-6),g(2) xor g(x-7).....}

AC代码：

#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;

vector<int> v;
int sg[300];

int Max(int a,int b)
{
    return a>b?a:b;
}

int mex(int n)
{
    bool flag[300];
    int i,t;
    if(sg[n]!=-1) return sg[n];
    if(n==0) return sg[n]=0;
    memset(flag,false,sizeof(flag));
    //i位置放X,它左边两个跟右边两个都为禁区，谁再放X谁输
    for(i=1;i<=n;i++)
    {
        //一个游戏分成两个子游戏
        t=(mex(Max(0,i-3))^mex(Max(0,n-i-2)));
        flag[t]=true;
    }
    for(i=0;i<300;i++)
        if(!flag[i]) break;
        return sg[n]=i;
}
bool is_oi(string s) //判断先手是否已经胜利
{
    for(int i=0;i<s.size()-2;i++)
        if(s[i]=='X' && s[i+1]=='X' && s[i+2]=='X')
            return true;
        return false;
}

bool is_oi1(string s) //先手一步后，不能确认先手胜利的情况
{
    int i;
    for(i=0;i<s.size();i++)//后手一步后，若后手必胜了，就没判断的必要了
    {
        if(s[i]=='.')
        {
            s[i]='X';
            if(is_oi(s)) return false;
            s[i]='.';
        }
    }
    int ans=0;//整个游戏的SG值
    int num=0;//子游戏的格子个数
    for(i=0;i<s.size();i++)//找子游戏（子游戏的定义：一段空白格子两端端点以外的X不影响游戏的结果）
    {
        //X的前两个空格跟后两个空格都不是最优的走法（必败），所以子游戏（两个X之间一段空白的格子减去每个X附近的两个格子数）
        if(s[i]=='X'||(i>=1&&s[i-1]=='X')||(i>=2&&s[i-2]=='X')||(i+1<s.size()&&s[i+1]=='X')||(i+2<s.size()&&s[i+2]=='X'))
        {ans^=mex(num);num=0;}
        else num++;
    }
    ans^=mex(num);
    if(ans==0)
        return true;
    return false;
}

void solve(string s)
{
    for(int i=0;i<s.size();i++)//先手走一步后，看后手的状态
    {
        if(s[i]=='.')
        {
            s[i]='X';
            if(is_oi(s) || is_oi1(s)) //如果先手这一步，后手的状态是必败的，记录位置
                v.push_back(i+1);
            s[i]='.';
        }
    }
}

int main()
{
    memset(sg,-1,sizeof(sg));
    int  t;
    string s;
    cin>>t;
    while(t--)
    {
        v.clear();
        cin>>s;
        solve(s);
        if(v.size()==0) //先手没有必胜的情况，肯定必败。
            cout<<"LOSING"<<endl<<endl;
        else
        {
            cout<<"WINNING"<<endl;
            for(int i=0;i<v.size();i++)
                printf(i?" %d":"%d",v[i]);
            cout<<endl;
        }
    }
    return 0;
}