UVA 11249 Game：Wythoff 遊戲變種與必敗態預計算

問題描述

兩堆石子 (a, b)，a ≤ b。每次操作：

• 任取一堆，拿任意多個（≥1）
• 或同時取兩堆，但兩堆拿取數量之差 ≤ k
• 無法操作者負。先手是否必勝？

  必敗態規律

  設 (x, y) 為必敗態（x < y）。已知 (1, k+2) 是必敗態。後續必敗態遞推：

  pre = 1
  for i = 2..100000:
      if lose[i] 已定義: continue
      tmp = lose[pre] + (i - pre) + k + 1
      lose[i] = tmp; lose[tmp] = i
      pre = i

  原理：新必敗態 (i, tmp) 滿足：從它出發的任何合法移動都無法到達前一個必敗態 (pre, lose[pre])，而對手總能移動到該必敗態。

  參考代碼（C++）

  #include <cstdio>
  #include <cstring>
  #include <algorithm>
  using namespace std;
  
  const int N = 100005;
  int lose[N];
  
  void init(int k) {
      memset(lose, 0, sizeof(lose));
      lose[1] = k + 2; lose[k+2] = 1;
      int pre = 1;
      for (int i = 2; i <= 100000; i++) {
          if (lose[i]) continue;
          int tmp = lose[pre] + i - pre + k + 1;
          if (tmp > 100000) break;
          lose[i] = tmp; lose[tmp] = i;
          pre = i;
      }
  }
  
  int main() {
      int T; scanf("%d", &T);
      while (T--) {
          int k, q; scanf("%d%d", &k, &q);
          init(k);
          while (q--) {
              int a, b; scanf("%d%d", &a, &b);
              if (a > b) swap(a, b);
              puts(lose[a] == b ? "LOSING" : "WINNING");
          }
          puts("");
      }
      return 0;
  }

  複雜度分析

  • 預計算：O(max_a)，max_a = 100,000
  • 每查詢：O(1)
  • 多測試用例共享預計算（若 k 相同可緩存）

  關鍵洞察

  1. 這是 Wythoff 遊戲的推廣（k=0 時退化為標準 Wythoff）
  2. 必敗態成對出現，且差值單調遞增
  3. 預計算所有必敗態，查詢極快