• 欢迎光临~

博弈论练习2 Digital Deletions(sg函数)

开发技术 开发技术 2022-10-19 次浏览

题目链接在这里:B-Digital Deletions_牛客竞赛博弈专题班组合游戏基本概念、对抗搜索、Bash游戏、Nim游戏习题 (nowcoder.com)

这道题有一个很明显的特征,就是由当前状态可以推到后面的状态,这符合sg函数类博弈问题,所以我们按照题目要求将当前状态推导到之前遍历过的状态,然后把sg函数推出来就行了。

本题注意一下特殊情况如最高位如果减到0了该如何判断就行了。

 1 #include "bits/stdc++.h"
 2 using namespace std;
 3 const int MAX=1e6+5;
 4 int t,ls;
 5 int sg[MAX];
 6 char s[15];
 7 void sgf(int x){
 8     if (sg[x]!=-1) return;
 9     int i,j;
10     for (i=1;i<=x;i*=10){
11         j=x;
12         while (j/i%10!=0 && j-i>=i){
13             if (sg[j-i]==0){
14                 sg[x]=1;
15                 goto away;
16             }
17             j-=i;
18         }
19         if (x/i%10==0 && sg[x/i/10]==0){
20             sg[x]=1;
21             goto away;
22         }
23     }
24     sg[x]=0;
25     away: return;
26 }
27 
28 int main(){
29     int i,j;
30     scanf("%d",&t);
31     memset(sg,-1,sizeof(sg));
32     sg[0]=1;
33     for (i=1;i<MAX;i++)
34         sgf(i);
35     while (t--){
36         scanf("%s",s+1);
37         ls=strlen(s+1);
38         if (s[1]=='0'){
39             printf("Yesn");
40             continue;
41         }
42         j=0;
43         for (i=1;i<=ls;i++)
44             j=j*10+s[i]-'0';
45         if (sg[j]==0) printf("Non");
46         else printf("Yesn");
47     }
48     return 0;
49 }

 

程序员灯塔
转载请注明原文链接:博弈论练习2 Digital Deletions(sg函数)
喜欢 (0)