社区讨论

90分,第四个点WA

P2292[HNOI2004] L 语言参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@mi6lg14b
此快照首次捕获于
2025/11/20 06:48
4 个月前
此快照最后确认于
2025/11/20 06:48
4 个月前
查看原帖
CPP
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
#define fo(a,b,c) for(int a=b;a<=c;a++)
int read(){
    int a=0,f=0;char c=getchar();
    for(;c<'0'||c>'9';c=getchar())if(c=='-')f=1;
    for(;c>='0'&&c<='9';c=getchar())a=a*10+c-'0';
    return f?-a:a;
}
const int N=1e5;
int son[N][26],count[N],len[N],fail[N],q[N],able[10];
string s;
int main(){
    //freopen("in.txt","r",stdin);
    int n=read(),m=read(),cnt=0;
    fo(i,1,n){
        cin>>s;int p=0;len[i]=s.length();
        fo(j,0,len[i]-1){
            int idx=s[j]-'a';
            if(!son[p][idx])
                son[p][idx]=++cnt;
            p=son[p][idx];
        }
        count[p]=1<<i;
    }
    for(int st=0,ed=0;st<=ed;st++){
        int u=q[st];
        count[u]|=count[fail[u]];
        fo(i,0,25){
            int v=son[u][i];
            if(v)q[++ed]=v;
            else son[u][i]=son[fail[u]][i];
            if(u&&v)fail[v]=son[fail[u]][i];            
        }
    }
    fo(i,1,m){
        cin>>s;
        memset(able,0,sizeof(able));able[9]=1;
        int ans=0,p=0,j,sum=1;
        for(j=0;j<s.length();able[(++j)%10]=0){
            int idx=s[j]-'a';
            p=son[p][idx];
            for(int x=count[p]>>1,k=1;x;x>>=1,k++)if(x&1)
                able[j%10]|=able[(j-len[k]+10)%10];
            sum+=able[j%10]-able[(j+1)%10];
            if(!sum)break;
        }
        if(!sum){printf("%d\n",j-8);continue;}
        while(!able[j%10])j--;
        printf("%d\n",j+1);
    }
    return 0;
}

回复

0 条回复,欢迎继续交流。

正在加载回复...