此文章可以使用目录功能哟↑(点击上方[+])

 51Nod Problem 1068 Bash游戏 V3

 Problem Idea

解题思路:

【题意】
有一堆石子,共有n个,A和B轮流拿,A先手,每次只能取2的非负整数次幂颗(如1,2,4,8,16,……)

取完者获胜,问谁会获胜

【类型】
博弈(sg函数找规律)

【分析】

一般的博弈题都是可以通过sg函数来求解的,只是直接与间接的区别

直接与间接从何说起呢?当数据比较大时,我们无法直接求得sg值,因为不管时间还是空间上都不允许

这个时候,我们通常的做法是通过sg函数打表来找到规律

在使用sg函数之前,我们先大致了解一下sg函数(具体的可以自行网上学习):

SG函数表示的是某种局面的状态,它是由mex运算得到的
mex表示最小的不属于这个集合的非负整数,例如mex{0,1,2,4}=3,mex{2,3,5}=0,mex{}=0;
其实mex可以这么理解,0表示必败态,非零表示必胜态,根据定理"能一步到达必败态的点就是必胜态",故只有集合包含0,那么mex得到的数必定非0
根据定理"只能到达必胜态的点是必败态",故若集合中不包含0,那么mex得到的数必定为0

接下来,我们回归正题,以下是打表程序:

/*Sherlock and Watson and Adler*/
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<bitset>
#include<cmath>
#include<complex>
#include<string>
#include<algorithm>
#include<iostream>
#define eps 1e-9
#define LL long long
#define PI acos(-1.0)
#define bitnum(a) __builtin_popcount(a)
using namespace std;
const int N = 100;
const int M = 4;
const int inf = 1000000007;
const int mod = 7;
int sg[N],s[7]={1,2,4,8,16,32,64};
bool v[N];
int mex(int x)
{int i;memset(v,false,sizeof(v));for(i=0;i<7;i++){if(x<s[i])break;v[sg[x-s[i]]]=true;}for(i=0;;i++)if(!v[i])return i;
}
int main()
{int i;sg[0]=0;for(i=1;i<N;i++)sg[i]=mex(i);for(i=0;i<N;i++)printf("sg[%2d] = %d\n",i,sg[i]);return 0;
}

规律表如下:

显然,凡是能被3整除的数,它们的sg值都为0,也就是说这些数量的石子,都是必败态,即先手必输

所以

而对于此题来说,n可能为大数,但并不影响,因为一个数能被3整除可以转化为该数各个位数字之和能被3整除

这样计算量就大大降低了,此题得解

【时间复杂度&&优化】
O(n)

题目链接→51Nod Problem 1068 Bash游戏 V3

 Source Code

/*Sherlock and Watson and Adler*/
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<bitset>
#include<cmath>
#include<complex>
#include<string>
#include<algorithm>
#include<iostream>
#define eps 1e-9
#define LL long long
#define PI acos(-1.0)
#define bitnum(a) __builtin_popcount(a)
using namespace std;
const int N = 1005;
const int M = 4;
const int inf = 1000000007;
const int mod = 7;
char s[N];
int main()
{int t,i,sum;scanf("%d",&t);while(t--){sum=0;scanf("%s",s);for(i=0;s[i]!='\0';i++)sum+=s[i]-'0';if(sum%3)puts("A");elseputs("B");}return 0;
}