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

🔗 P2882 [USACO07MAR] Face The Right Way G

Problem Statement

題目簡述

有 $N$ 頭牛排成一列，每頭牛朝前（F）或朝後（B）。

每次操作可以選定一個長度 $K$ $(1 \le K \le N)$ ，並將連續 $K$ 頭牛全部翻轉（F 變 B，B 變 F）。

目標是讓所有牛都朝前。
求最小的 $K$ 值，使得在該 $K$ 下所需操作次數最少；若有多個 $K$ 達到相同最少操作次數，則輸出最小的 $K$ 。

Constraints

約束條件

$N \le 5000$
每頭牛的初始方向為 F 或 B

思路：枚舉區間長度與貪心翻轉

一個貪心的做法是從左到右掃描牛群，當遇到第一頭朝後的牛時，立即以它為起點翻轉 $K$ 頭牛。

這樣的策略是合理的，因為如果不在第一時間翻轉，這頭牛將永遠無法被翻轉回來（後續的翻轉區間只會向右移動，不可能再回到這個位置）。因此，我們可以確定每當我們處理到位置 $i$ 時，所有在它左邊的牛都已經處理完畢且方向確定為 F，此時如果第 $i$ 頭牛是 B，就只能以它為起點翻轉。

差分加速：用標記記住還原點

然而，直接模擬翻轉的陣列變化太慢，每操作一次就得改 $K$ 個位置，最終會達到 $O(N^2 K)$ 甚至 $O(N^3)$ ，完全無法承受。

我們可以利用差分陣列來加速這一過程，由於翻轉兩次會回到原狀，我們只需要記錄翻轉的奇偶性即可。

維護一個差分陣列 $\textit{diff}[0..N]$ ，當我們在位置 $i$ 翻轉時，將 $\textit{diff}[i]$ 反轉（diff[i] ^= 1），同時在位置 $i+K$ 記錄一個反轉的標記（diff[i+K] ^= 1），表示從 $i+K$ 開始不再受這次翻轉影響。

然而此時的 $\textit{diff}[i]$ 在後續過程中已經不須被使用到，因此我們可以維護一個翻轉次數的前綴和 $s$ ，在掃描到位置 $i$ 時，先將 $s$ 根據 $\textit{diff}[i]$ 反轉（s ^= diff[i]），這樣 $s$ 就代表了當前位置的翻轉狀態（0 表示與初始相同，1 表示與初始相反）。如果當前牛的實際方向是 B（即 A[i] ^ s == 1），則需要翻轉。

常見的錯誤：直接取第一個可行的 $K$

Warning

有些解法會從 $K = N$ 開始往下找，遇到第一個可行的 $K$ 就輸出。這是錯誤的，因為較大的 $K$ 雖然可能讓操作次數較少，但也可能反過來需要更多次操作（例如大區間會連鎖影響，導致多餘動作）。正確做法是枚舉所有 $K$ ，記錄每個 $K$ 對應的操作次數，最後選出操作次數最少的那組，若平手則取最小的 $K$ 。

本題的測試資料沒有涵蓋到這種情況，這裡提供一組可以 hack 上述錯誤解法的反例

10
B
F
B
F
B
F
F
F
F
B

正確答案應該是 1 4（ $K=1$ 只需要翻四次背面牛），但錯誤做法會輸出 2 7。

複雜度分析

時間複雜度： $\mathcal{O}(N^2)$ ，枚舉 $N$ 種 $K$ ，每種 $K$ 掃描一次差分陣列，每次狀態轉移 $\mathcal{O}(1)$ 。
空間複雜度： $\mathcal{O}(N)$ ，僅需一個長度 $N+1$ 的輔助陣列存放差分標記。

Code

def solve():
    n = int(input())
    A = [0 if input().strip() == "F" else 1 for _ in range(n)]

    # k = 1 時必定有解（每頭牛可獨立翻轉）
    ans = (1, n)

    for k in range(1, n + 1):
        res = s = 0
        diff = [0] * (n + 1)
        for i in range(n):
            s ^= diff[i]
            if A[i] ^ s == 1:
                if i + k <= n:
                    res += 1
                    s ^= 1
                    diff[i + k] ^= 1
                else:
                    break
        else:
            ans = min(ans, (k, res), key=lambda x: (x[1], x[0]))
    print(*ans)


if __name__ == "__main__":
    solve()