题意:
给一个包含0,1,?的字符串,?可以换成0或1,要求换完之后使得成本最小,二进制字符串的成本定义为按非降序对字符串进行排序所需的“反转字符串的任意连续子字符串”形式的最小操作数。
思路:
因为每次操作是反转连续子字符串,即反转一个区间,所以一个1或0与连续的一块1或0的操作数都是一样的,所以只需要把?替换成与前面一样的即可。
代码:
/*************************************************************************
> File Name: c.cpp
> Author: Beans
> Mail: 3112748286@qq.com
> Created Time: 2023/5/26 14:09:09
************************************************************************/
#include <iostream>
#include <algorithm>
#define int long long
#define endl '\n'
using namespace std;
string s;
void solve(){
cin >> s;char a = '0';
for(auto& c : s){
if(c == '?') c = a;
a = c;
}
cout << s << endl;
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t -- )
solve();
}