前言:近期刚学了博弈论相关的内容,感觉博弈论相比数论还是更形象一点,更好理解(对从0到1开创理论的前辈们表示大大尊敬!!)。特别是SG函数的相关理论,学完后以前很多要扎耳挠腮一两个小时的题都能秒出,这种感觉太妙了!当然博弈论还是很深奥很广泛的东西(报以敬畏),我也只停留在入门水平。本篇博客就总结一下这几天学习的一些知识,以后遇到新的理论慢慢补充吧!
一堆n个物品,两个人轮流从这堆物品中取物, 规定每次取[1,m]个,最后取光者得胜,问先手必胜还是后手必胜。
我们先讲一个具体的例子:两个人在一堆n个石子里拿至少1个至多3个石子,轮流拿,问先手必胜还是后手必胜。
很容易可以知道无论先手拿几个,后手都可以拿若干个石子把两次拿的石子个数控制在4个(因为每次只能拿1-3个石子,先手拿1个后手拿3个,先手2个后手2个…必定保证两次为4个),那么可以很好地得出结论:如果n%4 == 0
则后手必胜(先手不管怎么拿后手都可以控制数量使石子总数-4,那么如果石子总数是4的倍数,那肯定可以在轮到后手的某次刚好取完所以石子)。
由此,我们有特例推及一般:如果n%(m+1) == 0
则后手必胜,否则先手必胜。
HDU1846 Brave Game 就是粗暴的套模板,代码:
#include<iotream>
using namespace std;
int main()
{
int t,n,m;
cin>>t;
while(t--)
{
cin>>n>>m;
if(n%(m+1) != 0)
printf("first\n");
else
printf("second\n");
}
return 0;
}
HDU4764 Stone(巴什博弈拓展——取完石子输) – 题意:两人在白板上写数字,若一个人写了数字X,则第二个人写的数字Y要满足1 <= Y – X <= k,且第一次写的数字要满足在[1, k]内,先写到数字N的人输。
(n-1)%(m+1) == 0
则后手必胜。
#include<iotream>
using namespace std;
int main()
{
int t,n,m;
cin>>t;
while(t--)
{
cin>>n>>m;
if((n - 1) % (m + 1) != 0)
printf("first\n");
else
printf("second\n");
}
return 0;
}
没有特定的描述,只能算一种博弈思想吧(感觉用到了零和思维),一般题目数据都是首位相连的一个环,直接放例题感受吧。
HDU – 3951 Coin Game 题意:两个玩家用一圈N个硬币开始游戏。他们轮流从圆圈里取硬币,每次可以取1~k个连续的硬币。(假设10个硬币从1到10,k等于3,因为1和10是连续的,你可以拿走连续的10、1、2,但是如果2被拿走,你不能拿走1、3、4,因为1和3不是连续的)。拿最后一枚硬币的玩家获胜。 思路:当一次能取完时,先手必胜。当k=1,n是奇数时,先手必胜。其他时,后手必胜。在k=1时,双方轮流取一枚,奇数时,先手必胜,偶数时,后手必胜。在k>1时,先手能一次取完,先手必胜,否则后手必胜。开始时,硬币是一圈,先手取完后,变成一列,后手只要取1-2个让这一列变成偶数个即可,然后将这一列从中间分开成两列(镜像),之后先手如何操作,后手就在另一列如何操作,后手必胜。
#include <stdio.h>
int main()
{
int t,i,n,k;
scanf("%d",&t);
for( i=1;i<=t;++i )
{
scanf("%d%d",&n,&k);
printf("Case %d: ",i);
if( k==1 )
{
if( n&1 ) printf("first\n");
else printf("second\n");
}
else if( n<=k ) printf("first\n");
else printf("second\n");
}
return 0;
}
中国有一种游戏称为“拈(Nim)”,游戏规则是给出n列珍珠,两人轮流取珍珠,每次在某一列中取至少1颗珍珠,但不能在两列中取。最后拿光珍珠的人输。后经由被贩卖到美洲的奴工们外传,辛苦的工人们,在工作闲暇之余,用石头玩游戏以排遣寂寞。后来流传到高级人士,则用便士(Pennies),在酒吧柜台上玩。最有名的玩法,是把十二枚便士放成3、4、5三列,拿光铜板的人赢。后来,大家发现,先取的人只要在3那列里取走2枚,变成了1、4、5,就能稳操胜券了,游戏也就变得无趣了。于是大家就增加列数,增加铜板的数量,这样就让人们有了毫无规律的感觉,不易于把握。直到本世纪初,哈佛大学数学系副教授查理士•理昂纳德•包顿(Chales Leonard Bouton)提出一篇极详尽的分析和证明,利用数的二进制表示法,解答了这个游戏的一般法则,故Nim游戏的解法也称为Bouton’s Theorem。
有 n 堆石子,第 i 堆石子有 a_i 个,每次可以从某一堆中取走若干个,先后手轮流取,最后无石子可取的人负。
将n堆石子每堆石子的数量求异或和(ans = a[1] ^ a[2] ^ … ^a[n]),若ans == 0
,先手必败,否则先手必胜。
首先明确这类博弈的最终状态是每堆石子数量都为0,此时异或和也为0。 我们假设某个时刻a_1 ^ a_2 ^ a_3 ^ … ^ a_n = k ≠ 0,设k二进制数1的最高位在p位,那么一定存在一个数 a_t 的二进制 1 的最高位也在 p 位。易得 a_t ^ k < a_ta_t 最高位和 k 的最高位都为 1 ,异或为 0 则必然小于 a_t )那么从 a_t 中拿掉 a_t – a_t ^ k个石子的操作一定合法(大于 0 且小于 k )那么第 t 堆石子的数量变为 a_t – (a_t – a_t ^ k) = a_t ^ k ,这个数和其余石子的异或和为0(k^k=0)。此时,下一个人无论怎么拿石子,都会使得异或和不为0,因为至少拿一个就会使其中一个数的二进制发生变化使得异或和不为0。 由上面推导我们有两个结论:1.异或和不为0时一定有办法使异或和变为0。2.异或和为0时无论怎么操作都会使异或和不为0。 由于000000….为游戏的最终状态,其异或和也为0,反向往回推——00000为输的状态,异或和为0,前一个状态异或和不确定但保证存在可能异或和不为0的状态(结论1反推),由于决策者绝对聪明故前一种状态一定为异或和不为0(因为此时异或和不为0下一次异或和必为0且由于是最后一次所以下一个人必输),再往前推,前一种状态一定为异或和为0 的状态(结论2),反复往前推就可以得到,若初始状态的异或和不为0,则先手的必胜,否则先手必输。 画图解释(字有点小丑):
上图可以看成一个DAG图(有向无环图),然后XOR=0的点其实就是P点,XOR≠ 0的点为N点,PN点是交替出现的(决策者都很聪明的情况下,毕竟可能有傻子会在必胜的时候选择了必败的状态),这也符合:P点的下一个点必然为N点,P点一定有办法经过合法操作后变为N点,可以好好体会理解PN状态的妙处。
若游戏规则变为 有 n 堆石子,第 i 堆石子有 a_i 个,每次可以从最多k堆中取走m个,先后手轮流取,最后无石子可取的人负,如何考虑?
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define LL long long
using namespace std;
const int maxn = 1e5 + 10;
const double PI = acos(-1.0);
int n, m, l, r;
int sg[41];
int ans[41];
int main(int argc, char const *argv[]) {
while (cin >> n >> m >> l >> r) {
int Max = l / (2 * PI * r);
for (int i = 1; i <= n; i++) {
scanf("%d", sg + i);
sg[i] = sg[i] / (2 * PI * r) + 1;
sg[i] %= Max + 1;
}
memset(ans, 0, sizeof(ans));
for (int i = 1; i <= n; i++) {
int x = sg[i];
int cnt = 0;
while (x) {
ans[cnt++] += x % 2;
x /= 2;
}
}
int i;
int x = 32;
for (i = 0; i < x; i++) {
printf("i=%d ans=%d x=%d\n", i, ans[i],x);
if (ans[i] % (m + 1)) break;
}
if (i < 32)
puts("Alice");
else
puts("Bob");
}
return 0;
}
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define LL long long
using namespace std;
const int maxn = 1e5 + 10;
int main(int argc, char const *argv[]) {
int n;
int a[1001];
while (cin >> n && n) {
int ans = 0;
for (int i = 0; i < n; ++i) {
cin >> a[i];
ans ^= a[i];
}
if (!ans)
cout << '0' << endl;
else {
int cnt = 0;
for (int i = 0; i < n; ++i) {
if (a[i] > (ans ^ a[i])) cnt++;
}
cout << cnt << endl;
}
}
return 0;
}
显然,由定义可知:
假设有7个石子 ,每次只能取1,3,4个石子,先取完石子的获胜。下面给出每个状态的SG值:
所以可以得出此情况先手必输。
int sg[maxn];
int a[maxn];//存的是每回合可选的操作
int get_sg(int x) {
if(sg[x] != -1) return sg[x];//记忆化优化时间复杂度
bool vis[2100];//用于记录当前状态的可达状态的sg值
memset(vis, 0, sizeof(vis));
for(int i = 1; i <= n; i++) {//n为可选操作的个数
if(x-a[i] >=0)//将所有当前状态可达状态记录下来
vis[get_sg(x-a[i])] = 1;
}
for(int i = 0;;i++) if(!vis[i]) return sg[x] = i;//记忆化存下每个状态的sg,这里的循环实现mex函数
}
对于多个ICG游戏 ,我们可以将其合并为一个更大的ICG游戏,合并后的g(x)为每个小游戏sg的异或和。这里可以考虑Nim游戏,把每个小游戏看成一堆石子,多个小游戏的sg值就是将其异或起来,这里其实也能看出,Nim游戏就是一种特殊的SG,每堆石子的sg值就是石子个数。
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define LL long long
using namespace std;
const int maxn = 1e5+10;
int sg[2010];
int get_sg(int x) {
if(x <= 0) return 0;
if(sg[x] != -1) return sg[x];
bool vis[2100];
memset(vis, 0, sizeof(vis));
for(int i = 1; i <= x; i++) {
vis[get_sg(i-3)^get_sg(x-i-2)] = 1;
}
for(int i =0;;i++) if(!vis[i]) return sg[x] = i;
}
int main(int argc, char const *argv[]) {
int n;
cin >> n;
memset(sg, -1, sizeof(sg));
if(get_sg(n)) puts("1");
else puts("2");
return 0;
}
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define LL long long
using namespace std;
const int maxn = 1e5 + 10;
int sg[210][210];
int vis[310];
int n, m;
int get_sg(int x, int y) {
if (sg[x][y] != -1) return sg[x][y];
for (int i = 2; i <= x - i; i++) {
vis[get_sg(i, y) ^ get_sg(x - i, y)] = 1;
}
for (int i = 2; i <= y - i; i++) {
vis[get_sg(x, i) ^ get_sg(x, y - i)] = 1;
}
for (int i = 0;; i++) {
if (!vis[i]) return sg[x][y] = i;
}
}
int main(int argc, char const *argv[]) {
memset(sg, -1, sizeof(sg));
while (cin >> n >> m) {
memset(vis, 0, sizeof(vis));
if (get_sg(n, m))
cout << "WIN" << endl;
else
cout << "LOSE" << endl;
}
return 0;
}
CodeForces 138D World of Darkraft 题意:有一个 n × m 的棋盘,每个点上标记了 L; R; X 中的一个每次能选择一个没有被攻击过的点 (i; j),从这个点开始发射线,射线形状为: 若字符是 L,向左下角和右上角发,若字符是 R,向左上角和右下角发,若字符是 X,向左下左上右下右上发,遇到被攻击过的点停下来,如果轮到的人无法操作(全部点都被破坏)则输。 分析: – 1.由于激光的特性,单数和双数的格子相互不受影响,所以将棋盘分成单双两部分,即两个子问题,如图:
如果不划分的话黑线激光会影响到白线激光,实际是不影响的。
– 2 激光的方向是与坐标轴成45°的,为了方便处理,将棋盘顺时针旋转45°。坐标(x,y)被映射为(x+y, x-y+W),于是射线分割的结果就是矩形而不是三角形或不规则的多边形了。
代码:
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define LL long long
using namespace std;
const int maxn = 50;
int n, m;
int sg[maxn][maxn][maxn][maxn][2];
char mp[maxn][maxn];
int get_sg(int x1, int y1, int x2, int y2, int op) {
if (sg[x1][y1][x2][y2][op] != -1) return sg[x1][y1][x2][y2][op];
int vis[100];
memset(vis, 0, sizeof(vis));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (((i + j) & 1) != op) continue;
int x = i - j + m, y = i + j;
if (x < x1 || x > x2 || y < y1 || y > y2) continue;
int sgg = 0;
if (mp[i][j] == 'L') {
sgg = get_sg(x1, y1, x2, y - 1, op) ^
get_sg(x1, y + 1, x2, y2, op);
} else if (mp[i][j] == 'R') {
sgg = get_sg(x1, y1, x - 1, y2, op) ^
get_sg(x + 1, y1, x2, y2, op);
} else if (mp[i][j] == 'X') {
sgg = get_sg(x1, y1, x - 1, y - 1, op) ^
get_sg(x1, y + 1, x - 1, y2, op) ^
get_sg(x + 1, y1, x2, y - 1, op) ^
get_sg(x + 1, y + 1, x2, y2, op);
}
vis[sgg] = 1;
}
}
for (int i = 0;; i++) {
if (vis[i] == 0) {
sg[x1][y1][x2][y2][op] = i;
return i;
}
}
}
int main() {
scanf("%d%d", &n, &m);
memset(sg, -1, sizeof(sg));
for (int i = 0; i < n; i++) {
scanf("%s", mp[i]);
}
int ans = get_sg(0, 0, n + m - 1, n + m - 1, 0) ^
get_sg(0, 0, n + m - 1, n + m - 1, 1);
if (ans)
printf("WIN\n");
else
printf("LOSE\n");
return 0;
}
部分题目数据量较小,可以用dp思想直接枚举所有的可能然后暴力求解,这里有时候可能会用到状态压缩,或者还有一种题型为打表找规律,下面附上几道例题。
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define LL long long
using namespace std;
const int maxn = 1e5+10;
int dp[1<<16];
int a[20], n;
bool check(int x) {//检查数字x所代表的状态下数组是否递增了
int p = 0;
for(int i = 0;i < n; i++) {
if(x&(1<<i)) {//遍历x每一位二进制数
if(p >= a[i])
return 0;
p =a[i];
}
}
return 1;
}
bool dfs(int x) {
if (check(x)) return dp[x] = 0;
if (dp[x] != -1) return dp[x];
for (int i = 0; i < n; i++) {//依次去掉每一个还存在于数组中的数字
if (x&(1<<i)) {
if(!x&(1<<i-1)) continue;
if(!dfs(x^(1<<i))) return dp[x] = 1;
}
}
return dp[x] = 0;
}
int main(int argc, char const *argv[]) {
int t;
cin >> t;
while(t--) {
memset(dp, -1, sizeof(dp));
cin >> n;
for(int i = 0; i < n ;i++) {
cin >> a[i];
}
if(dfs((1<<n)-1))//1<<n的二进制为10000...(n个0),-1则为1111...(n个1)表示所有数都没被取的状态
cout << "Alice\n";
else
cout << "Bob\n";
}
return 0;
}
URAL 2104 Game with a Strip(暴力)
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define LL long long
using namespace std;
const int maxn = 5e5+10;
char s[maxn];
int dfs(int l, int r, int n, int flag) {
if(n % 2 == 0 && ((n/2)&1)) {
int a = 0, b = 0;
for(int i = l;i <= r;i++) {
if(s[i] == 'A') a++;
else b++;
}
if(a == n) return 1;
else if(b == n) return -1;
else return 0;
}
int mid = (l+r)/2;
int t1 = dfs(l, mid, n/2, flag^1);
int t2 = dfs(mid+1, r, n/2, flag^1);
if(flag) return max(t1, t2);
return min(t1, t2);
}
int main(int argc, char const *argv[]) {
int n;
cin >> n;
if(n&1) {
int a = 0, b = 0;
cin >> s;
for(int i = 0;i < n;i++) {
if(s[i] == 'A') a++;
else b++;
}
cin >> s;
for(int i = 0;i < n;i++) {
if(s[i] == 'A') a++;
else b++;
}
if(a == 2*n) puts("Alice");
else if(b == 2*n) puts("Bob");
else puts("Draw");
}
else {
int t1, t2;
cin >> s;
t1 = dfs(0, n-1, n, 0);
cin >> s;
t2 = dfs(0, n-1, n, 0);
t1 = max(t1, t2);
if(t1>0) puts("Alice");
else if(t1 == -1) puts("Bob");
else puts("Draw");
}
return 0;
}
#include<iostream>
#include<cstring>
#include <cstdio>
using namespace std;
int main()
{
int y,m,d , t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d",&y,&m,&d);
if((m+d)%2==0 || m==9 && d==30 || m==11 && d==30) printf("YES\n");
else printf("NO\n");
}
return 0;
}