洛谷4965 薇尔莉特的打字机（Trie，DP）

神仙题。

考虑在一棵 Trie 上进行染色，将可能出现的串的末尾染成黑色。答案就是黑点的个数。一开始只有 \(A\) 的末尾点是黑色。

当出现一个字符（不是退格）\(c\) 时，就要将每个黑点的 \(c\) 儿子都染成黑色。

然而这样一个点可能会有重复染色，不能直接乘 \(2\)。

不妨记录一个 \(f[c]\) 表示有儿子 \(c\) 且该儿子是黑色的点的个数。

那么此时答案 \(ans\) 应该变成 \(2ans-f[c]\)（减掉已经是黑的儿子 \(c\) 的个数），同时更新一下 \(f[c]\)，就是原来的 \(ans\)（原来的每个黑点都有一个黑儿子 \(c\)）。其它的 \(f\) 不变。

当出现退格时：

退格实际上就是回到 Trie 上的父亲。

我们发现，一个字符不打，和打了再被退格是一样的。所以退格有用，当且仅当它删掉的是原来 \(A\) 串里的字符。

再仔细分析一波，如果是第 \(x\) 个退格，那么收到影响的点只有 \(A[n-x+1]\) 这个点。

（可以通过 Trie 理解，除了最浅的黑点，其它的黑点的父亲肯定都是黑点，所以只用考虑最浅的黑点，也就是 \(A[n-x+1]\) 这个点）

对这个点瞎搞一波就行了。

时间复杂度 \(O(n+m)\)。

#include<bits/stdc++.h>

using namespace std;

const int maxn=5000500,mod=19260817;

#define lson o<<1,l,mid

#define rson o<<1|1,mid+1,r

#define FOR(i,a,b) for(int i=(a);i<=(b);i++)

#define ROF(i,a,b) for(int i=(a);i>=(b);i--)

#define MEM(x,v) memset(x,v,sizeof(x))

inline int read(){

	int x=0,f=0;char ch=getchar();

	while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();

	while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();

	return f?-x:x;

}

int n,m,f[26],ans=1,at;

char a[maxn],b[maxn];

int main(){

	at=n=read();m=read();

	scanf("%s%s",a+1,b+1);

	FOR(i,1,m){

		int c=b[i]-'A';

		if(c<=25){

			int tmp=f[c];

			f[c]=ans;

			ans=(2*ans-tmp+mod)%mod;

		}

		else{

			if(!at) continue;

			f[a[at]-'A']=(f[a[at]-'A']+1)%mod;

			ans=(ans+1)%mod;

			at--;

		}

	}

	printf("%d\n",ans);

}

巴特西

洛谷4965 薇尔莉特的打字机（Trie，DP）

最新文章

热门文章