Incredible Chess（尼姆博弈）

原题目：

You are given an n x n chess board. Only pawn is used in the 'Incredible Chess' and they can move forward or backward. In each column there are two pawns, one white and one black. White pawns are placed in the lower part of the board and the black pawns are placed in the upper part of the board.

The game is played by two players. Initially a board configuration is given. One player uses white pieces while the other uses black. In each move, a player can move a pawn of his piece, which can go forward or backward any positive integer steps, but it cannot jump over any piece. White gives the first move.

The game ends when there is no move for a player and he will lose the game. Now you are given the initial configuration of the board. You have to write a program to determine who will be the winner.

Example of a Board

Input

Input starts with an integer T (≤ 200), denoting the number of test cases.

Each case starts with an integer n (3 ≤ n ≤ 100) denoting the dimension of the board. The next line will contain n integers, W0, W1, ..., Wn-1 giving the position of the white pieces. The next line will also contain n integers, B0, B1, ... Bn-1 giving the position of the black pieces. Wi means the row position of the white piece of ith column. And Bi means the row position of the black piece of ith column. You can assume that (0 ≤ Wi < Bi < n) for (0 ≤ i < n) and at least one move is remaining.

Output

For each case, print the case number and 'white wins' or 'black wins' depending on the result.

Sample Input

2

6

1 3 2 2 0 1

5 5 5 3 1 2

7

1 3 2 2 0 4 0

3 4 4 3 1 5 6

Sample Output

Case 1: black wins

Case 2: white wins

中文概要：

• 下棋，每一列又两个棋，一个黑色，一个白色，白色先走可以向上或向下走任意步，但不能跳过对面旗子下棋
• 无法下一步是停止。 

• 用到的概念：

  有若干堆石子，每堆石子的数量都是有限的，合法的移动是“选择一堆石子并拿走若干颗（不能不拿）”， 如果轮到某个人时所有的石子堆都已经被拿空了，则判负（因为他此刻没有任何合法的移动）：对于一个Nim游戏的局面(a1,a2,...,an)，它是先手必败态为当且仅当a1^a2^...^an=0，其中^表示异或(xor)运算。

  #include<bits/stdc++.h>
  using namespace std;
  int t,n,w[223],b[221],ans;
  int main()
  {
      scanf("%d",&t);
      for(int q=1; q<=t; q++)
      {
          scanf("%d",&n);
          printf("Case %d: ",q);
          for(int i=1; i<=n; i++)
              scanf("%d",&w[i]);
          for(int i=1; i<=n; i++)
              scanf("%d",&b[i]);
          ans=0;
          for(int i=1; i<=n; i++)
              ans^=(b[i]-w[i]-1);
          if(ans==0)printf("black wins\n");
          else printf("white wins\n");
      }
      return 0;
  }
             

• 这个任意步类似与NIM博弈的每一堆可以取任意个，（也许会有往后退的情况，但那些情况都不利于它赢。
• 也就是说往后退是一个无用的策略，那忽略掉往后退，只剩下中间的空格就是 b[i]-w[i]-1）然后取异或判断即可
• 日常不看解析想不出来系列。。。。