[原创]HDU 1404 Digital Deletions [SG]【博弈】

2017-07-05 19:07:23 Tabris_ 阅读数：239

博客爬取于2020-06-14 22:39:45
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/74482641

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1404
————————————————————————————————————————————
Digital Deletions

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 2891 Accepted Submission(s): 1052

Problem Description
Digital deletions is a two-player game. The rule of the game is as following.

Begin by writing down a string of digits (numbers) that’s as long or as short as you like. The digits can be 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 and appear in any combinations that you like. You don’t have to use them all. Here is an example:

这里写图片描述

On a turn a player may either:
Change any one of the digits to a value less than the number that it is. (No negative numbers are allowed.) For example, you could change a 5 into a 4, 3, 2, 1, or 0.
Erase a zero and all the digits to the right of it.

The player who removes the last digit wins.

The game that begins with the string of numbers above could proceed like this:
这里写图片描述

Now, given a initial string, try to determine can the first player win if the two players play optimally both.

Input
The input consists of several test cases. For each case, there is a string in one line.

The length of string will be in the range of [1,6]. The string contains only digit characters.

Proceed to the end of file.

Output
Output Yes in a line if the first player can win the game, otherwise output No.

Sample Input
0
00
1
20

Sample Output
Yes
Yes
No
No

————————————————————————————————————————————
题目大意:

给你一个长度不超过6的有数字组成的字符串,两个人分别操作,最后一次操作的人赢,问先手能不能赢.
有两种操作:
将任意一个不为0的数字变成小于它的数字
将任意一个0开始及其右面的左右数字删除.

很容易想到要用SG函数来求解，且第一个数字为0的先手必胜

但是这种时候用mex操作来求解SG函数实在太过麻烦，而且其中对于有前置0的状态很不好表示。

所以这里求解SG函数的时候用定义来求：
SG[]=0 表示必败 SG[]=1 表示必胜

能一步到达必败态的状态一定是必胜态.

所以我们从必败态出发,很容易表示其上一步状态,且不会出现有前置0的情况,

有SG[1]=0;
所以能够确保能够到达所有的状态在[1,1000000)

附本题代码
————————————————————————————————————————————

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
int sg[1000001];
int h[70],my[111],len;

int pow10(int x){
    if(x==0) return 1;
    if(x==1) return 10;
    if(x==2) return 100;
    if(x==3) return 1000;
    if(x==4) return 10000;
    if(x==5) return 100000;
}

void findsg(int x){
    int tem = x;len=0;
    for(;tem;tem/=10)      my[len++]=tem%10;

    for(int j=0;j<len;j++)
        for(int k=1;k+my[j]<10;k++)
            sg[x+pow10(j)*k]=1;

    int k=1;
    for(x*=10;x<1000000;x*=10) {
        for(int i=0;i<k;i++) sg[x+i]=1;
        k*=10;
    }

    return ;
}

void init(){
    memset(sg,0,sizeof(sg));
    sg[0]=1;
    for(int i=1;i<1000000;i++)if(!sg[i])
        findsg(i);
}

char s[10];
int main(){
    init();
    while(~scanf("%s",s)){
        if(s[0]=='0') {
            puts("Yes");
            continue;
        }

        int x=0;
        for(int i=0;s[i];i++) x=(x<<3)+(x<<1)+s[i]-'0';

        if(sg[x]) puts("Yes");
        else      puts("No");
    }
    return 0;
}