【做题基础】：有一个游戏叫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），效率十分的高。

证明：如图一。

http://s3/mw690/9a718e38g7bac30d09722&690

有了这个基础，我们做下面的题目就简单了。

【题目大意】：给出一个由‘（’和‘）’组成的字符串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\n", &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\n");

          }   else

          {

              printf("iamcs\n");

          }

    }

    return 0;

}

【个人心得】：自己看了关于博弈论的一些资料并做了一些例题，我便找了一道比较经典的题目来写报告，好开心啊！