题意

选择一个固定长度 $K$，每次翻转连续 $K$ 头牛，求能让所有牛朝前的最少操作数；先最小化操作数，再最小化 $K$。

思路

1. 翻转的数学本质是异或

先把牛的方向编码成二进制：F 记为 $0$，B 记为 $1$。翻转一次就是让方向在 $0$ 和 $1$ 之间切换，因此可以写成

设 $V_{x,K}$ 表示区间 $[x,x+K-1]$ 的翻转掩码，那么一次操作就是

异或满足交换律和结合律，所以任意两次翻转都可以交换顺序：

即使两个区间重叠，这个结论仍然成立，因为重叠位置被翻转两次，正好恢复原状。另外，同一个区间翻转两次也会抵消：

因此，一组操作的最终效果只取决于每个起点被使用了奇数次还是偶数次，与执行顺序无关。为了让操作数最少，每个起点只需要考虑“翻一次”或“不翻”。

2. 固定 $K$ 后，每一步都是被迫的

先固定翻转长度 $K$，令 $x_i\in\{0,1\}$ 表示是否从位置 $i$ 开始翻转。最终第 $i$ 头牛必须朝前，因此它满足一个只与奇偶性有关的方程：

从左向右看这些方程：处理位置 $i$ 时，所有 $x_1,x_2,\ldots,x_{i-1}$ 都已经确定。若当前牛在已有翻转的作用下仍然朝后，那么只有 $x_i=1$ 才能把它变成朝前：

• 从更左边开始的操作已经决定，不能回头修改；
• 从更右边开始的操作覆盖不到位置 $i$；
• 所以从位置 $i$ 开始翻转是唯一选择。

若此时 $i+K-1>N$，说明已经没有合法区间能够改变这头牛，当前的 $K$ 不可行。

以样例的 $K=3$ 为例，从左向右处理时会得到：

这三次翻转并不是为了猜测怎样对后面更有利，而是分别由当时最左边尚未朝前的牛强制产生的。

所以这里看起来像贪心，实际上没有在多个方案中猜测局部最优。它等价于在二元域 $\mathbb F_2$ 上，从左向右对一组三角形方程做前向代入：前面的未知量确定后，当前未知量也被唯一确定。固定 $K$ 后，可行方案的翻转奇偶性是唯一的，得到的操作次数自然也是最少的。

3. 只维护当前被翻转的奇偶性

直接翻转长度为 $K$ 的整个区间，会让一次操作花费 $O(K)$。但由异或模型可知，我们不关心当前位置被翻转了多少次，只关心次数的奇偶性。

扫描时用 flip_parity 表示当前位置是否受到奇数次翻转，并用 started[i] 记录是否从位置 $i$ 开始过一次翻转：

• 开始一次翻转时，令 started[i] = 1，再将 flip_parity 异或 $1$；
• 从 $i-K$ 开始的翻转只覆盖到 $i-1$；
• 因此走到位置 $i$ 时，把 started[i-K] 异或出 flip_parity，这次翻转就自然失效了。

这样，每次区间翻转只做常数次异或运算。对于一个固定的 $K$，可以在 $O(N)$ 时间内判断是否可行并计算操作次数。

4. 枚举所有 $K$

枚举 $K=1,2,\ldots,N$，分别执行上述过程，选择操作次数最少的方案；操作次数相同时选择更小的 $K$。一共有 $N$ 种长度，每种长度扫描一次，故总时间复杂度为 $O(N^2)$。

Python 知识

• 普通列表 started = [0] * n 直接记录每个位置是否开始过翻转，含义比结束标记更直观。
• ^ 表示异或，cows[i] ^ flip_parity 就是当前位置经过已有操作后的真实方向。
• 按 $K$ 从小到大枚举，只在操作次数严格变小时更新答案，就能自然保留并列时更小的 $K$。

代码

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63# P2882 [USACO07MAR] Face The Right Way G
# N 头牛排成一列（F=朝前,B=朝后），每次将连续 K 头转向。求最小 K 和最少操作数。

import sys

FORWARD = 0     # 朝前
BACKWARD = 1    # 朝后

# ---- 读入 ----
data = sys.stdin.read().split()
n = int(data[0])
cows = [BACKWARD if direction == "B" else FORWARD for direction in data[1:]]


def count_operations(k):
    """
    固定 K=k，贪心从左到右：
    碰到朝后的牛就翻从它开始的 k 头牛。
    返回操作数，不可行返回 None。
    """
    # started[i] = 1  表示"以 i 为起点发起过一次 k-翻转"
    started = [0] * n

    # flip_parity: 当前位置 i 上，有奇数个还是偶数个之前的翻转在生效？
    #   0 = 偶数（0个）= 朝向不变
    #   1 = 奇数      = 朝向反转
    # 每次开始/结束一次翻转就 XOR 1，在 0 和 1 之间来回切。
    # parity=奇偶性的意思：只关心"翻转次数是奇数还是偶数"。
    flip_parity = 0
    operations = 0

    for i in range(n):
        # 从 i-k 开始的翻转只覆盖 [i-k, i-1]，走到 i 已失效，关掉它
        if i >= k:
            flip_parity ^= started[i - k]

        # 真实朝向 = 原始朝向 XOR 是否处在翻转中
        current_direction = cows[i] ^ flip_parity
        if current_direction == FORWARD:
            continue        # 已经朝前，跳过

        # 仍然朝后 → 必须从 i 开始做一次 k-翻转
        if i + k > n:       # 窗口越界，此 K 不可行
            return None

        started[i] = 1      # 标记：从这里开始了一个翻转
        flip_parity ^= 1    # 立刻进入翻转状态
        operations += 1

    return operations


# ---- 枚举 K ----
best_k = 1
best_operations = n + 1

for k in range(1, n + 1):
    operations = count_operations(k)
    if operations is not None and operations < best_operations:
        best_k = k
        best_operations = operations

print(best_k, best_operations)

复杂度

时间复杂度 $O(N^2)$，空间复杂度 $O(N)$。

总结

固定窗口后的左端决策是被迫的，差分异或让一次窗口翻转只需常数时间维护。

知识点：差分维护奇偶性

flip_parity 这条思路的关键一句话：

用差分维护"当前被覆盖的奇偶性"，把查一段历史降成一个变量。

没有 flip_parity 会怎样？

走到牛 i 时，想知道它现在朝前还是朝后，你必须回看历史：从 i-K+1 到 i-1 这些位置，有几个发动了翻转？

1
2
3
4
5
6        i-K+1             i-1  i
        ├─────────────────┤
        │  你要查这段 ↑    │
        │  每个 started[j] │
        │  是 0 还是 1？   │
        └─────────────────┘

你把这段全部扫一遍，数奇偶。每次检查 O(K)。 K 次检查 × N 次扫描 = O(NK)，退化成 O(N²) 额外开销，总 O(N³)。

有了 flip_parity 呢？

flip_parity 是一个永远活在"现在时刻"的变量。它只维护一件事：走到 i 时，当前被翻转了奇数次还是偶数次。

翻转就像一个"开关灯"游戏：

1
2
3
4
5
6
7
8
9
10
11
12位置  :  0     1     2     3     4     5     6
牛    :  F     B     B     F     B     F     F

K=3，在位置 1 开始一次翻转（覆盖 [1,3]）：

       1────────────────3
       ┊  翻转区域      ┊
       ┊  i=1  ┊  i=2  ┊  i=3  ┊
       ┊  parity=1    ┊  parity=1 ┊  parity=1
       ┊              ┊           ┊
       started[1]=1  ┊           ends[1+K]=ends[4]=1
                     ┊           ↑ 到这里翻转结束

• 进入：位置 1 发动翻转 → started[1]=1，flip_parity ^= 1（0→1）
• 保持：i=2,3 时 parity 仍是 1
• 退出：i=4 时 flip_parity ^= started[4] → 0。灯灭了。

每个位置只做一次 XOR，O(1)。

完整图示（K=3 样例）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19K=3，在位置 1 翻一次，在位置 3 再翻一次：

位置:    0    1    2    3    4    5    6    7
        ────────┬───────┬───────┬───────┬──────
                │       │       │       │
启动1:  started[1]=1     │       │  ends[4]=1
        翻 [1,3]        │       │  ↑ 这里结束
                │       │       │
启动2:          │  started[3]=1 │  ends[6]=1
                │   翻 [3,5]    │  ↑ 这里结束
                │       │       │
────────────────┼───────┼───────┼────────────────

走到 i=1:  flip_parity ^= started[1] → 1     （进入翻转）
走到 i=2:  flip_parity = 1                    （仍在翻转中）
走到 i=3:  flip_parity ^= started[3] → 0     （两个翻转重叠→抵消！）
走到 i=4:  flip_parity ^= started[4]=ends[4]  （翻转1结束，仍为0）
走到 i=5:  flip_parity = 0                    （翻转2还在）
走到 i=6:  flip_parity ^= started[6]=ends[6]  （翻转2结束）

i=3 处两个翻转重叠，XOR 后 parity=0——一头牛被翻两次等于没翻，完美体现。

核心公式

1
2
3
4
5
6
7for i in range(n):
    flip_parity ^= started[i]       # 新翻转从这开始

    if i >= k:
        flip_parity ^= started[i - k]  # 旧翻转从这退出

    真实朝向 = cows[i] ^ flip_parity

c++

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
48
49
50
51
52
53
54
55
56
57
58// P2882 [USACO07MAR] Face The Right Way G
// N 头牛排成一列（F 朝前，B 朝后），每次可将连续 K 头牛转向。
// 枚举 K，贪心从左到右翻转，求最小 K 和对应最少操作数。

#include <cstdio>
#include <cstring>

const int N = 5005;

int n;
char cows[N];       // cows[i] = 'F' 或 'B'
int ends[N];        // 差分数组：ends[i]=1 表示第 i 个位置有一个翻转结束

// 固定窗口大小 K，贪心扫描，返回所需操作数，不可行则返回 n+1
int operations(int K) {
    memset(ends, 0, sizeof(ends));
    int flipped = 0;    // 当前位置是否处于被翻转状态
    int moves = 0;      // 操作次数

    for (int i = 0; i < n; i++) {
        flipped ^= ends[i];     // i 是某个翻转的结束位置，则取消翻转效果

        // 当前牛的真实朝向：cows[i]=='B' 再异或 flipped
        // 如果朝向是 B（需要被翻），就从 i 开始翻一个长度为 K 的窗口
        if ((cows[i] == 'B') ^ flipped) {
            if (i + K > n) {    // 窗口越界，这个 K 不可行
                return n + 1;
            }
            moves++;
            flipped ^= 1;           // 标记当前位置进入翻转
            ends[i + K] ^= 1;       // 在 i+K 处标记翻转结束
        }
    }
    return moves;
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        char s[5];
        scanf("%s", s);
        cows[i] = s[0];
    }

    int bestK = 1, bestM = n + 1;
    // 枚举所有可能的窗口大小
    for (int K = 1; K <= n; K++) {
        int m = operations(K);
        if (m < bestM) {          // 更少的操作数 → 更新答案
            bestM = m;
            bestK = K;
        }
        // 操作数相同时保持 K 更小的那个（因为 K 从小到大枚举）
    }

    printf("%d %d\n", bestK, bestM);
    return 0;
}

一句话

flip_parity 就是一个"翻转计数器对 2 取模"，每来一个翻转 +1，走一个翻转 -1，每次只花 O(1)。