Best Binary String
题面翻译
给定由 1 0 ? 所组成的字符串，你需要用 0 或 1 替换 ?。
我们将 \(s_{l},s_{l+1},\dots,s_r\) 反转成为一次操作。
你要使通过“反转”操作使原字符串成为升序的操作次数尽可能的小。
问最终构造出的字符串，有多解输出其一。
题目描述
You are given a string $ s $ consisting of the characters 0, 1 and/or ?. Let's call it a pattern.
Let's say that the binary string (a string where each character is either 0 or 1) matches the pattern if you can replace each character ? with 0 or 1 (for each character, the choice is independent) so that the strings become equal. For example, 0010 matches ?01?, but 010 doesn't match 1??, ??, or ????.
Let's define the cost of the binary string as the minimum number of operations of the form "reverse an arbitrary contiguous substring of the string" required to sort the string in non-descending order.
You have to find a binary string with the minimum possible cost among those that match the given pattern. If there are multiple answers, print any of them.
输入格式
The first line contains a single integer $ t $ ( $ 1 \le t \le 3 \cdot 10^4 $ ) — the number of test cases.
The first and only line of each test case contains the string $ s $ ( $ 1 \le |s| \le 3 \cdot 10^5 $ ) consisting of characters 0, 1, and/or ?.
The sum of the string lengths over all test cases does not exceed $ 3 \cdot 10^5 $ .
输出格式
For each test case, print a binary string with the minimum possible cost among those that match the given pattern. If there are multiple answers, print any of them.
样例 #1
样例输入 #1
4
??01?
10100
1??10?
0?1?10?10
样例输出 #1
00011
10100
111101
011110010
提示
In the first test case of the example, the cost of the resulting string is $ 0 $ .
In the second test case, the cost of the resulting string is $ 2 $ : we can reverse the substring from the $ 1 $ -st character to the $ 5 $ -th character, and we obtain the string 00101. Then we reverse the substring from the $ 3 $ -rd to the $ 4 $ -th character, and we obtain the string 00011, which is sorted in non-descending order.
分析
题目要求我们通过反转操作，将初始字符串变为一个非降序的字符串串，并输出我们构建的这个初始串，使得反转操作的次数最少
思路是我们要让相同的数字在一起，比如这一块都是1，这样子我翻转的时候就可以一整块1一起翻转，就能够使得操作次数最少
具体来说:
令s[0] = 0(如果s[0] == '?')，因为要升序，所以最左边的设成0肯定没问题
令s[i] = s[i - 1]，这样就能使的相同的字符尽可能的连续
代码
#include <iostream>
#include <string.h>
using namespace std;
const int N = 3e5 + 10;
int main()
{
int t;
scanf("%d", &t);
while (t--)
{
char s[N];
scanf("%s", s);
if (s[0] == '?') s[0] = '0';
for (int i = 1; s[i]; i++)
{
if (s[i] == '?') s[i] = s[i - 1];
}
printf("%s\n", s);
}
return 0;
}