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

 51Nod Problem 1067 Bash游戏 V2

 Problem Idea

解题思路:

【题意】
有一堆石子,共有n个,A和B轮流拿,A先手,每次只能取1 or 3 or 4颗

取完者获胜,问谁会获胜

【类型】
博弈(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[3]={1,3,4};
bool v[N];
int mex(int x)
{int i;memset(v,false,sizeof(v));for(i=0;i<3;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;
}

规律表如下:

sg[ 0] = 0

sg[ 1] = 1

sg[ 2] = 0

sg[ 3] = 1

sg[ 4] = 2

sg[ 5] = 3

sg[ 6] = 2

sg[ 7] = 0

sg[ 8] = 1

sg[ 9] = 0

sg[10] = 1

sg[11] = 2

sg[12] = 3

sg[13] = 2

sg[14] = 0

sg[15] = 1

sg[16] = 0

sg[17] = 1

sg[18] = 2

sg[19] = 3

sg[20] = 2

sg[21] = 0

sg[22] = 1

sg[23] = 0

sg[24] = 1

sg[25] = 2

sg[26] = 3

sg[27] = 2

sg[28] = 0

sg[29] = 1

sg[30] = 0

sg[31] = 1

sg[32] = 2

sg[33] = 3

sg[34] = 2

sg[35] = 0

sg[36] = 1

sg[37] = 0

sg[38] = 1

sg[39] = 2

sg[40] = 3

sg[41] = 2

sg[42] = 0

sg[43] = 1

sg[44] = 0

sg[45] = 1

sg[46] = 2

sg[47] = 3

sg[48] = 2

sg[49] = 0

sg[50] = 1

sg[51] = 0

sg[52] = 1

sg[53] = 2

sg[54] = 3

sg[55] = 2

sg[56] = 0

sg[57] = 1

sg[58] = 0

sg[59] = 1

sg[60] = 2

sg[61] = 3

sg[62] = 2

sg[63] = 0

sg[64] = 1

sg[65] = 0

sg[66] = 1

sg[67] = 2

sg[68] = 3

sg[69] = 2

sg[70] = 0

sg[71] = 1

sg[72] = 0

sg[73] = 1

sg[74] = 2

sg[75] = 3

sg[76] = 2

sg[77] = 0

sg[78] = 1

sg[79] = 0

sg[80] = 1

sg[81] = 2

sg[82] = 3

sg[83] = 2

sg[84] = 0

sg[85] = 1

sg[86] = 0

sg[87] = 1

sg[88] = 2

sg[89] = 3

sg[90] = 2

sg[91] = 0

sg[92] = 1

sg[93] = 0

sg[94] = 1

sg[95] = 2

sg[96] = 3

sg[97] = 2

sg[98] = 0

sg[99] = 1

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

所以

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

题目链接→51Nod Problem 1067 Bash游戏 V2

 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 = 100;
const int M = 4;
const int inf = 1000000007;
const int mod = 7;
int main()
{int t,n;scanf("%d",&t);while(t--){scanf("%d",&n);if(n%7==0||n%7==2)puts("B");elseputs("A");}return 0;
}

菜鸟成长记