3777. 砖块(递推)

https://www.acwing.com/problem/content/3780/
一眼递推,主要有每个砖块只能操作一次,以及操作顺序不影响结果这两个性质
但是第一次写的代码一塌糊涂,这次模仿了一下y总的代码风格,感觉不错

#include<iostream>
#include<vector>

using namespace std;

string s;
int T,n;

void update(char &c)
{
    if(c=='W')c='B';
    else c='W';
}

bool check(char c)//检测str是否全为c,不为c就操作一次
{
    vector<int>res;
    int n=s.size();
    string t = s;
    for(int i=0;i<n-1;i++)//遍历到倒数第二个字符
    {
        if(t[i]!=c)
        {
            update(t[i]);//更新字符串
            update(t[i+1]);
            res.push_back(i);//记录答案
        }
    }
    //不知道n是奇数还是偶数,也不知道最后一个字符是否操作了
    //因此特判最后一位
    if(t.back()!=c)return false;//不是全为c,同时无解
    cout << res.size() << endl;
    for(int i=0;i<res.size();i++)
        cout << res[i]+1 << ' ';
    if(res.size())cout <<endl;
    return true;
}

int main()
{
    cin >> T ;
    while(T -- )
    {
        cin >> n >> s;
        if(!check('B') && !check('W'))cout << -1 << endl;
    }
    return 0;
}