CF1553D. Backspace（正难则反）

最新推荐文章于 2021-10-19 15:11:41 发布

NeverMakeIt

最新推荐文章于 2021-10-19 15:11:41 发布

阅读量477

点赞数 2

分类专栏： Codeforces 文章标签：贪心算法算法字符串

本文链接：https://blog.csdn.net/NeverMakeIt/article/details/119042818

版权

Codeforces 专栏收录该内容

8 篇文章

订阅专栏

这篇博客探讨了一种字符串处理问题，即如何通过添加退格字符将字符串S转换为字符串T。文章介绍了两种解题思路，一种是从正向匹配，另一种是从反向匹配。关键在于分析字符串段的长度，确保在匹配过程中保持段的偶数长度。代码实现部分展示了两种方法的C++代码，用于判断是否能通过退格操作完成字符串转换。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

传送门

题目大意

给定一个字符串S和一个字符串T。可以将S字符串中的任意字符变成退格字符\b，问，能否将字符串变S为T。例如：S=“abcdef”，我们将其中第3个字符变为退格字符，则S=“ab\bdef”=“adef”，如果T为“adef”则输出YES。如果无法变成T字符串则输出NO。

解题思路

经过分析可以发现，如果将目标符串中的每个字符看成一个隔板，则原字符串S将被分成strlen(T)+1断，除了第一段，其余段的长度一定为偶数。
这样衍生出了两种方法。第一种从正向考虑，我们可以推导出第一段的长度是奇数还是偶数。可以发现strlen(S)-strlen(T)的结果如果是奇数的话，说明一定有一个多余字符无法跟一个退格符配对。将这个多余字符变成退格符放在第一段（不能放在其他段，因为其他段的长度都是偶数，放进去之后会变成奇数）。这样第一段至少有一个退格符，索性从原字符串第二个字符开始与目标字符串匹配，匹配不成功要向后移动两个位置（保证其余段间长度为偶数）。如果S和T的长度之差为偶数，也可以推导出第一段的长度为偶数，这样从零开始往后匹配，匹配方法同上。
第二种方法从反向考虑，结合第一种方法的经验，如果我们把S和T都倒置，那么第一段就是倒置之前的最后一段，其长度一定为偶数。这样就确定了第一段长度，接着匹配方法与之前类似。

代码实现

方案一：

#include <bits/stdc++.h>

const int MAXN = 1e6 + 5; 
char s[MAXN], t[MAXN];

int main() {
	int T; scanf("%d", &T);
	while (T--) {
		
		scanf("%s%s", s, t);
		int slen = strlen(s);
		int tlen = strlen(t);
		
		int c = slen - tlen & 1;
		int jud = 1;
		for (int i = c, j = 0; j < tlen; j++) {
		while (i < slen && s[i] != t[j]) i += 2;
			if (i >= slen) {
				jud = 0; break;
			}
			i++;
		}
		jud ? puts("YES") : puts("NO");
	}
}

方案二：

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 5; 
char s[MAXN], t[MAXN];

int main() {
	int T; scanf("%d", &T);
	while (T--) {
		scanf("%s%s", s, t);
		int slen = strlen(s);
		int tlen = strlen(t);
		reverse(s, s + slen);
		reverse(t, t + tlen);
		int jud = 1;
		for (int i = 0, j = 0; j < tlen; j++) {
		while (i < slen && s[i] != t[j]) i += 2;
			if (i >= slen) {
				jud = 0; break;
			}
			i++;
		}
		jud ? puts("YES") : puts("NO");
	}
}