526互联

Educational Codeforces Round 149 (Rated for Div. 2) C. Best Binary String

发布时间 2023-10-19 19:48:35作者: zsxuan

给一个字符串 \(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;
}