題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 CF2183A Binary Array Game

rating: 678

Problem Statement

題目簡述

Alice 和 Bob 在 0/1 陣列上博弈。

每次選一個長度 ≥2\ge 2 的區間 [l,r][l, r] (l<rl < r)，把該區間「縮成一個數」並替換為 b=1−min⁡(al…ar)b = 1 - \min(a_l \dots a_r)（區間全為 1 則 b=0b=0，只要含 0 則 b=1b=1），因此陣列長度會變短。

剩一數時若為 0 則 Alice 勝，否則 Bob 勝。求最優策略下的勝者。

Constraints

約束條件

  • 3≤n≤1003 \le n \le 100
  • ai∈{0,1}a_i \in \{0, 1\}

思路：分類討論

關鍵性質

當輪到 Bob 且目前陣列長度 ≥2\ge 2 時，若陣列中存在 0，Bob 選整段 [1,n][1,n]，因為 min⁡=0\min=0，操作後直接縮成單一元素 11，遊戲結束且 Bob 獲勝。

這意味著 Alice 若不能在本回合直接結束並贏（把陣列縮成單一元素 0），就必須讓自己操作完後的陣列不含 0，否則 Bob 會在下一步直接獲勝。

Alice 的獲勝方式分析

考慮 Alice 在第一回合的獲勝方式，以及在什麼情況下 Alice 操作後還會有 0。

  1. 先手勝利：若原陣列 AA 中沒有 0，即全為 1，Alice 操作 [1,n][1, n] 變為 0，Alice 獲勝。
  2. 後手必敗：若原陣列 AA 中有 00，此時 Alice 先手不能操作整個陣列，否則會使 Bob 獲勝。考慮如何操作把 00 消除。
    • 若 A1=1A_1 = 1：Alice 操作 [2,n][2, n]，由於 [2,n][2, n] 中包含 0，陣列變為 [1,1][1, 1]，Bob 操作後必敗。
    • 若 An=1A_n = 1：Alice 操作 [1,n−1][1, n-1]，同理。
  3. 後手必勝：A1=0A_1 = 0 且 An=0A_n = 0。
    • 此時 Alice 既不能操作整個陣列，也不能把這兩個 00 都消除，故操作後必仍有 0，Bob 獲勝。
結論

Winner={Aliceif a1=1 or an=1Bobif a1=0 and an=0\text{Winner} = \begin{cases} \text{Alice} & \text{if } a_1 = 1 \text{ or }a_n = 1 \\ \text{Bob} & \text{if } a_1 = 0 \text{ and } a_n = 0 \end{cases}

複雜度分析

  • 時間複雜度：O(n)\mathcal{O}(n)，讀取輸入。
  • 空間複雜度：O(n)\mathcal{O}(n)，保存輸入。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def solve():
    n = int(input())
    A = list(map(int, input().split()))
    assert len(A) == n

    if A[0] == 0 and A[-1] == 0:
        print("Bob")
    else:
        print("Alice")

if __name__ == "__main__":
    t = int(input())
    for _ in range(t):
        solve()

寫在最後

PROMPT

masterpiece, best quality, high quality, good quality, 32K UHD, colorful, official art, illustration, in the style of fashion photography, dynamic, dynamic force picture, (Visual impact:1.2), impactful picture, extreme aesthetic, A shot with tension, sharp focus, The Ninth Art, depth of field, cinematic lighting, light particles, lens flare, movie perspective, (Tyndall Effect:1.4), light particles, light, shadow, scenery, temperate atmosphere, (artist:pigeon666:0.83), (Yomu:0.4), (remsrar:0.45), (quasarcake:0.3),

1girl, solo, Nijika Ijichi (ijichi nijika, bocchi the rock), brown eyes, blonde hair, long hair, very long hair, bangs, side ponytail, school uniform, white shirt, pleated skirt, long sleeves, bow, ahoge, sidelocks, outdoors, collared shirt, bowtie, black skirt, bag, red bow, red bowtie,

holding umbrella, transparent umbrella, rain, raining, night, wet street, puddle, reflection, glowing vending machine, backlighting, neon lights, urban scenery, wide shot, landscape, horizontal, looking at viewer, blush