CF2162B Beautiful String

Andy1101 · 2025-11-21 20:17:51 · 题解

思路

不下降序列：指一个序列的任意一项不小于其上一项，即 a[i] \ge a[i-1]。例如 00011、00000、11111 是不下降序列，而 10011、110 不是不下降序列。

回文串：指一个序列正着读和倒着读是一样的。例如 10101、101、1111 是回文串，而 10011、110 不是回文串。

不难发现，将所有的 0 删除即可保证删除部分不下降且剩余部分为回文串（删除所有的 1 也可以）。

代码

#include <bits/stdc++.h>
using namespace std;
void solve()
{
    int n;
    string s;
    cin >>n>>s;
    int cnt=0;
    for(int i=0;i<n;i++)
    {
        if(s[i]=='0') cnt++;
    }
    cout <<cnt<<'\n';
    for(int i=0;i<n;i++)
    {
        if(s[i]=='0') cout <<i+1<<" ";
    }
    cout <<'\n';
}
int main()
{
    int t;
    cin >>t;
    while(t--)
    {
        solve();
    }
    return 0;
}