三道博弈论入门题

首先同学们要学习一下[博弈论](https://www.cnblogs.com/sineatos/p/3888921.html)... 然后这里是~~广~~杭电上的三道题： # 1.最(zhui)简单(dang)的[巴什博奕](https://www.cnblogs.com/Judge/p/10920451.html#_label32) [传送门](http://acm.hdu.edu.cn/showproblem.php?pid=1846) ## 题意 题目不多说了，就是两个人取 n 个石子，每次最多取 m 个，不能操作者输 ## 分析 其实呢，这玩意儿看标题的链接里的就好了，就是个裸题，代码简短愉快 ``` //by Judge #include<bits/stdc++.h> #define Rg register int T,n,m; int main(){ scanf("%d",&T); while(T--){ scanf("%d%d",&n,&m); puts(n%(m+1)?"first":"second"); } return 0; } ``` # 2.很(heng)简单(dang)的巴什博奕 [传送门](http://acm.hdu.edu.cn/showproblem.php?pid=4764) ## 题意 题目不多说了，其实就是巴什博奕的变种 ## 分析 首先我们可以看出，当前操作者面对 $X=[n-k,n-1]$ 的情况时必胜 而普通巴什博奕是当前操作者面对剩下 $[1,k]$ 个石子时必胜，可以看到这里就是反了一下 于是我们把 n 减去 1 之后就可以当做普通的巴什博奕把加石子当做减石子做了，代码依旧短 ``` //by Judge #include<bits/stdc++.h> #define Rg register int n,m; int main(){ while(~scanf("%d%d",&n,&m)&&n&&m) puts((n-1)%(m+1)?"Tang":"Jiang"); return 0; } ``` # 3.不是很难(nang)的[ SG 函数](https://www.cnblogs.com/sineatos/p/3888921.html) [传送门](http://acm.hdu.edu.cn/showproblem.php?pid=1847) ## 题意 取 n 个石子，每次取 2 的幂次，不能操作者输 ## 分析 SG 函数，标题里有链接 SG 函数定义直接上，裸题，这数据范围 $n^2$ 也完全顶得住...代码相对上面小长 ``` //by Judge #include<bits/stdc++.h> #define Rg register #define fp(i,a,b) for(Rg int i=(a),I=(b)+1;i<I;++i) int n; int g[1003],h[1003]; inline void solv(int n){ fp(i,1,n){ memset(h,0,(n+2)<<2); for(Rg int j=1;j<=i;j<<=1) h[g[i-j]]=1; fp(j,0,i) if(!h[j]){ g[i]=j; break; } } } int main(){ solv(1000); while(~scanf("%d",&n)) puts(g[n]?"Kiki":"Cici"); return 0; } ```