• 周一. 8月 15th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

「题解」Codeforces 1553D Backspace

admin

11月 28, 2021

看到字符串就害怕傻眼到降智,赢得番薯田大丰收。

注意到问题等价于是否存在一种 (t) 的字符先后一一映射到 (s) 的方案,使得在 (s) 中的下标奇偶性不同,并且要满足最后 (s) 没有被映射到的极长后缀长度为偶数,这样才能保证能把多余的删完

考虑类似于子序列自动机的形式处理出 (fir_{i,j}) 代表第 (i) 位之后最近的下标奇偶性不同的字符 (j) 在哪里。

(t) 串上设计一个 dp,设 (f_{i,0/1}) 代表匹配完 (t) 串的前 (i) 位,第 (i) 位匹配的下标奇偶性为偶数/奇数,最靠前的匹配位置。

由于预处理出了 (fir)(f) 的转移就很明显了,不多赘述。注意到由于要保证最后多余的能删完,仅需要判断 (f_{m,n&1}) 中的值。

(mathcal{Code})

#include<iostream>
#include<cstdio>
#include<cstring>
template <typename T> T Max(T x, T y) { return x > y ? x : y; }
template <typename T> T Min(T x, T y) { return x < y ? x : y; }
template <typename T>
T& read(T& r) {
	r = 0; bool w = 0; char ch = getchar();
	while(ch < '0' || ch > '9') w = ch == '-' ? 1 : 0, ch = getchar();
	while(ch >= '0' && ch <= '9') r = r * 10 + (ch ^ 48), ch = getchar();
	return r = w ? -r : r;
}
const int N = 100010;
char s[N], t[N];
int n, m, vis[2][27], fir[N][27], f[N][2];
void solve() {
	scanf("%s", s+1);
	scanf("%s", t+1);
	n = std::strlen(s+1); m = std::strlen(t+1);	
	for(int i = 0; i < 27; ++i) vis[0][i] = vis[1][i] = 0;
	for(int i = n; ~i; --i) {
		for(int j = 0; j < 27; ++j) fir[i][j] = vis[!(i&1)][j];
		vis[i&1][s[i]-'a'] = i;
	}
	f[1][0] = vis[0][t[1]-'a'];
	f[1][1] = vis[1][t[1]-'a'];
	if(!f[1][0]) f[1][0] = -1;
	if(!f[1][1]) f[1][1] = -1;
	for(int i = 2; i <= m; ++i) {
		if(~f[i-1][1]) f[i][0] = fir[f[i-1][1]][t[i]-'a'];
		else f[i][0] = -1;
		if(~f[i-1][0]) f[i][1] = fir[f[i-1][0]][t[i]-'a'];
		else f[i][1] = -1;
		if(!f[i][0]) f[i][0] = -1;
		if(!f[i][1]) f[i][1] = -1;
	}
	printf("%s
", f[m][n&1] != -1 ? "YES" : "NO");
}
signed main() {
	int T; read(T);
	while(T--) solve();
	return 0;
}

发表回复

您的电子邮箱地址不会被公开。