【BZOJ 4713】迷失的字符串

相关链接

题目传送门: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

20 thoughts to “【BZOJ 4713】迷失的字符串”

  1. 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?

  2. 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!

  3. 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.

  4. 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.

  5. 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.

  6. 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

  7. 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!

  8. 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.

  9. 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!

  10. 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.

Leave a Reply to ps4 games Cancel reply

Your email address will not be published. Required fields are marked *