BZOJ4713 迷失的字符串 解题报告
2024-10-20 20:34:40
题目大意：有 \(n\) 个点 \(n-1\) 条边，每条边有一个字符。给你 \(m\) 个字符串 \(s_i\)，问每个字符串是否可以通过树上的一条简单路径表示。
\(n,m\le 30000,\sum |s_i|\le 30000\)
题解
一眼可以看出是点分治，因为路径可以看作点对，判断一个字符串是否出现使用hash即可（为了防止被卡，可能要模数奇怪点，或者多模）。
因为询问 \(m\) 很大，我们不能每次对于每个子树都枚举询问。具体来说对于每个分治重心，将子树里的所有点到重心的路径字符串hash值加入hash表，然后如果一个值分别被从两个不同的子树加入，那么可以知道这个值不管如何都可以和别的任何可行的值进行配对，因为它总能至少有一个与别的值位于不同子树的位置。做完这些就枚举询问，将每个询问的字符串拆分成两段求hash值，看是否都出现且不位于相同子树。然后得到答案的询问可以用链表删除来卡常。
然后发现这样还是有点问题，算一下复杂度是 \(O(n\log n+nm)\) 显然寄了。
发现如果我们对询问建立trie树，然后dfs每个点，并以这个点扩展的同时按照树上的边权跳trie树，那么这样可得到一个与 \(m\) 无关的 \(O(n^2)\) 的暴力。可以优化一下，如果当前trie下的字符串被算过了，就删除，然后减小trie树上每个点维护的 \(sz\) ，发现 \(sz=0\) 就直接退出以此剪枝。总之复杂度小于 \(O(n^2)\) 。
可能你疑惑我为什么讲一个暴力做法？其实因为这个暴力复杂度几乎与 \(m\) 无关，那么可以考虑根号分治。对于点分治下的子树 \(sz\ge \sqrt n\) 的，我们考虑点分治枚举询问做，因为分治子树大小一小于 \(\sqrt n\)，就直接跑暴力去了，由 \(\frac{n}{2^k}\le \sqrt n\) ，得 \(\log\sqrt n\le k\)，可知复杂度为 \(O(n\log\sqrt n+\sqrt nm)\)。
而对于分治子树 \(sz<\sqrt n\) 的，我们最坏复杂度 \(O(n)\)。综上总复杂度 \(O(n\log\sqrt n+\sqrt nm+n)\) ，足以通过此题。
参考代码:
#include<bits/stdc++.h>
#define ll long long
#define db double
#define filein(a) freopen(#a".in","r",stdin)
#define fileot(a) freopen(#a".out","w",stdout)
#define sky fflush(stdout)
#define gc getchar
#define pc putchar
namespace IO{
template<class T>
inline void read(T &s){
s=0;char ch=gc();bool f=0;
while(ch<'0'||'9'<ch) {if(ch=='-') f=1;ch=gc();}
while('0'<=ch&&ch<='9') {s=s*10+(ch^48);ch=gc();}
if(ch=='.'){
db p=0.1;ch=gc();
while('0'<=ch&&ch<='9') {s=s+p*(ch^48);ch=gc();}
}
s=f?-s:s;
}
template<class T,class ...A>
inline void read(T &s,A &...a){
read(s);read(a...);
}
inline bool blank(char c){
return c==' ' or c=='\t' or c=='\n' or c=='\r' or c==EOF;
}
inline void gs(std::string &s){
s+='#';char ch=gc();
while(blank(ch) ) ch=gc();
while(!blank(ch) ){
s+=ch;ch=gc();
}
}
};
using IO::read;
using IO::gs;
const int N=3e4+3;
int n;
std::vector<int>head,nxt;
struct Edge{
int u,v;
char w;
};std::vector<Edge>to;
inline void join(int u,int v,char w){
nxt.push_back(head[u]);
head[u]=to.size();
to.push_back({u,v,w});
}
const int Sz=1e7+9;
struct pr{
ll x,x2;
};
struct Hash_map{
std::vector<int>head,nxt;
struct node{
pr x;
int val;
};
Hash_map(){
head.resize(Sz+3,-1);
};
std::vector<node>to;
inline int& operator [] (pr x){
int u=(x.x+x.x2)%Sz;
for(int i=head[u];~i;i=nxt[i]){
if(to[i].x.x==x.x and to[i].x.x2==x.x2){
return to[i].val;
}
}
nxt.push_back(head[u]);
head[u]=to.size();
to.push_back({x,0});
return to[to.size()-1].val;
}
}ex;
std::string s[N],s2[N];
int sum,rt;
int sz[N],wei[N];
bool vis[N],ans[N];
inline void getroot(int u,int f){
sz[u]=1;wei[u]=0;
for(int i=head[u];~i;i=nxt[i]){
int v=to[i].v;
if(v==f or vis[v]) continue;
getroot(v,u);
sz[u]+=sz[v];
wei[u]=std::max(wei[u],sz[v]);
}
wei[u]=std::max(wei[u],sum-sz[u]);
if(!rt or wei[rt]>wei[u]){
rt=u;
}
}
const ll mod1=1e15+23,mod2=1e14+31;
const int p1=1361,p2=1009;
ll P1[N],P2[N];
std::vector<pr>cls;
inline void getdis(int u,int f,ll hs,ll hs2,int id){
int k=ex[{hs,hs2}];
if(k==id or k==0) ex[{hs,hs2}]=id;
else ex[{hs,hs2}]=-1;
cls.push_back({hs,hs2});
//fprintf(stderr,"%d %lld %lld\n",u,hs,hs2);
for(int i=head[u];~i;i=nxt[i]){
int v=to[i].v;
if(v==f or vis[v]) continue;
getdis(v,u,(1ll*hs*p1%mod1+(to[i].w-'a'+1) )%mod1,
(1ll*hs2*p2%mod2+(to[i].w-'a'+1) )%mod2,id);
}
}
int size;
struct List{
int x,r;
}p[N];
inline void Erase(int x){
p[x].x=p[p[x].r].x;
p[x].r=p[p[x].r].r;
--size;
}
int m;
inline void calc(int u){
//fprintf(stderr,"%d\n",u);
cls.clear();
int id=1;
ex[{0,0}]=id;
cls.push_back({0,0});
for(int i=head[u];~i;i=nxt[i]){
int v=to[i].v;
if(vis[v]) continue;
++id;
getdis(v,u,to[i].w-'a'+1,to[i].w-'a'+1,id);
}
for(int i=1;(i and p[i].x) and size;){
//fprintf(stderr," %d\n",p[i].x);
bool flag=0;
int len=s[p[i].x].size()-1;
ll hl=0,hr=0;
ll hl2=0,hr2=0;
for(int j=1;j<=len;++j){
hr=(1ll*hr*p1%mod1+(s[p[i].x][j]-'a'+1) )%mod1;
hr2=(1ll*hr2*p2%mod2+(s[p[i].x][j]-'a'+1) )%mod2;
}
//fprintf(stderr,"%d %d %d\n",0,hl,hr);
if(ex[{hr,hr2}]){
ans[p[i].x]=1;
//fprintf(stderr,"Kill %d\n",p[i].x);
Erase(i);flag=1;
continue;
}
for(int j=1;j<=len;++j){
hr=(hr-1ll*(s[p[i].x][j]-'a'+1)*P1[len-j]%mod1+mod1)%mod1;
hr2=(hr2-1ll*(s[p[i].x][j]-'a'+1)*P2[len-j]%mod2+mod2)%mod2;
hl=(hl+1ll*P1[j-1]*(s[p[i].x][j]-'a'+1)%mod1)%mod1;
hl2=(hl2+1ll*P2[j-1]*(s[p[i].x][j]-'a'+1)%mod2)%mod2;
//fprintf(stderr,"%d %d %d\n",j,hl,hr);
int k1=ex[{hl,hl2}],k2=ex[{hr,hr2}];
//fprintf(stderr,"%d %d\n",k1,k2);
if(k1 and k2 and (k1==-1 or k2==-1 or k1!=k2) ){
ans[p[i].x]=1;
//fprintf(stderr,"Kill %d\n",p[i].x);
Erase(i);flag=1;
break;
}
}
if(!flag) i=p[i].r;
}
for(auto it:cls){
ex[it]=0;
}
}
int tot=0;
int ch[N][26];
int csz[N];
std::vector<int>val[N];
inline void ins(const std::string &s,int id){
int p=0,len=s.size()-1;
for(int i=1;i<=len;++i){
int c=s[i]-'a';
if(!ch[p][c]) ch[p][c]=++tot;
++csz[p];
p=ch[p][c];
}
++csz[p];
val[p].push_back(id);
}
int dfs2(int u,int f,int p){
int d=0;
if(!val[p].empty() ){
d+=val[p].size();
for(auto it:val[p]) ans[it]=1;
val[p].clear();
}
for(int i=head[u];~i;i=nxt[i]){
int v=to[i].v,c=to[i].w-'a';
if(v==f or vis[v]) continue;
if(ch[p][c] and csz[ch[p][c] ])
d+=dfs2(v,u,ch[p][c]);
}
csz[p]-=d;
return d;
}
void dfs1(int u,int f){
dfs2(u,u,0);
for(int i=head[u];~i;i=nxt[i]){
int v=to[i].v;
if(v==f or vis[v]) continue;
dfs1(v,u);
}
}
const int sqn=sqrt(N);
void dfs(int u){
if(sum>sqn)
calc(u);
else{
dfs1(u,u);
return;
}
vis[u]=1;
for(int i=head[u];~i;i=nxt[i]){
int v=to[i].v;
if(vis[v]) continue;
rt=0;sum=sz[v];
getroot(v,u);
dfs(rt);
}
}
int main(){
filein(a);fileot(a);
read(n);
head.resize(n+3,-1);
for(int i=1;i<n;++i){
int u,v;char c;
read(u,v);
scanf("%c",&c);
join(u,v,c);join(v,u,c);
}
read(m);
for(int i=1;i<=m;++i){
gs(s[i]);
p[i].r=i+1;
p[i].x=i;
ins(s[i],i);
}
P1[0]=P2[0]=1;
for(int i=1;i<=(int)3e4;++i){
P1[i]=1ll*P1[i-1]*p1%mod1;
P2[i]=1ll*P2[i-1]*p2%mod2;
}
size=m;
sum=n;rt=0;
getroot(1,1);
dfs(rt);
for(int i=1;i<=m;++i){
if(ans[i]) printf("YES\n");
else printf("NO\n");
}
fprintf(stderr,"%dms\n",clock() );
return 0;
}
最新文章
- 在安卓下打包cocos2d-js 3.6项目with ProtoBuf.js
- GCD-Grand Central Dispatch
- Android annotations REST
- [知识点]C++中的运算符
- win7旗舰版梦幻主题补丁~完美你的桌面
- 配置openerp的开发环境
- [矩阵快速幂]HDOJ4565 So Easy!
- UIAlertView笔记
- J2EE走向成功路-02-Struts2 配置(Maven)
- 15-5-23 下午02时22分58秒 CST> <Info> <Management> <BEA-141281> <unable to get file lock, will retry ...>
- Arch Linux VMware虚拟机（新手）安装教程
- h264文件分析(纯c解析代码)
- centos6.5 squid安装
- Mysql中大数据类型的存取
- Linux好用的工具命令 - rz/sz
- itchat和wordcloud对微信好友的签名进行画像
- selenium如何定位同级节点
- Go RPC返回值
- 5-java 排序, sort, collections.sort()
- robotframework 运行集合