codeforce每日一题链接
题目描述
给你一个只含0,1,?的字符串,请你将?替换成0或者1,使得字符串开销最小。二进制字符串的开销定义为按非降序排序字符串所需的“逆转字符串的任意连续子字符串”形式的最小操作数。
样例
输入样例1
4
??01?
10100
1??10?
0?1?10?10
输出样例1
00011
10100
111101
011110010
算法
(暴力枚举) $O(n)$
对于一段连续的?,我们只需要找到它的两段是什么,如果两段的字符相等,那就填哪个字符,否则随便填。
C++ 代码
// https://www.acwing.com/blog/content/34755/
#include<bits/stdc++.h>
#define endl '\n'
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;
const int N = 1e5 + 10, M = N * 2, INF = 0x3f3f3f3f;
int n, m;
inline void solve()
{
string str;
cin>>str;
n = str.size();
for(int i=0;i<n;i++){
if(str[i]=='?')
{
int j = i;
while(j<n && str[j]=='?') j++;
if(i>0){
for(int k=i;k<j;k++) str[k] = str[i - 1];
}else{
if(j<n) for(int k=i;k<j;k++) str[k] = str[j];
else
for(int k=i;k<j;k++) str[k] = '0';
}
// cout<<i<<" "<<j<<endl;
i = j - 1;
}
}
cout<<str<<endl;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T;
cin>>T;
while(T--)
{
solve();
}
return 0;
}