给定两个长度相等的 \(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\) 串。