E. Array Game 解析(思維、博弈、雙指標)

今天我們來看看CF1600E 題目連結

題目描述

Alice 和 Bob 玩一個遊戲。他們有一個長度為 $N$ 的數組 $A$，並需要共同建立一個嚴格遞增的序列。
每回合，玩家可以從數組的左端或右端移除一個數，然後將其添加到序列中。
Alice 先手，最後能夠成功移除並加入數列的人獲勝。
假設兩人都採取最優策略，請判斷誰會贏得比賽。

輸入格式

• 第一行：整數 $N$（$1 \leq N \leq 2 \times 10^5$），表示數組的長度。
• 第二行：$N$ 個整數 $A_1, A_2, …, A_N$（$0 \leq A_i \leq 10^9$）。

輸出格式

• 輸出一行，若 Alice 獲勝則輸出 "Alice"，否則輸出 "Bob"。

前言

原本我還以為只要簡單判斷一次或兩次哪一個遞增序列比較長就好，沒想到要用到雙指標

想法

首先一開始可以注意到，頭和尾都只會有一個嚴格遞增序列，不管中間還有多少個遞增序列，我們都完全不可能使用到，因為要使用中間的序列，必定要先用掉頭或者尾的。
接著我們可以注意到，如果我現在是先手，如果有一個數字開頭比較大的序列(例如左邊的序列是[1,3,5]，右邊的序列反過來看是[2,4,6]，那右邊的序列的第一個數字2比左邊的序列的第一個數字1大)，那我只要先手去拿那個數字，對方就不可能拿另外一邊的序列的數字，而必定被鎖死在目前這個序列中，只要我能確認這個序列的長度是奇數，我先手拿就一定會贏。
但是如果這個序列的長度是偶數，我先手拿了就一定會輸，那麼我們就只能先去拿另外一個數字比較小的序列，然後將先後手swap一下，再做一次上面的判斷即可。

程式碼:

const int _n = 2e5 + 10;
int t, n, a[_n];
VI seqL, seqR;
main(void) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  rep(i, 0, n) {
    cin >> a[i];
  }
  seqL.pb(a[0]);
  rep(i, 1, n) {
    if (a[i] <= a[i - 1]) break;
    seqL.pb(a[i]);
  }
  seqR.pb(a[n - 1]);
  per(i, 0, n - 1) {
    if (a[i] <= a[i + 1]) break;
    seqR.pb(a[i]);
  }
  string first = "Alice", second = "Bob";
  int lenL = SZ(seqL), lenR = SZ(seqR);
  int idxL = 0, idxR = 0;
  while (1) {
    if (idxR == SZ(seqR)) {
      if (lenL % 2 == 1) {
        cout << first << '\n';
        return 0;
      } else {
        cout << second << '\n';
        return 0;
      }
    }
 
    if (seqL[idxL] < seqR[idxR]) {
      swap(seqL, seqR);
      swap(lenL, lenR);
      swap(idxL, idxR);
    }
    if (lenL % 2 == 1) {
      cout << first << '\n';
      return 0;
    }
    if (seqL[idxL] == seqR[idxR] and (lenL % 2 == 1 or lenR % 2 == 1)) {
      cout << first << '\n';
      return 0;
    }
 
    idxR++;
    lenR--;
    swap(first, second);
  }
 
  return 0;
}

標頭、模板請點Submission看 Submission