正文

bzoj3940&&bzoj3942

友人A  友人A  2022-09-01  375

关键词：

方法就是维护一个动态栈记录栈的每一位匹配到串的哪一位的编号第一道kmp第二道ac自动机自己理会

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int M=1000055;
char stack[M],s[M],t[M],f[M],next[M];
int len,top;
void getfail(){
    for(int i=1;i<len;i++){
        int j=f[i];
        while(j&&t[i]!=t[j]) j=f[j];
        f[i+1]=(t[i]==t[j]?j+1:0);
    }
}
int main()
{
    scanf("%s %s",s,t);
    int L=strlen(s); len=strlen(t); getfail(); 
    for(int i=0;i<L;i++){
        stack[++top]=s[i];
        int j=next[top-1];
        while(j&&t[j]!=stack[top]) j=f[j];
        if(t[j]==stack[top]) j++;
        next[top]=j;
        if(j==len) top-=len;
    }
    for(int i=1;i<=top;i++) printf("%c",stack[i]);
    return 0;
}

View Code

//同bzoj3942 
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int size=27,M=100055;
char s[M],T[M],stack[M];
int next[M],top,n;
struct node{
    int sum,a[M][27],last[M],fail[M],val[M];
    int id(char s) {return s-‘a‘+1;}
    void insert(char s[]){
        int k=0,L=strlen(s);
        for(int i=0;i<L;i++){
            int now=id(s[i]);
            if(!a[k][now]) a[k][now]=++sum;
            k=a[k][now];
        }
        val[k]=L;
    }
    void getfail(){
        int q[M],k=0,head=0,tail=0;
        for(int i=1;i<=26;i++){
            int now=a[0][i];
            if(now) q[tail++]=now;
        }
        while(head!=tail){
            int x=q[head++];
            for(int i=1;i<=26;i++){
                int now=a[x][i];
                if(!now) { a[x][i]=a[fail[x]][i];continue;}
                q[tail++]=now;
                fail[now]=a[fail[x]][i];
                last[now]=val[fail[now]]?fail[now]:last[fail[now]];
            }
        }
    }
    void Ac_boy(){
        int now=0,L=strlen(T);
        for(int i=0;i<L;i++){
            int d=id(T[i]);
            stack[top]=T[i];
            now=a[now][d];
            next[top]=now;
            if(val[now]) top-=val[now],now=next[top];
            else if(last[now]) top-=val[last[now]],now=next[top];
            top++;
        }
    }
}node;
int main()
{
    scanf("%s",T);
    int n; scanf("%d",&n);
    while(n--) scanf("%s",s),node.insert(s);
    node.getfail(); node.Ac_boy();
    for(int i=0;i<top;i++) putchar(stack[i]);
    return 0;
}

View Code

bzoj1411&&vijos1544:[zjoi2009]硬币游戏递推，快速幂

1411:[ZJOI2009]硬币游戏TimeLimit:10Sec MemoryLimit:162MBSubmit:897 Solved:394[Submit][Status][Discuss]DescriptionOrez很喜欢玩游戏，他最近发明了一款硬币游戏。他在桌子的边缘上划分出2*n个位置并按顺时针把它们标号为1，2，…&he... 查看详情

censoring（bzoj3940）

DescriptionFarmerJohnhaspurchasedasubscriptiontoGoodHooveskeepingmagazineforhiscows,sotheyhaveplenty ofmaterialtoreadwhilewaitingaroundinthebarnduringmilkingsessions.Unfortunately,thelatest 查看详情

bzoj3670&&bzoj3620&&bzoj3942kmp

最近感到KMP不会啊，以前都是背板的现在要理解了。 1#include<iostream>2#include<cstring>3#include<cstdio>4#include<algorithm>5usingnamespacestd;6constintMaxn=16000;78charS[Maxn];9intk,P[Maxn],Ans; 查看详情

bzoj3940[usaco2015feb]censoring

DescriptionFarmerJohnhaspurchasedasubscriptiontoGoodHooveskeepingmagazineforhiscows,sotheyhaveplentyofmaterialtoreadwhilewaitingaroundinthebarnduringmilkingsessions.Unfortunately,thelatestissuecontain 查看详情

考后反思（bzoj3940bzoj4899bzoj3307）(代码片段)

...最后骗了五分考后主要讲一下第二题：记忆的轮廓（bzoj4899）和第三题：雨天查看详情

bzoj3940censoring

把上题的KMP改成AC自动机。注意root必须是0。因为root其实是NULL的意思。#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<queue>#definemaxn500050usingnamespacestd;chart[m 查看详情

bzoj3940[usaco2015feb]censoring*

bzoj3940[Usaco2015Feb]Censoring题意:有一个S串和一大堆T串，不断地在S串里找最早出现的T串，然后将其删除。S串≤100000，T串总长度≤100000。题解：对所有T串建AC自动机，然后同bzoj3942。注意，本题的AC自动机必须利用所有fail函数建成... 查看详情

bzoj-1878&&bzoj-2743

前言因为两题类似所以一起写了，双倍经验233Bzoj-1878看到数据范围，觉得可以莫队啊，但是不会写qwq...然后发现可以树状数组（Byhzwer然后理解了一下，大概是这样的把询问按照左右端点排序以后维护的几乎就是一个序列了 "... 查看详情

bzoj3940

AC自动机复习一下。。。可惜又写错了我们发现就是把单词建成ac自动机，然后把串在ac自动机上跑一遍，每到一个单词结束点就删除，删除是利用栈，每次弹出单词长度个字符就可以了发现两个小问题，strlen很慢，不能写在循环... 查看详情

bzoj1061&&bzoj3256

http://www.lydsy.com/JudgeOnline/problem.php?id=1061单纯形。。。先开始我不知道对偶，看着代码不知所措，并不能懂他们写的是什么。。。单纯形的标准形式是uoj上那样的，限制小于，最大化，但是这道题是最小化，而且系数取负还不行... 查看详情

bzoj3940censoring题解（ac自动机）(代码片段)

题目描述FarmerJohnhaspurchasedasubscriptiontoGoodHooveskeepingmagazineforhiscows,sotheyhaveplenty ofmaterialtoreadwhilewaitingaroundinthebarnduringmilkingsessions.Unfortunately,thelatest issueco 查看详情

bzoj3339&&bzoj3585莫队+权值分块

显然若一个数大于n就不可能是答案。12#include<iostream>3#include<cstring>4#include<cstdio>5#include<algorithm>6#include<map>7#include<cmath>8usingnamespacestd;9constintMaxn=200 查看详情

[bzoj4408&&bzoj4299][fjoi2016&&codechef]神秘数&&frbsum(主席树)

4299:CodechefFRBSUMTimeLimit:10Sec MemoryLimit:128MBSubmit:550 Solved:351[Submit][Status][Discuss]Description数集S的ForbiddenSum定义为无法用S的某个子集（可以为空）的和表示的最小的非负整数。例如，S={1,1,3,7}，则查看详情

bzoj3940:[usaco2015feb]censoring--ac自动机

3940:[Usaco2015Feb]CensoringTimeLimit: 10Sec MemoryLimit: 128MBDescriptionFarmerJohnhaspurchasedasubscriptiontoGoodHooveskeepingmagazineforhiscows,sotheyhaveplenty ofmaterial 查看详情

bzoj_3585_mex&&bzoj_3339_rmqproblem_莫队+分块

BZOJ_3585_mex&&BZOJ_3339_RmqProblem_莫队+分块Description　　有一个长度为n的数组a1,a2,...,an。m次询问，每次询问一个区间内最小没有出现过的自然数。Input　　第一行n,m。　　第二行为n个数。　　从第三行开始，每行一个询问l,r。Ou... 查看详情

bzoj_3585_mex&&bzoj_3339_rmqproblem_主席树

BZOJ_3585_mex&&BZOJ_3339_RmqProblem_主席树Description　　有一个长度为n的数组a1,a2,...,an。m次询问，每次询问一个区间内最小没有出现过的自然数。Input　　第一行n,m。　　第二行为n个数。　　从第三行开始，每行一个询问l,r。Output... 查看详情

bzoj3545&&bzoj3551peaks（离线版&&在线版）

题目给n点m边的无向图，有点权和边权每次询问求点v在经过路径上的边都不超过w的情况下，能到达的第k大的点的权值首先离线版比较容易想到，属于我现在能码出来的最难的码农题之一吧TT这道题思路是这样的1、对于边权的限... 查看详情

最小割分治(最小割树):bzoj2229&&bzoj4519(代码片段)

...有的最小割。这两个题是一样的，直接搬dinic模板即可。BZOJ2229:1#include<cstdio>2#include<cstring>3#include<algorithm>4#include<v 查看详情