526互联

Educational Codeforces Round 154 (Rated for Div. 2) B. Two Binary Strings

发布时间 2023-10-16 21:49:37作者: zsxuan

给定两个长度相等的 \(01\) 字符串 \(a\) 和 \(b\) 。每个字符串都是以 \(0\) 开始以 \(1\) 结束。
在一步操作中，你可以选择任意一个字符串：

  • 选择任意两个位置 \(l, r\) 满足 \(s_l = s_r\) ，然后让 \(\forall i \in [l, r], s_i = s_l\) 。

询问经过若干次操作后能否使得 \(a = b\) 。

显然若 \(a, b\) 经过若干次操作后可以相等，则存在一个 \(x\) ，使得：

  • \(a_x = 0, a_{x + 1} = 1\)
  • \(b_x = 0, b_{x + 1} = 1\)
view 
#include <bits/stdc++.h>
typedef long long ll;
void solve(){
	std::string a, b;
	std::cin >> a >> b; int n = a.length();
	a = " " + a; b = " " + b;
	for (int i = 1; i < n; i++) {
		if (a[i] == '0' && a[i + 1] == '1') {
			if (b[i] == '0' && b[i + 1] == '1') {
				std::cout << "YES\n";
				return;
			}
		}
	}
	std::cout << "NO\n";
}
int main() {
	int _ = 1; std::cin >> _;
	while (_--) {solve();}
	return 0;
}

假设没有每个字符串以 \(0\) 开始以 \(1\) 结束的条件，也可以使用分类讨论解决。

  • \(a_1 \neq b_1\) 或者 \(a_n \neq b_n\) 则不能。
  • 否则 \(a_1 = a_n\) 一定能。
  • 再否则，找 \(01\) 串或 \(10\) 串。