P8266 [USACO22OPEN] Photoshoot B

yzyjh · 2022-04-04 17:29:34 · 题解

蒟蒻又来写题解了 awa

首先，我们先把题目抽象一下，每次翻转一个偶数长度的前缀事实上就是将那一段中奇数位翻转到偶数位，偶数位翻转到奇数位，更直接一些，将输入的字符没两个为一组，如果一次操作包含了这两个字符，这两个字符位置的奇偶会交换，如果这两个字符是相同的，显然怎样翻转都是无用的，要求是让尽可能多的 G 在偶数位置上。

然后我们只需要定义一个动态数组，将 G 在左侧的看做 1，G 在右侧的看做 0,遍历一遍就会得到一个 01 串。

然后我们在遍历这个 01 串，如果相邻的两位数不同，那么就要多进行一次翻转。

一点细节：如果末尾数字为 1 （即需要翻转），那么答案要 +1。

下面就是 code 了：

#include<bits/stdc++.h>
using namespace std;
char s[200005];
int n;
vector<int>p;
int main()
{
    int i,j;
    cin>>n;
    cin>>(s+1);
    for(i=1;i<=n;i+=2)
        if(s[i]!=s[i+1])//两两一组
            if(s[i]=='G'&&s[i+1]=='H')
                p.push_back(1);
            else
                p.push_back(0);
    int cnt=0;
    for(i=1;i<p.size();i++)//遍历动态数组
        if(p[i-1]!=p[i])
            cnt++;
    if(p.size()==0)cout<<cnt<<endl;
    else cout<<cnt+p[p.size()-1]<<endl;//如果最后一个是1，那答案要加1
    return 0;   
}

完结撒花✿✿ヽ(°▽°)ノ✿