给一个字符串 \(s\) 包含 \(0, 1, ?\) 。
定义一个 \(01\) 串 \(s\) 的 \(cost\) 为：选择 \(s\) 的任意一个子段 \([l, r]\) 并 \(reverse\) 。将 \(s\) 变为一个非降序序列时的 \(reverse\) 最小次数即 \(cost\) 。
你可以让 \(s\) 的 \(?\) 换成 \(0/1\) ，使新 \(s\) 的 \(cost\) 最小。输出 \(cost\) 最小的 \(s\) 。
首先分析一个 \(01\) 串 \(s\) 的 \(cost\) ，即需要 \(reverse\) 多少次。不难和证明发现使 \(s\) 非降序需要 \(reverse\) 的次数等于 \(s\) 中 \(10\) 子串的个数。
可以使用 \(navie\) 的 \(dp\) 做法，\(dp_{i, j}\) 为考虑到前 \(i\) 个位置，以 \(j\) 结尾，可以产生的 \(10\) 串数量。
view
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int dp[300005][2], pre[300005][2];
void solve(){
std::string s; std::cin >> s; int n = s.length(); s = " " + s;
for (int i = 1; i <= n; i++) {
dp[i][0] = dp[i][1] = 1 << 30;
if (i == 1) {
if (s[1] == '?') {
dp[1][0] = dp[1][1] = 0;
}
else if (s[i] == '1') {
dp[1][1] = 0;
}
else if (s[i] == '0') {
dp[1][0] = 0;
}
}
else {
if (s[i] == '?') {
dp[i][0] = std::min(dp[i - 1][0], dp[i - 1][1] + 1);
pre[i][0] = dp[i - 1][0] < dp[i-1][1] + 1 ? 0 : 1;
dp[i][1] = std::min(dp[i - 1][0], dp[i - 1][1]);
pre[i][1] = dp[i - 1][0] < dp[i-1][1] ? 0 : 1;
}
else if (s[i] == '1') {
dp[i][1] = std::min(dp[i - 1][0], dp[i - 1][1]);
pre[i][1] = dp[i - 1][0] < dp[i-1][1] ? 0 : 1;
}
else if (s[i] == '0') {
dp[i][0] = std::min(dp[i - 1][0], dp[i - 1][1] + 1);
pre[i][0] = dp[i - 1][0] < dp[i-1][1] + 1 ? 0 : 1;
}
}
}
// std::cout << dp[n][0] << ' ' << dp[n][1] << '\n';
std::vector<int> ans;
int p = dp[n][0] < dp[n][1] ? 0 : 1; ans.push_back(p);
for (int i = n; i >= 2; --i) {
p = pre[i][p];
ans.push_back(p);
}
std::reverse(ans.begin(), ans.end());
int m = ans.size();
for (int i = 0; i < m; i++) std::cout << ans[i]; std::cout << "\n";
}
int main() {
int _ = 1; std::cin >> _;
while (_--) solve();
return 0;
}