UVA10561 Treblecross —

UVA10561 Treblecross —— SG博弈

题目链接：https://vjudge.net/problem/UVA-10561
题意：
两个人玩游戏，轮流操作：每次往里面添加一个X，第一个得到XXX的获胜。
题解：
详情请看《训练指南》P139，以及代码注释。
代码如下：
  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #include <vector>
  6 #include <cmath>
  7 #include <queue>
  8 #include <stack>
  9 #include <map>
 10 #include <string>
 11 #include <set>
 12 using namespace std;
 13 typedef long long LL;
 14 const int INF = 2e9;
 15 const LL LNF = 9e18;
 16 const int MOD = 1e9+7;
 17 const int MAXN = 1e3+10;
 18 
 19 int SG[MAXN], vis[MAXN];
 20 bool hav[MAXN]; //是否有‘X'
 21 
 22 void getSG()    //SG[Len]：'.'连续长度为Len时，往其中放一个'X'的游戏的SG值。
 23 {
 24     SG[0] = 0;  //长度为0时，没有后继状态，故SG[0] = mex{} = 0;
 25     //长度为1、2、3时的后继状态为0， 故SG[1/2/3] = mex{SG[0]} = 1,之所以单独拿出来，是因为
 26     //他们的求法与后面的不一样。
 27     SG[1] = SG[2] = SG[3] = 1;
 28     for(int Len = 4; Len<MAXN; Len++)
 29     {
 30         memset(vis, 0, sizeof(vis));
 31         for(int pos = 1; pos<=(Len+1)/2; pos++)
 32         {
 33             //当放了一个'X'进去之后，原先的游戏因为禁区的出现而可能被分为两个子游戏。
 34             int val = SG[Len-pos-2];
 35             if(pos>3) val ^= SG[pos-3];
 36             vis[val] = 1;
 37         }
 38         for(int j = 0;;j++) if(!vis[j]){
 39             SG[Len] = j;
 40             break;
 41         }
 42     }
 43 }
 44 
 45 int len, ans[MAXN];
 46 bool oneHit(int pos)    //判断在pos位置能否放置一个X然后赢得游戏
 47 {
 48     if(hav[pos]) return 0;
 49     if(pos<=len-2&&hav[pos+1]&&hav[pos+2]) return 1;
 50     if(pos>=3&&hav[pos-1]&&hav[pos-2]) return 1;
 51     if(pos!=1&&pos!=len&&hav[pos-1]&&hav[pos+1]) return 1;
 52     return 0;
 53 }
 54 
 55 bool prohibit(int pos)  //判断pos是否在禁区之内
 56 {
 57     return  hav[pos]||(pos>=2&&hav[pos-1])||(pos>=3&&hav[pos-2])||
 58            (pos<=len-1&&hav[pos+1])||(pos<=len-2&&hav[pos+2]);
 59 }
 60 
 61 int getVAL()    //得到整个游戏的SG异或和
 62 {
 63     int val = 0, L = 0;
 64     for(int i = 1; i<=len; i++)
 65     {
 66         if(prohibit(i)) val ^= SG[L], L = 0;
 67         else L++;
 68     }
 69     val ^= SG[L];
 70     return val;
 71 }
 72 
 73 void solve()
 74 {
 75     ans[0] = 0;
 76     for(int i = 1; i<=len; i++) if(oneHit(i)) { //首先判断先手是否能“一击毙命”
 77         ans[++ans[0]] = i;
 78         for(++i; i<=len; i++)
 79             if(oneHit(i)) ans[++ans[0]] = i;
 80         return;
 81     }
 82     if(getVAL())    //否则，则利用SG来判断输赢
 83     {
 84         for(int i = 1; i<=len; i++) if(!prohibit(i)){
 85             hav[i] = true;  //因为先手处于必胜状态，当先手走了一步之后，就轮到后手处于必败状态。
 86             if(!getVAL()) ans[++ans[0]] = i;
 87             hav[i] = false;
 88         }
 89     }
 90 }
 91 
 92 char str[MAXN];
 93 int main()
 94 {
 95     getSG();
 96     int T;
 97     scanf("%d", &T);
 98     while(T--)
 99     {
100         scanf("%s", str+1);
101         len = strlen(str+1);
102         memset(hav, 0, sizeof(hav));
103         for(int i = 1; i<=len; i++)
104             hav[i] = (str[i]=='X');
105 
106         solve();
107         if(!ans[0])
108             printf("LOSING

");
109         else
110         {
111             printf("WINNING
");
112             for(int i = 1; i<ans[0]; i++)
113                 printf("%d ", ans[i]);
114             printf("%d
", ans[ans[0]]);
115         }
116     }
117 }
View Code