# A. Two 0-1 Sequences (greedy)

2022-08-06 09:23:45Luo gkv

## 题意

Ask through the above operations several times,能否将a转化为b.

## 思路

aof each operation,Essentially after removing a few characters from the prefix,can finally andb相等.
We are greedy for reservationsa和bSuffix the same part.

• 如果b和a的最长公共后缀,小于len(b)-2,此时a和b至少有2个字符不同,直接gg
• 如果b和a的最长公共后缀,等于len(b)-1,此时a和b有1个字符不同.我们只需看athe remaining prefixes,是否有等于b的元素即可.
• 如果b和a的最长公共后缀,等于len(b),Clearly there is a solution at this point.

## 代码

``````#include<bits/stdc++.h>
using namespace std;
const int maxn = 55;

int n, m;
char a[maxn], b[maxn];
void solve() {

scanf("%d%d", &n, &m);
scanf("%s%s", a, b);
int i = n - 1, j = m - 1;
while (i >= 0 && j >= 0) {

if (a[i] != b[j]) {

break;
}
--i;
--j;
}
int flag = 0;
while (i >= 0) {

if (a[i] == '0') {

flag |= 1;
} else {

flag |= 2;
}
--i;
}
bool ok = j < 0;
ok |= (j == 0 && flag == 3);
printf("%s\n", ok ? "YES" : "NO");
}
int main() {

int t;
scanf("%d", &t);
while (t--) {

solve();
}
}
``````

## 最后

weixin gongzhonghao搜 对方正在debug,关注下,一起快乐刷题吧~