正文

bzoj3940:[usaco2015feb]censoring

Blue233333  Blue233333  2022-09-17  351

关键词：

给个长度<=1e5的串s，再给n个模板串总长不超1e5，每次把s中起始位置最早的一个模板串删掉，求最后剩的串。

AC自动机，开个栈记一下每次走到哪里，匹配成功后直接在栈里找到这一串的初始位置对应自动机上的节点，从而回到刚才的样子就行了。

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<stdlib.h>
 4 #include<algorithm>
 5 //#include<iostream>
 6 using namespace std;
 7 
 8 #define maxs 100011
 9 char s[maxs],p[maxs];int n,len;
10 struct Trie
11 {
12     int ch[maxs][27],size;
13     int fail[maxs],last[maxs],dep[maxs];bool val[maxs];
14     Trie() {size=0;memset(ch[0],0,sizeof(ch[0]));dep[0]=0;}
15     int idx(char s) {return s-‘a‘;}
16     void insert(char* s)
17     {
18         int len=strlen(s),now=0;
19         for (int i=0;i<len;i++)
20         {
21             int u=idx(s[i]);
22             if (!ch[now][u])
23             {
24                 size++;
25                 memset(ch[size],0,sizeof(ch[size]));
26                 val[size]=0;
27                 ch[now][u]=size;
28                 dep[size]=dep[now]+1;
29             }
30             now=ch[now][u];
31         }
32         val[now]=1;
33     }
34     int sta[maxs],top;char ans[maxs];
35     void match(char* t)
36     {
37         int len=strlen(t),now=0;top=0;
38         for (int i=0;i<len;i++)
39         {
40             int u=idx(t[i]);
41             now=ch[now][u];
42             sta[++top]=now;
43             ans[top]=t[i];
44             if (val[now])
45             {
46                 top-=dep[now];
47                 now=sta[top];
48             }
49         }
50     }
51     int que[maxs],head,tail;
52     void makefail()
53     {
54         head=tail=fail[0]=0;
55         for (int i=0;i<26;i++)
56         {
57             int u=ch[0][i];
58             if (u)
59             {
60                 fail[u]=0;
61                 que[tail++]=u;
62                 last[u]=0;
63             }
64         }
65         while (head!=tail)
66         {
67             const int now=que[head++];
68             for (int i=0;i<26;i++)
69             {
70                 const int u=ch[now][i];
71                 if (!u) {ch[now][i]=ch[fail[now]][i];continue;}
72                 que[tail++]=u;
73                 fail[u]=ch[fail[now]][i];
74                 last[u]=val[fail[now]]?fail[now]:last[fail[now]];
75             }
76         }
77     }
78 }t;
79 int main()
80 {
81     scanf("%s",s);
82     scanf("%d",&n);
83     for (int i=1;i<=n;i++)
84     {
85         scanf("%s",p);
86         t.insert(p);
87     }
88     t.makefail();
89     t.match(s);
90     t.ans[t.top+1]=‘‘;
91     puts(t.ans+1);
92     return 0;
93 }

View Code

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 查看详情

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... 查看详情

bzoj3942:[usaco2015feb]censoringkmp+栈

好久没写kmp都不会写了……开两个栈，s存当前串，c存匹配位置用t串在栈s上匹配，栈每次入栈一个原串字符，用t串匹配一下，如果栈s末尾匹配了t则弹栈#include<iostream>#include<cstdio>#include<cstring>usingnamespacestd;constintN=1... 查看详情

bzoj3943[usaco2015feb]superbull：最大生成树

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3943题意：　　有n只队伍，每个队伍有一个编号a[i]。　　每场比赛有两支队伍参加，然后选一支队伍淘汰。共进行n-1场比赛，然后比赛结束。　　若某场比赛是队伍i和j参加，则该... 查看详情

[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.. 查看详情

[bzoj]1631:[usaco2007feb]cowparty

1631:[Usaco2007Feb]CowPartyTimeLimit:5Sec MemoryLimit:64MBSubmit:866 Solved:624[Submit][Status][Discuss]Description 农场有N(1≤N≤1000)个牛棚，每个牛棚都有1只奶牛要参加在X 查看详情