[省选集训2022] 模拟赛17

本文主要是介绍[省选集训2022] 模拟赛17，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

选拔

题目描述

给定一棵边带字符的树，有 \(m\) 次询问，每次问一个字符串是否对应着树上的一条简单路径。

\(n,m\leq 30000\)，询问字符串总长不超过 \(30000\)

解法

考虑询问串出现在树上的形式一定是从下到上的路径和从上到下的路径拼接起来。

考虑 \(dp\)，设 \(f(u,i,j)\) 表示从下到上到 \(u\)，是否可以匹配到字符串 \(i\) 的前缀 \(j\)，\(g(u,i,j)\) 表示 \(u\) 开始从上到下，是否可以匹配到字符串 \(i\) 的后缀 \(j\)

两者都可以很容易地从子树转移上来，发现询问串的总长很小，所以我们把询问串拼在一起作为状态，在中间插入分隔符，那么就可以用 \(\tt bitset\) 优化转移了，时间复杂度 \(O(\frac{nm}{w})\)

注意转移不能直接 \(\tt dfs\) 做，要先把欧拉序搞出来循环做，要不然会爆内存（可能是计算机原理，具体原因不清楚）

#include <cstdio>
#include <vector>
#include <bitset>
#include <cstring>
#include <iostream> 
using namespace std;
const int M = 30005;
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,m,k,fa[M],fc[M],id[M],l[M],r[M];
bitset<M<<1> f[M],g[M],pos[27],ans;char s[M],t[M<<1];
struct edge{int v,c;};vector<edge> G[M];
void dfs(int u,int p)
{
	fa[u]=p;id[++k]=u;
	for(auto x:G[u]) if(x.v^p)
		fc[x.v]=x.c,dfs(x.v,u);
}
signed main()
{
	freopen("selection.in","r",stdin);
	freopen("selection.out","w",stdout);
	n=read();
	for(int i=1;i<n;i++)
	{
		int u=read(),v=read();scanf("%s",s);
		G[u].push_back({v,s[0]-'a'});
		G[v].push_back({u,s[0]-'a'});
	}
	dfs(1,0);
	m=read();k=0;
	for(int i=1;i<=m;i++)
	{
		scanf("%s",s);
		int len=strlen(s);
		l[i]=k;t[k++]='#';
		for(int j=0;j<len;j++) t[k++]=s[j];
		t[r[i]=k]='#';
	}
	for(int i=0;i<=k;i++)
	{
		if(t[i]!='#') pos[t[i]-'a'].set(i);
		else pos[26].set(i);
	}
	for(int i=1;i<=n;i++) f[i]=g[i]=pos[26];
	for(int i=n;i>=1;i--)
	{
		int u=id[i],v=fa[u],x=fc[u];
		if(!v) continue;
		ans|=(f[u]<<1)&pos[x]&(g[v]>>1);
		ans|=(f[v]<<1)&pos[x]&(g[u]>>1);
		f[v]|=pos[x]&(f[u]<<1);
		g[v]|=pos[x]&(g[u]>>1);
	}
	for(int i=1;i<=m;i++)
	{
		int fl=0;
		for(int j=l[i];j<r[i];j++) fl|=ans[j];
		puts(fl?"YES":"NO");
	}
}

这篇关于[省选集训2022] 模拟赛17的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！