博弈论的经典题目
2013-02-02 16:17阅读：
【做题基础】：有一个游戏叫Nim，就是有n堆石子，有两个人，当轮到其中一个人的时候，他可以拿走任意一堆石子里的任意石子个数（不可以不拿），直到最后不能操作的为败者，另一个为胜者。当只剩下两堆石子且这两堆石子的个数相等时为必败态（必胜态表示先手在这个状态下操作必胜，必败态表示先手在这个状态下操作必败。其中如果这个状态可以推到一个必败态，则这个状态为必胜态，否则这个状态为必败态）。
证明：设这两堆石子的个数为（x，x），那么如果先手在第一堆石子中取出y个石子（0 < y <=
x），那么下一个状态就是（x – y，x），后手就会在另一堆石子里面取走y个石子，状态就转移到了（x – y，x – y）。当状态到了（
1
，1）的时候，先手一定要拿走一个石子，状态转移到了（0，1），后手便取走最后一个石子取得胜利。
假设有n堆石子，如何快速求出这个状态是必胜态还是必败态呢？其实很简单，令f = stone[1] ^ stone[2] ^ ……
^ stone[n – 1] ^
stone[n]（^是异或操作），如果f为0则该状态为必败态，否则为必胜态，这样做的时间复杂度是O（n），效率十分的高。
证明：如图一。
有了这个基础，我们做下面的题目就简单了。
【题目大意】：给出一个由‘（’和‘）’组成的字符串s（len <=
1000），保证括号是匹配的，有两个人要操作，每次操作可以删去字符串的一个区间，使得这个区间是括号匹配的，问一开始这个状态是必胜态还是必败态。
【题目分析】：对于一般并列的括号如（）（（）），我们直接把1^2作为结果就行了。
对于复杂嵌套的括号如（（（））（））（），我们首先用2^1加上1（代表外层括号）得到4，再用4^1得到5，因为f=5所以此状态为必胜态。对于这些操作，我们可以用栈来实现，程序代码量比较短。
【程序代码】：#include
<fstream>
#include
<cstdio>
using namespace
std;
int query[1050];
char st[1050];
int main()
{
int T, len, now,
i;
freopen('bracket.in', 'r', stdin);
freopen('bracket.out', 'w', stdout);
scanf('%d', &T);
while
(T--)
{
memset(query, 0,
sizeof(query));
scanf('%s',
st);
len =
strlen(st);
now = 0;
for (i = 0; i < len;
i++)
if (st[i] ==
'(')
{
query[++now] = 0;
}
else
{
query[--now] ^= query[now + 1] + 1;
}
if
(query[0])
{
printf('peipei');
}
else
{
printf('iamcs');
}
}
return
0;
}
【个人心得】：自己看了关于博弈论的一些资料并做了一些例题，我便找了一道比较经典的题目来写报告，好开心啊！
