每日一題-磚塊-10

磚塊

n 個磚塊排成一排，從左到右編号依次為 1∼n。

每個磚塊要麼是黑色的，要麼是白色的。

現在你可以進行以下操作若幹次（可以是 0 次）：

選擇兩個相鄰的磚塊，反轉它們的顔色。（黑變白，白變黑）

你的目标是通過不超過 3n 次操作，将所有磚塊的顔色變得一緻。

輸入格式

第一行包含整數 T，表示共有 T 組測試資料。

每組資料第一行包含一個整數 n。

第二行包含一個長度為 n 的字元串 s。其中的每個字元都是 W 或 B，如果第 i 個字元是 W，則表示第 i 号磚塊是白色的，如果第 i 個字元是 B，則表示第 i 個磚塊是黑色的。

輸出格式

每組資料，如果無解則輸出一行 −1。

否則，首先輸出一行 k，表示需要的操作次數。

如果 k>0，則還需再輸出一行 k 個整數，p1,p2,…,pk。其中 pi 表示第 i 次操作，選中的磚塊為 pi 和 pi+1 号磚塊。

如果方案不唯一，則輸出任意合理方案即可。

資料範圍

1≤T≤10，

2≤n≤200。

輸入樣例：

4

8

BWWWWWWB

4

BWBB

5

WWWWW

3

BWB

輸出樣例：

3

6 2 4

-1

2

2 1

思路：如果b 或者w 磚塊的數量有一者的是0 表示不需要翻轉

如果都是奇數個 則沒有正确答案 參考第二個案例 無論怎麼翻轉 總有一個與衆不同的磚塊

需要翻轉 磚塊數量為偶數的 友善消除

先選擇一個數量為偶數的磚塊

可以從前到後 周遊每一個磚塊 如果這磚塊 則翻轉此磚塊和其後面的磚塊 知道最後一行 次數一定會找到答案

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int N=210;
char s[N];
int T;
void turn(int n){
    if(s[n]=='W')s[n]='B';
    else s[n]='W';
    if(s[n+1]=='B')s[n+1]='W';
    else s[n+1]='B';
} 
vector<int>num;
int main(){
    cin>>T;
    while(T--)
    {
        int w_c=0,b_c=0,n,cou=0;
        cin>>n;
        num.clear();
        for(int i=0;i<n;i++){
            cin>>s[i];
            if(s[i]=='W')w_c++;
            else b_c++;
        }
       // cout<<"w_c:"<<w_c;
       //  cout<<"b_c"<<b_c;
       //如果其中一個為0 表示不需要翻轉
        if(w_c==0||b_c==0){cout<<0<<endl;continue;}
        // cout<<'*';
        //都為奇數也不需要翻轉
        if(w_c%2==1&&b_c%2==1){cout<<-1<<endl;continue;}
        //翻轉數量為偶數的
        if(w_c%2==0){
            for(int i=0;i<n-1;i++){
                if(s[i]=='W')turn(i),cou++,num.push_back(i);
            }
        }else
        {
            for(int i=0;i<n;i++){
                if(s[i]=='B')turn(i),cou++,num.push_back(i);
           }
        }
         cout<<cou<<endl;
        for(auto x:num)
      {
        cout<<x+1<<" ";  
      }
        puts("");
}
}