Rating predictions
A | B | C | D | E | F | G | H | I | |
---|---|---|---|---|---|---|---|---|---|
Error_Yuan | 800 | 1200 | 1600 | 2100 | 2300 | 2600 | 3000 | 3400 | 3500 |
sszcdjr | 800 | 1100 | 1600 | 2000 | 2300 | 2600 | 2900 | 3300 | 3500 |
[problem:476175B]
Author: wyrqwq
Hint
($$$\texttt{01}$$$ or $$$\texttt{10}$$$ exists) $$$\Longleftrightarrow$$$ (both $$$\texttt{0}$$$ and $$$\texttt{1}$$$ exist).
Solution
Each time we do an operation, if $$$s$$$ consists only of $$$\texttt{0}$$$ or $$$\texttt{1}$$$, we surely cannot find any valid indices. Otherwise, we can always perform the operation successfully. In the $$$i$$$-th operation, if $$$t_i=\texttt{0}$$$, we actually decrease the number of $$$\texttt{1}$$$-s by $$$1$$$, and vice versa. Thus, we only need to maintain the number of $$$\texttt{0}$$$-s and $$$\texttt{1}$$$-s in $$$s$$$. If any of them falls to $$$0$$$ before the last operation, the answer is NO
, otherwise answer is YES
.
Code (C++)
#include <bits/stdc++.h>
#define all(s) s.begin(), s.end()
using namespace std;
using ll = long long;
const int _N = 1e5 + 5;
void solve() {
int n; cin >> n;
string s, t; cin >> s >> t;
int cnt0 = count(all(s), '0'), cnt1 = n - cnt0;
for (int i = 0; i < n - 1; i++) {
if (cnt0 == 0 || cnt1 == 0) {
cout << "NO" << '\n';
return;
}
if (t[i] == '1') cnt0--;
else cnt1--;
}
cout << "YES" << '\n';
}
int main() {
int T; cin >> T;
while (T--) {
solve();
}
}