关键词:
最近做题成双成对?不是双倍经验就是两题同解。
3940 3942
给定字典,给定字符串,删去字符串中所有字典内单词。保证不会出现二者包含状况。$n leq 1e5,sum len leq 1e5$
AC自动机裸题。build出AC自动机后从左到右插入文本串,同时边匹配边push进栈里。匹配成功就弹栈。
注意要记录匹配到第几个字符的时候,AC自动机指针(我管那个一直蹦的东西就叫指针了?)指到哪里。弹栈之后要指针也要跳回来。
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int,int> P;
const int N=100010;
struct ACAM{
int ch[N][26],cnt[N],f[N];
int sz,rt;
void init(){
memset(ch,-1,sizeof ch);
memset(cnt,0,sizeof cnt);
memset(f,0,sizeof f);
sz=rt=0;
}
void ins(char *s){
int n=strlen(s),u=rt;
for(int i=0;i<n;i++){
int c=s[i]-‘a‘;
if(!~ch[u][c])
ch[u][c]=++sz;
u=ch[u][c];
}
cnt[u]=n;
}
void build(){
queue<int>q;
while(!q.empty())q.pop();
for(int i=0;i<26;i++)
if(~ch[rt][i])
f[ch[rt][i]]=rt,q.push(ch[rt][i]);
else ch[rt][i]=rt;
while(!q.empty()){
int u=q.front();q.pop();
for(int i=0;i<26;i++){
int v=ch[u][i];
if(~v){
int now=f[u];
while(f&&!~ch[now][i])now=f[now];
f[v]=ch[now][i];q.push(v);
}
else ch[u][i]=ch[f[u]][i];
}
}
}
void query(char *s){
int n=strlen(s);
stack<P>S;int u=0;
while(!S.empty())S.pop();
for(int i=0;i<n;i++){
int c=s[i]-‘a‘;
while(u&&!~ch[u][c])u=f[u];
u=ch[u][c];S.push(P(c,u));
if(cnt[u]){
for(int j=1;j<=cnt[u];j++)
S.pop();
if(!S.empty())u=S.top().y;
else u=0;
}
}
vector<char>ans;
while(!S.empty())
ans.push_back(S.top().x+‘a‘),S.pop();
for(int i=ans.size()-1;~i;i--)
printf("%c",ans[i]);
}
}Aho;
char str[N],s[N];
int main(){
scanf("%s",str);
int n;scanf("%d",&n);
Aho.init();
for(int i=1;i<=n;i++){
memset(s,0,sizeof s);
scanf("%s",s);
Aho.ins(s);
}
Aho.build();
Aho.query(str);
}
bzoj3940[usaco2015feb]censoring*
bzoj3940[Usaco2015Feb]Censoring题意:有一个S串和一大堆T串,不断地在S串里找最早出现的T串,然后将其删除。S串≤100000,T串总长度≤100000。题解:对所有T串建AC自动机,然后同bzoj3942。注意,本题的AC自动机必须利用所有fail函数建成... 查看详情
[bzoj3940][usaco2015feb]censoring
最近做题成双成对?不是双倍经验就是两题同解。3940 3942给定字典,给定字符串,删去字符串中所有字典内单词。保证不会出现二者包含状况。$nleq1e5,sumlenleq1e5$AC自动机裸题。build出AC自动机后从左到右插入文本串,同时... 查看详情
bzoj3940:[usaco2015feb]censoring
给个长度<=1e5的串s,再给n个模板串总长不超1e5,每次把s中起始位置最早的一个模板串删掉,求最后剩的串。AC自动机,开个栈记一下每次走到哪里,匹配成功后直接在栈里找到这一串的初始位置对应自动机上的节点,从而回... 查看详情
bzoj3940[usaco2015feb]censoring
【题目描述】FJ把杂志上所有的文章摘抄了下来并把它变成了一个长度不超过10^5的字符串S。他有一个包含n个单词的列表,列表里的n个单词记为t_1...t_N。他希望从S中删除这些单词。 FJ每次在S中找到最早出现的列表中的单词(... 查看详情
bzoj3942:[usaco2015feb]censoring
3942:[Usaco2015Feb]CensoringTimeLimit: 10Sec MemoryLimit: 128MBSubmit: 404 Solved: 221[Submit][Status][Discuss]DescriptionFarmerJohnhaspurchasedasubscriptiont 查看详情
bzoj3942:[usaco2015feb]censoringkmp+栈
好久没写kmp都不会写了……开两个栈,s存当前串,c存匹配位置用t串在栈s上匹配,栈每次入栈一个原串字符,用t串匹配一下,如果栈s末尾匹配了t则弹栈#include<iostream>#include<cstdio>#include<cstring>usingnamespacestd;constintN=1... 查看详情
3940.[usaco15feb]censoringac自动机+栈(代码片段)
DescriptionFarmerJohnhaspurchasedasubscriptiontoGoodHooveskeepingmagazineforhiscows,sotheyhaveplenty ofmaterialtoreadwhilewaitingaroundinthebarnduringmilkingsessions.Unfortunately,thelatest 查看详情
bzoj3942[usaco2015feb]censoring*
bzoj3942[Usaco2015Feb]Censoring题意:有一个S串和一个T串,不断地在S串里匹配T串,然后将其删除。S串、T串长度≤1000000。题解:用1、2两个栈,每次将S串的当前字符压入1栈,当前匹配到T串的位置压入2栈,如果匹配出一个T串,则让1... 查看详情
最大生成树bzoj3943[usaco2015feb]superbull
TimeLimit: 10Sec MemoryLimit: 128MBSubmit: 374 Solved: 217[Submit][Status][Discuss]DescriptionBessieandherfriendsareplayinghoofballintheannualSuperbullc 查看详情
bzoj_3942_[usaco2015feb]censoring_kmp
BZOJ_3942_[Usaco2015Feb]Censoring_KMPDescription有一个S串和一个T串,长度均小于1,000,000,设当前串为U串,然后从前往后枚举S串一个字符一个字符往U串里添加,若U串后缀为T,则去掉这个后缀继续流程。InputThefirstlinewillcontainS.Thesecondlinewill... 查看详情
bzoj2015:[usaco2010feb]chocolategivingspfa
因为是双向边,所以相当于两条到1的最短路和,先跑spfa然后直接处理询问即可#include<iostream>#include<cstdio>#include<queue>usingnamespacestd;constintN=50005,inf=1e9;intn,m,b,h[N],cnt,dis[N];boolv[N];structqweintne,to, 查看详情
bzoj3939[usaco2015feb]cowhopscotch动态开点线段树优化dp
题目描述JustlikehumansenjoyplayingthegameofHopscotch,FarmerJohn‘scowshaveinventedavariantofthegameforthemselvestoplay.Beingplayedbyclumsyanimalsweighingnearlyaton,CowHopscotchalmostalwaysendsindisaster,bu 查看详情
[bzoj3943][usaco2015feb]superbull_kruskal
SuperBullbzoj-3943Usaco-2015Feb题目大意:贝西和她的朋友们在参加一年一度的“犇”(足)球锦标赛。FJ的任务是让这场锦标赛尽可能地好看。一共有N支球队参加这场比赛,每支球队都有一个特有的取值在1-230-1之间的整数编号(即... 查看详情
bzoj3939[usaco2015feb]cowhopscotch
传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3939【题解】f[i][j]=s[i-1][j-1]-sum[a[i][j]]用cdq分治来处理横坐标,先处理上面的dp值,再讨论上面部分对下面的贡献,然后分治处理下面的dp值即可。如果加了快读好像排bzojrk1?#include<s... 查看详情
bzoj3943[usaco2015feb]superbull:最大生成树
题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=3943题意: 有n只队伍,每个队伍有一个编号a[i]。 每场比赛有两支队伍参加,然后选一支队伍淘汰。共进行n-1场比赛,然后比赛结束。 若某场比赛是队伍i和j参加,则该... 查看详情
bzoj3364:[usaco2004feb]distancequeries距离咨询
Description一棵树,询问两点间距离.Sol倍增.方向没用.没有然后了.Code/**************************************************************Problem:3364User:BeiYuLanguage:C++Result:AcceptedTime:400msMemory:11556kb******************** 查看详情
[bzoj2591][usaco2012feb]nearbycows
2591:[Usaco2012Feb]NearbyCowsTimeLimit:4Sec MemoryLimit:128MBSubmit:149 Solved:89[Submit][Status][Discuss]Description FarmerJohnhasnoticedthathiscowsoftenmovebetweennearbyfi 查看详情
bzoj1651:[usaco2006feb]stallreservations专用牛棚
二次联通门: BZOJ1651:[Usaco2006Feb]StallReservations专用牛棚 权限题放题面DescriptionOhthosepickyN(1<=N<=50,000)cows!TheyaresopickythateachonewillonlybemilkedoversomeprecisetimeintervalA.. 查看详情