相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4713
解题报告
这题拿bitset搞一搞就好了
f[i]表示前缀匹配,g[i]表示后缀匹配
然后暴力更新
时间复杂度:$O(\frac{n^2}{64})$
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int M = 16; const int SGZ = 26; const int N = 30000+9; int head[N],nxt[N<<1],to[N<<1],col[N<<1],sz[N],hvy[N]; int n,m,tot,beg[N],ed[N],id[N],pool[M],top; char s[N]; bitset<N> vout,ans,ve,vis[SGZ],vs[SGZ],f[M],g[M]; inline int read() { char c=getchar(); int f=1,ret=0; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret * f; } inline void Add_Edge(int u, int v, int c) { static int E = 1; to[++E] = v; nxt[E] = head[u]; head[u] = E; col[E] = c; to[++E] = u; nxt[E] = head[v]; head[v] = E; col[E] = c; } void DFS1(int w, int f) { sz[w] = 1; for (int i=head[w];i;i=nxt[i]) { if (to[i] != f) { DFS1(to[i], w); sz[w] += sz[to[i]]; if (sz[hvy[w]]<sz[to[i]]) hvy[w] = to[i]; } } } inline void init(int w) { id[w] = pool[top--]; f[id[w]].reset(); g[id[w]] = ve; } inline void solve(int x, int y, int c) { int ix = id[x], iy = id[y]; f[iy] <<= 1; f[iy] &= vis; f[iy] |= vs; g[iy] = g[iy] & vis; vout |= g[iy]; g[iy] >>= 1; ans |= f[ix] & g[iy]; ans |= g[ix] & f[iy]; f[ix] |= f[iy]; g[ix] |= g[iy]; pool[++top] = iy; } void DFS2(int w, int f) { if (hvy[w]) DFS2(hvy[w], w); init(w); for (int i=head[w];i;i=nxt[i]) if (to[i] == hvy[w]) solve(w, hvy[w], col[i]); for (int i=head[w];i;i=nxt[i]) if (to[i] != hvy[w] && to[i] != f) DFS2(to[i], w), solve(w, to[i], col[i]); } int main() { for (int i=top=M-1;~i;i--) pool[i] = i; for (int i=n=read(),u,v;i>1;i--) { u = read(); v = read(); scanf("%s",s); Add_Edge(u, v, s[0]-'a'); } for (int i=m=read(),len;i;i--) { scanf("%s",s); len = strlen(s); vs[s[0]-'a'][beg[m-i+1]=tot+1] = 1; for (int j=0;j<len;j++) vis[s[j]-'a'][++tot] = 1; ve[ed[m-i+1]=tot] = 1; } DFS1(1, 1); DFS2(1, 1); for (int i=1,tag=0;i<=m;i++,tag=0) { if (vout[beg[i]]) tag = 1; for (int j=beg[i];j<=ed[i]&&!tag;j++) if (ans[j]) tag = 1; puts(tag?"YES":"NO"); } return 0; }
后记
这题似乎之前听谁说过有点分的做法?
不过想不起怎么做了 _(:з」∠)_
会的神犇可不可以给我讲一讲怎么做啊 QwQ