LightOJ 1401 - No Tic-tac-toe(博弈,SG定理)

àì夳堔傛蜴生んèń 2022-06-11 07:38 166阅读 0赞

##                         No More Tic-tac-toe ##

[LightOJ - 1401 ][LightOJ - 1401]

Alice was bored with the game tic-tac-toe. Usually she used to play against computer. She was so bored because, she always managed to make a tie against computer as she already became an expert in this game. She was also bored about the matching things, that means she does not like to see two adjacent **'X'**s or two adjacent **'O'**s. So Bob created a new computer game for her.

Here is the description of this new 2-player game:

1)      A **1 x N** grid will be given.

2)      In each turn, a player can mark an unmarked cell by an **'X'** or by an **'O'** (it's not Zero it is big **'O'**).

3)      No two adjacent **'X'**s are allowed in this game.

4)      No two adjacent **'O'**s are allowed in this game.

5)      The player who marks the last cell wins the game.

Let's have an example for **N = 3**. Suppose first player mark the leftmost cell with an **'X'**. Then the grid will look like this:

![c41fef8ea800b97b4f9986d9c93ab891_v_1501119992][]

From this state, the winning move of the second player is to mark the rightmost cell with an 'O'.

![8f9d07c63f757cbd2663e634f7b33330_v_1501119992][]

Now first player has no move, because in the only empty cell she cannot mark **'X'** and cannot mark **'O'** because the left of this cell is already marked **'X'** and the right of this cell is marked **'O'**. The second player will win.

But this is not an optimal example for first player. If in first move, the first player marks the middle cell with any one of **'X'**or **'O'**, she will win.

Now about Bob's computer game, Alice always makes the first move. Alice usually used to start playing with Bob. But most often after some move, Bob gave his responsibility to the computer. Computer always plays optimally. You are given the state of the grid after Bob's departure and your task is to determine whether it is possible to win against computer from this state for Alice.

**Input**

Input starts with an integer **T (≤ 10000)**, denoting the number of test cases.

Each case starts with a line containing a string which represents the state of the game after Bob's departure. Here the length of the string is **N (1 ≤ N ≤ 100)**. In this string besides **'X'** and **'O'**, another character **'.'** is used, which represents an unmarked cell.

**Output**

For each case, print the case number and **'Yes'** if it is possible to win against computer, otherwise print **'No'**.

**Sample Input**

...

X..

....O

..X..

**Sample Output**

Case 1: Yes

Case 2: No

Case 3: No

Case 4: Yes

Case 5: Yes

题意：

每次两个玩家进行游戏，轮流在一条直线上画O和X，O不能和O相邻，X不能和X相邻，每个玩家既可以选择画X也可以选择画O，当有玩家无处可画的时候，该玩家就输了，另一个玩家就赢了。这个题目会给你一个残局，每个残局都是爱丽丝先下的第一步，如果该残局爱丽丝可以赢过电脑就输出yes，否则输出no。

思路：

对于每一个残局，我们可以根据'O'和'X'把它分成许多个中间部分全是'.'的子残局，通过找规律我们可以发现，由O和X组成的子残局的SG值全部为0，而由O和O或X和X组成的子残局的SG值全部为1，那么接下来我们就只需要判断左右两个端点的情况就行了，有一点需要注意的是你需要记录当前这一步是爱丽丝下还是电脑下，然后才能判断出最终正确答案，AC代码如下。

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <string>
    #include <cstdlib>
    #include <cmath>
    #include <vector>
    #include <queue>
    #include <map>
    #include <algorithm>
    #include <set>
    #include <functional>
    using namespace std;
    typedef long long LL;
    typedef unsigned long long ULL;
    const int INF = 1e9 + 5;
    const int MAXN = 100005;
    const int MOD = 1000000007;
    const double eps = 1e-8;
    const double PI = acos(-1.0);
    
    int T, n, sg[105], CAS;
    char s[105];
    
    void solve()
    {
    	for (int i = 1; i < 102; i++)
    	{
    		memset(s, 0, sizeof s);
    		for (int j = 0; j < i; j++)
    		{
    			if (j)
    				s[sg[i - j - 1] ^ 1] = true;
    			s[sg[i - j - 1]] = true;
    		}
    		while (s[sg[i]])
    		{
    			sg[i]++;
    		}
    	}
    }
    
    int main()
    {
    	solve();
    	scanf("%d", &T);
    	while (T--)
    	{
    		scanf(" %s", s);
    		bool first = true;
    		int l, r = -1, x;
    		for ( n = 0; s[n]; n++)
    		{
    			if (s[n]!='.')
    			{
    				first = !first, l = r, r = n;
    				if (l < 0)
    					x = sg[r];
    				else
    					x ^= s[l] == s[r];
    			}
    		}
    		if (r < 0)
    			x = n & 1;
    		else
    			x ^= sg[n - r - 1];
    		printf("Case %d: %s\n", ++CAS, (x&&first) || (!(x || first)) ? "Yes" : "No");
    	}
    }

[LightOJ - 1401]: https://vjudge.net/problem/27109/origin
[c41fef8ea800b97b4f9986d9c93ab891_v_1501119992]: https://odzkskevi.qnssl.com/c41fef8ea800b97b4f9986d9c93ab891?v=1501119992
[8f9d07c63f757cbd2663e634f7b33330_v_1501119992]: https://odzkskevi.qnssl.com/8f9d07c63f757cbd2663e634f7b33330?v=1501119992