🔗 AWC0022D Simultaneous Control of Light Bulb Panels

Problem Statement

題目簡述

NN 個燈泡排成一列，初始狀態為 AiA_i（00 亮、11 暗）。
每次操作可選一個位置 ii，將連續 KK 個燈泡 [i,i+K−1][i, i+K-1] 全部切換。
求最少幾次操作讓所有燈泡亮起，或判斷不可能。

Constraints

約束條件

  • 1≤N≤2×1051 \leq N \leq 2 \times 10^5
  • 1≤K≤N1 \leq K \leq N
  • Ai∈{0,1}A_i \in \{0, 1\}

思路：貪心 + 差分陣列

貪心策略

從左到右掃描，遇到暗的燈泡就立刻翻轉以 ii 為起點的連續 KK 個燈泡。這是唯一的選擇——因為 ii 左邊的位置已經處理完畢，不會再有操作能覆蓋到 ii。若掃到某個暗燈泡時已經無法放下長度 KK 的區間（i>N−Ki > N - K），則無解。

用差分追蹤翻轉效果

貪心的瓶頸在於：每次翻轉影響 KK 個位置，暴力修改是 O(NK)O(NK)。
但翻轉操作本質上就是對狀態做 XOR，可以用差分陣列維護區間操作：

  • 維護一個累積翻轉狀態 s，在位置 ii 時先 s ^= diff[i] 取得當前的翻轉奇偶性。
  • 若 x ^ s == 1（該燈泡實際是暗的），執行翻轉：s ^= 1。操作區間為 [i, i+K−1][i,\, i+K-1]，因此在 diff[i+K] 打上標記，即再 XOR 一次。

也算是很經典的套路了。

複雜度分析

  • 時間複雜度：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
15
16
17
18
19
20
21
22
def solve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    diff = [0] * N
    ans = s = 0
    for i, x in enumerate(A):
        s ^= diff[i]
        if x ^ s == 1:
            if i <= N - K:
                ans += 1
                s ^= 1
                if i + K < N:
                    diff[i + K] ^= 1
            else:
                ans = -1
                break
    print(ans)


if __name__ == "__main__":
    solve()