Qingshan Loves Strings 2 题解

jcs_pp · 2025-09-26 20:31:25 · 题解

我不知道为神马这些题解这么……长。

说一下我的思路。

第一步（没啥用）

首先，可证明如果 s 中 1 与 0 数量不一样，那么一定不可行。

为什么？因为结果 s 中 1 与 0 数量一定一样，而操作不改变 s 中 1 与 0 数量差。

第二步

此题一定是先处理两端，再处理中间的。因为对中间的操作不会影响两端。

我们把题中的 k−i+1 设为 j ，有以下三种情况：

#include<bits/stdc++.h>
using namespace std;
int T,n;
string s;
void add(string &s,int x){
    s=s.substr(0,x)+"01"+s.substr(x);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>T;
    while(T--){
        cin>>n>>s;
        vector<int>cnt(2);
        for(int i=0;i<n;i++){
            cnt[s[i]-'0']++;
        }
        if(cnt[1]!=cnt[0]){
            cout<<"-1\n";
            continue;
        }
        vector<int>a;
        for(int i=0;i<s.size();i++){
            int t=s.size()-i-1;
            if(s[i]!=s[t]) continue;
            if(s[i]=='0'){
                add(s,t+1);
                a.emplace_back(t+1);
            }
            else{
                add(s,i);
                a.emplace_back(i);
            }
            if(a.size()>300) break;
        }
        if(a.size()>300) cout<<"-1\n";
        else{
            cout<<a.size()<<'\n';
            for(int i:a) cout<<i<<' ';
            cout<<'\n';
        }
    }
    return 0;
}