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

🔗 CF2178A Yes or Yes

rating: 516

Problem Statement

題目簡述

給定一個由 ‘Y’ (Yes) 和 ‘N’ (No) 組成的字串 $s$ 。
你可以重複執行以下操作：選取相鄰兩個字元，將它們替換為它們的邏輯 OR 結果（ $Y \lor N = Y, N \lor N = N$ ）。
限制：不能選取兩個 ‘Y’ 進行合併（即禁止 “YY” $\to$ “Y”）。
請問是否能在不違反限制的情況下，將字串縮減為單一字元？

Constraints

約束條件

$2 \le |s| \le 100$
$s_i \in \{\mathtt{Y}, \mathtt{N}\}$

思路：貪心

由於 $Y \lor Y$ 操作是禁止的，且其他操作不會改變 $Y$ 的數量，故可以得知 $Y$ 的數量是無法減少的。

因此，若初始字串中有超過 1 個 $Y$ ，我們永遠無法將其減少到只剩 1 個字元。
反之，若 $Y$ 的數量 $\le 1$ ，我們總是可以透過消除相鄰的 $N$ 來縮減字串。

結論

計算字串中 $Y$ 的出現次數。如果不超過 1 次，輸出 YES，否則輸出 NO。

複雜度分析

時間複雜度： $\mathcal{O}(|s|)$ ，只需遍歷一次字串計算 $Y$ 的數量。
空間複雜度： $\mathcal{O}(|s|)$ 。

Code

def solve():
    s = input().strip()
    print("YES" if s.count('Y') <= 1 else "NO")

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

寫在最後

PROMPT

這裡什麼都沒有。