博弈论一点点

Posted by Cww97 on 2016-07-26

版权声明:本文为博主原创文章,未经博主允许不得转载。原文所在http://blog.csdn.net/cww97 https://blog.csdn.net/cww97/article/details/52037047
基本就是把这里的题过了一遍
SG函数资料(入门必备)

感觉很不错的文章
博弈论(一):Nim游戏
博弈论(二):Sprague-Grundy函数
寻找必败态——一类博弈问题的快速解法

练手
hdu1846

1
2
3
4
5
6
7
8
9
10
11
12
#include<cstdio>
using namespace std;
int main(){
int T,n,m;
scanf("%d",&T);
while (T--){
scanf("%d%d",&n,&m);
if (n<=m)puts("first");//多余的一行
else puts((n%(m+1))?"first":"second");
}
return 0;
}

hdu2147

1
2
3
4
5
6
7
8
9
10
#include<cstdio>
using namespace std;

int main(){
int n,m;
while (scanf("%d%d",&n,&m)==2&&n&&m){
puts((n&m&1)?"What a pity!":"Wonderful!");
}
return 0;
}

hdu2188

1
2
3
4
5
6
7
8
9
10
11
#include<cstdio>
using namespace std;
int main(){
int T,n,m;
scanf("%d",&T);
while (T--){
scanf("%d%d",&n,&m);
puts((n%(m+1))?"Grass":"Rabbit");
}
return 0;
}

hdu2148
PN似乎反过来了。。。。找规律

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<cstdio>
using namespace std;
int main(){
int n,m;
while (scanf("%d%d",&m,&n)==2){
if (n>=m){
for (int i=m;i<n;i++)printf("%d ",i);
printf("%d\n",n);
}else {
int x=m%(n+1);
if (x)printf("%d\n",x);
else puts("none");
}
}
return 0;
}

Nim游戏

对于一个Nim游戏的局面(a1,a2,…,an),它是P-position当且仅当a1a2an=0,其中表示异或(xor)运算。

先记个结论(坑以后再填)

hdu1907

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<cstdio>
using namespace std;
int main(){
int T,n,x;
scanf("%d",&T);
while (T--){
scanf("%d",&n);
int ans=0,cnt=0;
for (int i=1;i<=n;i++){
scanf("%d",&x);
ans ^= x;
if (x>1)cnt++;
}
if (!cnt)ans = !(n&1);
if (ans)puts("John");
else puts("Brother");
}
return 0;
}

hdu2509

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<cstdio>
#include<iostream>
using namespace std;

int main(){
int n,x;
while (scanf("%d",&n)==1){
int ans=0,cnt=0;
for (;n--;){
scanf("%d",&x);
ans ^= x;
if (x>1) cnt++;
}
if (!cnt)ans = !!(n&1);//这个时候n都=0了,前面循环应该for个i,这里能过是因为数据弱吧
if (ans)puts("Yes");
else puts("No");
}
return 0;
}

hdu1527
威佐夫博弈

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const double phi=(1+sqrt(5))/2.0;
int main(){
int m,n;
while (scanf("%d%d",&n,&m)==2){
if (min(n,m)==(int)(phi*abs(n-m)))puts("0");
else puts("1");
}
return 0;
}

继续练手

hdu1847

1
2
3
4
5
6
7
8
9
10
#include<cstdio>
using namespace std;
int main(){
int n;
while (scanf("%d",&n)==1){
if (n%3==0)puts("Cici");
else puts("Kiki");
}
return 0;
}

hdu1849

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<cstdio>
using namespace std;
int main(){
int n,x;
while (scanf("%d",&n)==1&&n){
int ans=0;
for (;n--;){
scanf("%d",&x);
ans ^= x;
}
puts(ans?"Rabbit Win!":"Grass Win!");

}
return 0;
}

hdu1850

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<cstdio>
using namespace std;
const int N=111;
int a[N];
int main(){
int n;
while (~scanf("%d",&n)&&n){
int nim=0;
for (int i=1;i<=n;i++){
scanf("%d",&a[i]);
nim ^= a[i];
}
if (!nim)puts("0");
else {
int cnt=0;
for (int i=1;i<=n;i++){
int kk = nim^a[i];
if (a[i]>kk)cnt++;
}
printf("%d\n",cnt);
}
}
return 0;
}

SG函数模板
理论详细解释
这里写图片描述

hdu1848

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
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 1007;
int sg[N],fib[N];

void getFib(){
fib[1] = 1 , fib[2] = 2;
for (int i=3;i<=17;i++)
fib[i]=fib[i-1]+fib[i-2];
}

void getSG(){
getFib();
/*memset(sg,0,sizeof(sg));
int lastP;
for (int i = 0; i < N ; i++ ){
if (sg[i]==-1) sg[i] = i-lastP;
else {//sg[i]==0
lastP = i ;
for (int j=1;j<17&&i+fib[j]<N;j++){
sg[i+fib[j]] = -1 ;
}
}
//printf("sg[%d]=%d\n",i,sg[i]);
}*/
int j;
sg[0]=0;
bool mex[17];
for(int i=1;i<N;i++){
memset(mex,0,sizeof(mex));
for (j=1 ;fib[j]<=i ;j++ )mex[sg[i-fib[j]]]=1;
for (j=0 ; j<N ; j++ )if(!mex[j])break;
sg[i] = j;
}

}
//by cww97
int main(){
int x,y,z;
getSG();
while (scanf("%d%d%d",&x,&y,&z)==3){
if ( !x&& !y&& !z ) break;
int ans = sg[x]^sg[y]^sg[z];
if (ans)puts("Fibo");
else puts("Nacci");
}
return 0;
}

hdu1536
再次上演悲剧,调试N弄成了15,然后RTE,然后设成了10W(题目上数字看错了),然后TLE,然后,,,,好气啊
这里写图片描述

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
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=10007;
int s[110],sg[N],k;

void getSG(){
sg[0]=0;
bool vis[N];
for (int i=1;i<N;i++){
memset(vis,0,sizeof(vis));
for (int j=1;s[j]<=i&&j<=k;j++)vis[sg[i-s[j]]]=1;
for (int j=0;j<N;j++)if(!vis[j]){sg[i]=j;break;}
}
}

int main(){
//freopen("fuck.in","r",stdin);
int m,n,x;
while (scanf("%d",&k)==1&&k){
for (int i=1;i<=k;i++)scanf("%d",&s[i]);
sort(s+1,s+k+1);
getSG();
scanf("%d",&n);
while (n--){
scanf("%d",&m);
int ans=0;
while (m--){
scanf("%d",&x);
ans ^= sg[x];
}
putchar(ans?'W':'L');
}
puts("");
}
return 0;
}

hdu5724

第一次多校训练的题,,就是这题引出了这一整篇文fei章hua

学(zhuang)术(bi)一点的说法是,状态压缩+SG
先说状态压缩
简单点的话,一行一行处理,第i个格子有棋子就 +1<< i(2的i次方) ,最后得到一个数字表示这一行的一种状态,个人习惯从1开始数,,,于是1<<0=1遍没有意义,导致我的表只有偶数(一半是空的,为了个人的强迫症强行多开了一倍空间,不过我喜欢,嘻嘻),所以所有状态的最小值是0(没有棋子),最大是(1<<21-2)(所有格子都有棋子,等比数列求个和就行)。

SG嘛,对棋盘的每个状态求sg值,注意所有棋子集中在右边的时候是没法走的(sg=0),所以从大到小求,,,状态变化,我一开始写的加减号,然后看有人用的位运算,以为自己错了,改成位运算的样子,A了之后又感觉自己想法不错,改回加减号,果然还是A了,,当然,感觉用位运算更易于理(zhuang)解(bi)一点,这里贴的代码就是位运算版本的辣(mdzz,一个符号讲这么多废话)

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
#include<cstdio>
#include<cstring>
using namespace std;
const int N=(1<<21)+7;
int sg[N];
int c[23],C;//the position of chesses

int next(int x){//move the x-th chess
for (int i=x;i<=C;i++){
if (c[i+1]>c[i]+1)return 1<<(c[i]+1);
}
return 0;
}

void getSG(){
bool vis[107];// enough??
for (int i=N-9;i>=0;i-=2){//downto
C=0; //get the stituation
for (int j=1;j<=20;j++)//num->array
if (i&(1<<j)) c[++C]=j;
c[C+1]=21;
memset(vis,0,sizeof(vis));//sgsgsg
for (int j=1;j<=C;j++){
int nxt=next(j);//move a chess
if (nxt)vis[sg[i^(1<<c[j])^nxt]]=1;//- +
}
for (int j=0;j<107;j++)
if(!vis[j]){sg[i]=j;break;}
}
}

int main(){
//freopen("fuck.in","r",stdin);
int T,n,m,x;
getSG();
scanf("%d",&T);
while (T--){
int ans = 0;
scanf("%d",&n);
for (;n--;){
int che = 0;
scanf("%d",&m);
for (;m--;){
scanf("%d",&x);
che |= 1<<x;//+=
}
ans ^= sg[che];
}
if (ans)puts("YES");
else puts("NO");
}
return 0;
}