相关链接
题目传送门: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
楼下是疯子。哈哈
bookmarked!!, I love your website!
Superb, what a blog it is! This web site presents helpful facts to us,
keep it up.
It’s hard to find educated people about this subject, however, you seem like you know what you’re talking about!
Thanks
I was wondering if you ever thought of changing the layout of your site?
Its very well written; I love what youve got to say. But maybe you
could a little more in the way of content so people could connect with it better.
Youve got an awful lot of text for only having one or 2 pictures.
Maybe you could space it out better?
Very good write-up. I absolutely appreciate this website. Keep it up!
Hey! This is my first visit to your blog! We are a
group of volunteers and starting a new initiative in a community in the same
niche. Your blog provided us valuable information to work on. You have done a outstanding job!
Way cool! Some very valid points! I appreciate you writing this post plus the rest
of the website is extremely good.
Thank you for another wonderful post. Where else may just anyone get that kind of information in such a perfect method of writing? I’ve a presentation subsequent week, and I’m at the search for such info.
Hello every one, here every one is sharing these kinds of familiarity, so it’s nice to read this blog, and I used to pay a quick visit this
web site daily.
I got this web site from my friend who informed me about this website and at the moment this time I am visiting this
web page and reading very informative articles or
reviews at this time.
Good article. I absolutely appreciate this website.
Keep writing!
I know this if off topic but I’m looking into starting
my own weblog and was wondering what all is needed to get
setup? I’m assuming having a blog like yours would cost a pretty penny?
I’m not very web savvy so I’m not 100% sure. Any recommendations or advice would be
greatly appreciated. Cheers
Wow, fantastic blog layout! How long have you been blogging for?
you make blogging look easy. The overall look of your web site is
wonderful, let alone the content!
I visited many web pages except the audio feature for audio songs current at this site is
actually fabulous.
Heya i’m for the first time here. I came across this board and
I find It really helpful & it helped me out a lot. I’m hoping to offer something
back and help others like you aided me.
It is the best time to make some plans for the future and it is time to be happy.
I’ve read this post and if I could I wish to suggest you few interesting things
or suggestions. Maybe you could write next articles referring to this article.
I want to read even more things about it!
Everyone loves it when individuals come together and share ideas.
Great blog, stick with it!
I’m gone to say to my little brother, that he should also go to see
this weblog on regular basis to take updated from
newest reports.
Thanx for the effort, keep up the good work Great work, I am going to start a small Blog Engine course work using your site I hope you enjoy blogging with the popular BlogEngine.net.Thethoughts you express are really awesome. Hope you will right some more posts.