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;
}