A. Two 0-1 Sequences (greedy)

题目

题意

给定a,b这两个01字符串
现a可以执行操作
选取a的头两个字符,and delete one of them,Reassemble the remaining elements into a new string.
即a = a[0] + a[2:]或者a = a[1] + a[2:]

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[0]的元素即可.
• 如果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,关注下,一起快乐刷题吧~