🔗 C - Road Pothole Survey (awc0022_c)

tags: 前綴和(Prefix Sum)

Problem Statement

題目簡述

有 NN 塊磁磚排成一列，其中 MM 塊已損壞。
KK 輛車分別行經連續區段 [Li,Ri][L_i, R_i]，若該區段內損壞磁磚數量 ≥T\geq T，則報告為「需要維修」。> 對每輛車輸出判定結果。

Constraints

約束條件

  • 1≤N≤2×1051 \leq N \leq 2 \times 10^5
  • 1≤M≤N1 \leq M \leq N，1≤K≤2×1051 \leq K \leq 2 \times 10^5，1≤T≤N1 \leq T \leq N
  • 1≤Bi≤N1 \leq B_i \leq N，所有 BiB_i 互不相同
  • 1≤Li≤Ri≤N1 \leq L_i \leq R_i \leq N

思路：前綴和

典型的區間計數問題，用前綴和即可 O(1)O(1) 回答每筆查詢。

建立長度為 NN 的 0/1 陣列 A，損壞的位置標記為 1，再對 A 做前綴和得到 s。對於查詢 [L,R][L, R]，損壞磁磚數量為 s[R]−s[L−1]s[R] - s[L-1]，與閾值 TT 比較即可。

複雜度分析

  • 時間複雜度：O(N+M+K)\mathcal{O}(N + M + K)
  • 空間複雜度：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
from itertools import accumulate


def solve():
    N, M, K, T = map(int, input().split())
    B = list(map(int, input().split()))

    A = [0] * N
    for b in B:
        A[b - 1] = 1
    s = list(accumulate(A, initial=0))

    ans = []
    for _ in range(K):
        L, R = map(int, input().split())
        ans.append("YES" if s[R] - s[L - 1] >= T else "NO")
    print(*ans, sep="\n")


if __name__ == "__main__":
    solve()

🔗 D - Simultaneous Control of Light Bulb Panels (awc0022_d)

tags: 貪心(Greedy) 差分陣列(Difference Array)

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()

🔗 E - Delivery Driver’s Route (awc0022_e)

tags: 狀態壓縮DP(Bitmask DP) 最短路(Shortest Path) Floyd-Warshall TSP

Problem Statement

題目簡述

有 NN 個城鎮與 MM 條雙向道路。
從城鎮 11 出發，訪問所有城鎮至少各一次後回到城鎮 11。
求最短總路程；若不可能則輸出 −1-1。

Constraints

約束條件

  • 2≤N≤152 \leq N \leq 15
  • 1≤M≤N(N−1)21 \leq M \leq \frac{N(N-1)}{2}
  • 1≤Wi≤1061 \leq W_i \leq 10^6
  • 無自環、無重邊

思路：Floyd-Warshall + 狀壓 DP（TSP）

觀察：本質就是 TSP

由於可以重複經過同一條道路，而在任意兩點間移動時走最短路一定最優，因此可以先預處理所有點對的最短距離，再將問題轉化為：

問題轉化

在以最短距離為邊權的完全圖上，求從節點 00 出發、恰好訪問每個節點一次並回到起點的最短迴路——即經典的 旅行推銷員問題（TSP）。

第一步：Floyd-Warshall 全源最短路

用 Floyd-Warshall 在 O(N3)O(N^3) 內求出所有點對之間的最短距離 dist[u][v]。

若存在某個節點 uu 使得 dist[0][u] = ∞，表示從起點不可達，直接輸出 −1-1。

第二步：狀壓 DP 求解 TSP

為什麼想到狀壓 DP？

N≤15N \leq 15，這是狀壓 DP 的經典信號。用一個 NN 位元的 bitmask 表示「哪些城鎮已被訪問」，狀態數為 O(2N⋅N)O(2^N \cdot N)。

定義 dfs(u, s)：目前位於城鎮 uu，已訪問的城鎮集合為 ss（bitmask），要完成剩餘所有城鎮的訪問後回到起點的最小代價。

轉移：

dfs(u,s)=min⁡v∉s(dist[u][v]+dfs(v, s∪{v}))\text{dfs}(u, s) = \min_{v \notin s} \Big( \text{dist}[u][v] + \text{dfs}(v,\, s \cup \{v\}) \Big)

邊界：當 ss 包含所有節點時（s=2N−1s = 2^N - 1），回到起點的代價為 dist[u][0]。

初始呼叫：dfs(0, 1)，表示從節點 00 出發，初始已訪問集合為 {0}\{0\}。

複雜度分析

  • 時間複雜度：O(N3+2N⋅N2)\mathcal{O}(N^3 + 2^N \cdot N^2)。
    • Floyd-Warshall 為 N3N^3；
    • 狀壓 DP 有 2N⋅N2^N \cdot N 個狀態，每個轉移枚舉 NN 個下一步，因此為 2N⋅N22^N \cdot N^2
  • 空間複雜度：O(N2+2N⋅N)\mathcal{O}(N^2 + 2^N \cdot N)，分別為距離矩陣和 DP 記憶化表

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
from functools import cache


def solve():
    N, M = map(int, input().split())
    dist = [[float("inf")] * N for _ in range(N)]
    for u in range(N):
        dist[u][u] = 0

    for _ in range(M):
        u, v, w = map(int, input().split())
        u, v = u - 1, v - 1
        if w < dist[u][v]:
            dist[u][v] = w
            dist[v][u] = w

    # Floyd-Warshall
    for k in range(N):
        for u in range(N):
            if dist[u][k] == float("inf"):
                continue
            for v in range(N):
                dist[u][v] = min(dist[u][v], dist[u][k] + dist[k][v])

    if any(dist[0][u] == float("inf") for u in range(N)):
        print(-1)
        return

    U = (1 << N) - 1

    @cache
    def dfs(u, s):
        if s == U:
            return dist[u][0]

        res = float("inf")
        for v in range(N):
            if s & (1 << v):
                continue
            res = min(res, dist[u][v] + dfs(v, s | (1 << v)))
        return res

    print(dfs(0, 1))


if __name__ == "__main__":
    solve()

寫在最後

PROMPT

masterpiece, best quality, high quality, good quality, 32K UHD, colorful, official art, illustration, 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:makoto_shinkai:0.75), soft pastel gradients, luminous dusk glow, crisp lineart, delicate rim light, gentle bokeh, dreamy cinematic atmosphere,

1girl, solo, nakano miku, miku nakano (gotoubun no hanayome), medium hair, brown hair, hair between eyes, sidelocks, blue eyes, headphones around neck, collarbone, sleeveless summer dress, white dress with subtle teal-blue accents, front zipper detail, fitted bodice and softly flared skirt, straw sunhat with a blue ribbon and a small yellow flower, long hair draping over shoulders, small shoulder bag strap, black pantyhose, amusement park date, fairytale castle in the background, tall ornate pastel castle towers, stone walls and garden hedges, warm sunset sky, romantic evening ambience, soft ambient park lights beginning to glow, standing in the foreground, relaxed posture, slightly turning toward the viewer, gentle smile, looking at the camera, candid date-photo feeling, shallow depth of field, foreground subject sharp, background softly blurred,

This image should feel like a romantic amusement-park date at golden hour, with a storybook castle behind her and soft pastel dusk light spilling across the scene. Use a Makoto Shinkai-inspired cinematic illustration look: luminous skies, clean yet delicate linework, subtle color gradients, and gentle bokeh that makes the moment feel dreamy, tender, and full of quiet anticipation