uva 1561 - Cycle Game(推理)

uva 1561 - Cycle Game(推理)

題目鏈接：uva 1561 - Cycle Game

題目大意：給出一個環，每次從起點開始，可以選擇一個權值非0的邊移動，移動後減掉權值至少1點。不能移動的為失敗。

解題思路：

• 1:有0的情況，如果有方向離權值為0的邊的步數為奇數，則為必勝；否則必敗；
• 2:無0的情況，奇數邊必勝；
• 3:有1的情況，同0的判斷一樣；
• 4:無1的情況，只剩偶數邊的情況，必敗；

  #include 
  #include 
  #include 
  
  using namespace std;
  const int maxn = 30;
  
  int N, arr[maxn];
  
  bool check (int k) {
      int p = -1;
      while (arr[++p] != k);
      int q = N;
      while (arr[--q] != k);
      q = N - 1 - q;
      return (p&1) || (q&1);
  }
  
  bool judge () {
      for (int i = 0; i < N; i++) {
          if (arr[i] == 0)
              return check(0);
      }
  
      if (N&1)
          return true;
  
      for (int i = 0; i < N; i++) {
          if (arr[i] == 1)
              return check(1);
      }
      return false;
  }
  
  int main () {
      int cas;
      scanf("%d", &cas);
      while (cas--) {
          scanf("%d", &N);
          for (int i = 0; i < N; i++)
              scanf("%d", &arr[i]);
          printf("%s\n", judge() ? "YES" : "NO");
      }
      return 0;
  }