首页 > 代码库 > Bzoj4212--神牛养成计划

Bzoj4212--神牛养成计划

2024-09-17 10:48:12   214人阅读

正规题解传送门 ： https://zyqn.tech/?p=3163

但是我们发现n只有2000，于是可以建出trie树然后愉快的bitset去搞。

直接对于trie上每个节点开个bitset空间爆炸。但是有很多是重复的，所以我们想虚树一样建，每个节点只存一个link指针。

代码 ： 

技术分享
#include<bits/stdc++.h>#define INF 0x3f3f3f3f#define eps 1e-9#define LL long longusing namespace std;#define int intinline int Max(int a,int b) {return a>b?a:b;}inline int Min(int a,int b) {return a<b?a:b;}inline int Sqr(int a) {return a*a;}inline int Abs(int a) {return a>0?a:-a;}#undef int#define MAXN 2000006int n,m,ans;bitset<2005> x,pol[100005];int tot;char s[MAXN];struct Trie{    int tra[MAXN][27],lk[MAXN],cnt;    void Init() {        memset(tra,0,sizeof(tra));        cnt=1;    }        void Build(int v) {        int fr=0;        for(int i=0;i<27;i++) {            if(!tra[v][i]) continue;            Build(tra[v][i]);            if(!fr) lk[v]=lk[tra[v][i]],fr=1;            else if(fr==1) {                tot++;pol[tot]=pol[lk[v]];                pol[tot]|=pol[lk[tra[v][i]]];                lk[v]=tot;fr=2;            }            else pol[lk[v]]|=pol[lk[tra[v][i]]];        }    }        void Insert(int k,char *s,int len) {        int now=1;        for(int i=0;i<len;i++) {            if(!tra[now][s[i]-‘a‘]) now=tra[now][s[i]-‘a‘]=++cnt;            else now=tra[now][s[i]-‘a‘];        }        if(!lk[now]) lk[now]=++tot;        pol[lk[now]][k]=1;    }    int Patten(char *s,int len) {        int now=1;        for(int i=0;i<len;i++) {            if(!tra[now][s[i]-‘a‘]) return 0;            now=tra[now][s[i]-‘a‘];        }        return lk[now];    }}hd,bk;inline void Updata(int n) {    for(int i=0;i<n;i++)         s[i]=((s[i]-‘a‘+ans)%26)+‘a‘;}int main() {    hd.Init();bk.Init();    scanf("%d",&n);    for(int len,i=1;i<=n;i++) {        scanf("%s",s);        len=strlen(s);        hd.Insert(i,s,len);        reverse(s,s+len);        bk.Insert(i,s,len);    }    hd.Build(1);    bk.Build(1);    scanf("%d",&m);    for(int len,i=1;i<=m;i++) {        x.set();        scanf("%s",s);        len=strlen(s);        Updata(len);        x&=pol[hd.Patten(s,len)];                scanf("%s",s);        len=strlen(s);        reverse(s,s+len);        Updata(len);        x&=pol[bk.Patten(s,len)];                ans=x.count();        printf("%d\n",ans);    }    return 0;}
View Code

 

Bzoj4212--神牛养成计划


联系
我们