在一個2*N的格子上，Alice和Bob又開始了新游戲之旅。 

這些格子中的一些已經被涂過色，Alice和Bob輪流在這些格子里進行涂色操作，使用兩種涂色工具，第一種可以涂色任意一個格子，第二種可以涂色任意一個2*2的格子。每一輪游戲里，他們可以選擇一種工具來涂色尚未被染色的格子。需要注意，涂色2*2的格子時，4個格子都應當未被涂色。最后一步涂滿所有格子的玩家獲勝。 

一如既往，Alice先手，最優策略，誰是贏家？ 
Input輸入第一行為T，表示有T組測試數據。 
每組數據包含兩個數字，N與M，M表示有多少個已被染色的格子。接下來的M行每行有兩個數字Xi與Yi，表示已經被涂色的格子坐標。 

[Technical Specification] 

1. 1 <= T <= 74 
2. 1 <= N <= 4747 
3. 0 <= M <= 2 * N 
4. 1 <= Xi <= 2, 1 <= Yi <= N，格子坐標不會重復出現 
Output對每組數據，先輸出為第幾組數據，然后輸出“Alice”或者“Bob”，表示這輪游戲的贏家。 Sample Input
2
2 0
2 2
1 1
2 2
Sample Output
Case 1: Alice
Case 2: Bob

思路：

可以先考慮有連續n列的空格的sg值是多少。

n=0時顯然sg[0]=0，之后就是普通的sg函數打表,只不過是要將格子分區而已。

#include <iostream>#include <cstdio>#include <cstring>#include <string>#include <cmath>#include <queue>#include <algorithm>#include <vector>#include <stack>#define INF 0x3f3f3f3f#pragma comment(linker, "/STACK:102400000,102400000")using namespace std;const int maxn=5000;int sg[maxn];bool pl[2][maxn];int get_sg(int x){ if(sg[x]!=-1)  return sg[x]; bool vis[maxn]; memset(vis, false , sizeof(vis)); for(int i=0; i<=x-1-i; i++) {  int t=get_sg(i)^1^get_sg(x-1-i); //只涂這一列的其中一個格子  vis[t]=true; } for(int i=0; i<=x-2-i; i++) {  int t=get_sg(i)^get_sg(x-i-2); //這一列的格子都涂  vis[t]=true; } for(int i=0; ; i++) {  if(!vis[i])  {   sg[x]=i;   break;  } } return sg[x];}int main(){ memset(sg, -1, sizeof(sg)); sg[0]=0; for(int i=1; i<maxn; i++)  sg[i]=get_sg(i); int t; scanf("%d", &t); for(int cas=1; cas<=t; cas++) {  int n, m;  scanf("%d%d", &n, &m);  memset(pl, false, sizeof(pl));  int ans=0;  for(int i=1; i<=m; i++)  {   int x, y;   scanf("%d%d", &x, &y);   pl[--x][--y]=true;   }  int cnt=0;  for(int i=0; i<n; i++) //將格子分區  {   if(pl[0][i]&&pl[1][i])  //如果某一列的格子都涂了，那么異或這一列格子之前的連續空格子的sg值   {    ans^=sg[cnt];    cnt=0;    continue;   }   if(pl[0][i]^pl[1][i]) //如果這一列之涂了一個格子，那么異或這一列格子之前的連續空格子的sg值再異或1   {    ans=ans^sg[cnt]^1;    cnt=0;    continue;   }   cnt++;  //如果這一列沒有格子被涂，那么連續空格子的長度+1  }  ans^=sg[cnt];  if(ans)   printf("Case %d: Alice/n", cas);  else   printf("Case %d: Bob/n", cas); } return 0;}

以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持武林網之家。