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

🔗 CF2178B Impost or Sus

rating: 762

Problem Statement

題目簡述

給定一個僅由 s 和 u 組成的字串 $r$ ，定義 suspicious 字串需滿足：

字母 s 至少出現兩次
對於每個 u，其左右最近的兩個 s 到它的距離相等

每次操作可將任意位置的字元變為 s，求最少操作次數使 $r$ 成為 suspicious 字串。

Constraints

約束條件

$3 \le |r| \le 2 \times 10^5$
$r_i \in \{\mathtt{s}, \mathtt{u}\}$

思路：貪心分隔連續 u

等價條件推導

考慮 suspicious 字串中任意一個位於位置 $i$ 的 u。設其左右最近的 s 距離皆為 $d$ ，則這兩個 s 必分別位於 $w_{i-d}$ 與 $w_{i+d}$ 。由此可推導出 suspicious 字串的充要條件：

首尾字元為 s
不存在相鄰的 u

詳細推導

首尾必須是 s：若 u 位於端點，則有一側必定不存在 s，無法滿足「兩側等距」。
每個 u 的鄰居都必須是 s：
- u 兩側皆為 s（如 sus）→ 兩側最近 s 距離皆為 $1$ ，合法 ✓
- u 一側為 s、一側為 u（如 suus 的左側 u）→ 距離分別為 $1$ 和 $2$ ，不等距 ✗
- u 兩側皆為 u（如 suuus 的中間 u）→ 中間 u 本身可能等距，但該連續段的其他 u 必屬於上一情況，仍不合法 ✗

貪心策略

處理邊界：若首尾為 u，需將其改為 s。
處理中間：對每段長度為 $k$ 的連續 u，破壞其連續性需 $\lfloor \dfrac{k}{2} \rfloor$ 次操作。

為何此策略最優？

將一段連續 $k$ 個 u（形如 $\mathtt{s}\underbrace{\mathtt{uu \cdots u}}_{k}\mathtt{s}$ ）的相鄰 u 兩兩配對：

\mathtt{s} \ {\color{red}\underline{\mathtt{uu}} \ \underline{\mathtt{uu}} \ \mathtt{u}} \ \mathtt{s}

每對中至少需將一個 u 改為 s，否則該對仍相鄰。故操作下界為 $\lfloor \dfrac{k}{2} \rfloor$ 。

而將每對中的第二個 u 改為 s，便可恰好達到此下界。

複雜度分析

時間複雜度： $\mathcal{O}(n)$ 。
空間複雜度： $\mathcal{O}(n)$ 。

Code

from itertools import groupby

def solve():
    r = list(input().strip())
    n = len(r)
    ans = 0

    if r[0] == 'u':
        r[0] = 's'
        ans += 1
    if r[n - 1] == 'u':
        r[n - 1] = 's'
        ans += 1
    for c, lst in groupby(r):
        if c == 'u':
            ans += len(list(lst)) // 2
    print(ans)

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

寫在最後

PROMPT

這裡什麼都沒有。