题解：P2882 [USACO07MAR] Face The Right Way G

Jerrycyx · 2025-01-18 11:36:13 · 题解

首先，翻转的顺序不影响最终结果，所以我们可以规定它从左往右顺序翻转。

其次，假设某个位置 x 以前的所有牛都已经处理为 F，那么当 x 位置出现 B 时：

• 在顺序翻转下，如果从左边某头牛 y 开始翻转来影响它，那么要使 y 回到 F，要么在原位翻一遍（等于啥也没干），要么用更左边某头牛 z 来影响 y（把 y 看成 x，z 看成 y，相当于又回到了这个问题上，无法以合法情况结束；同时还不符合“顺序翻转”的规定）。

• 而如果在它右侧翻转根本不影响 x，更不行了。

综上所述，必须恰好从 x 开始翻转一次来使它变成 F。

解法也就有了：枚举 k，通过这种方式来翻转序列。如果处理完以后还有 B，代表这个 k 不合法；否则用得到的 m 来更新答案。

但是暴力翻转序列所需总时间复杂度为 O(n^3)，过不了这道题（70 Pts）。虽然据说卡常能卡过，但我们需要更加优雅的方法。其他大佬普遍用差分，但是我这里使用的是队列。

• 开一个队列，记录开始翻转的位置。
• 每到达一个新的点 i，就将队尾已经无法覆盖 i 的翻转起始点弹出，保证队列中所有起始点都是能覆盖 i 的。
• 此时队列的大小就是 i 被覆盖的次数，根据其奇偶性来反转 i 即可。如果反转完依然是 B，则将 i 入队，并将其调正。

最后判断处理完毕后的序列是否合法即可。

代码上，B 和 F 可以分别处理成 true 和 false 存入一个 bitset 当中。

使用 bitset 不仅可以直接使用 = 进行复制以进行临时计算，也可以用 any() 方便地对判断序列是否合法，还能节省一些常数。

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

代码如下：

#include<cstdio>
#include<bitset>
#include<queue>
using namespace std;

const int N=5005;
int n,ansk,ansm=0x3f3f3f3f;
bitset<N> a,t;

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        char ch[5]; scanf("%s",ch);
        a[i]=(ch[0]=='B');
    }
    for(int k=1;k<=n;k++)
    {
        int m=0; t=a;
        queue<int> q;
        for(int i=1;i<=n;i++)
        {
            while(!q.empty() && q.front()<i-k+1) q.pop();
            if(q.size()&1) t.flip(i);
            if(i+k-1<=n && t[i])
            {
                q.push(i);
                t.flip(i);
                m++;
            }
        }
        if(!t.any() && m<ansm)
            ansk=k,ansm=m;
    }
    printf("%d %d\n",ansk,ansm);
    return 0;
}

AC 记录