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

分析

我们可以选区间 [l,r] 进行反转操作.

题目要求我们通过反转操作，将初始字符串变为一个非降序的字符串，并输出我们构建的这个初始串，使得反转操作的次数最少, 那我们能操作的就是 '?', 我们就要关注这个 '?' 要放0还是放1

首先我们要知道, 连续出现的相同数字, 在反转的时候可以视为一个数字, 就比如 000000 可以看作 0, 11111 可以看作 1. 比如对于 11110000 , 要让反转次数最少, 那肯定要把一整段1和一整段0调换以构成非降序

那这是不是就告诉我们, 如果我们可以使得连续出现相同数字的段尽可能的长, 那我们就可以让反转次数达到最少, 用例子来说明就是 11111100 只需要1次, 而 01010101001 肯定1次是操作不完的, 如果我们可以填数, 肯定要使得连续出现相同数字的那一段尽可能的长

那如果 a[i] 是 '?' 就让 a[i] = a[i - 1] 就好了, 那如果开头是 '?' 怎么办, 那就填0, 因为开头是 0 肯定符合非降序, 后续就不需要操作开头, 也符合让反转次数尽可能少

代码

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

JZTXT

CF1837C