QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#352928#5312. Levenshtein Distancezsq147258369WA 1438ms810964kbC++142.6kb2024-03-13 18:25:512024-03-13 18:25:51

Judging History

你现在查看的是最新测评结果

  • [2024-03-13 18:25:51]
  • 评测
  • 测评结果:WA
  • 用时:1438ms
  • 内存:810964kb
  • [2024-03-13 18:25:51]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+50,M=65,ba=31,mod=998244353;

int *a=new int[N]+100000;
int n,m,k,h[N],mi[N],ans[M],st[N][20],p[N],d[N];
char s[N],t[N],g[N];

void solve(int*hs,char*s)
{
    int n=strlen(s+1);
    for(int i=1;i<=n;i++)hs[i]=(hs[i-1]*ba+s[i]-'a'+1)%mod;
}

int find(int l,int r)
{
    return (h[r]-h[l-1]*mi[r-l+1]%mod+mod)%mod;
}

int findlen(int a,int b)
{
    if(!b)return 0;
    int len=0,l=1,r=n+m-max(a,b)+1;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(find(a,mid+a-1)==find(b,mid+b-1))len=mid,l=mid+1;
        else r=mid-1;
    }
    return len;
}

bool cmp(int a,int b)
{
    int len=findlen(a,b);
    return g[a+len]<g[b+len];
}

int lcp(int l,int r)
{
    if(l>n||r>m)return 0;
    int mx=min(n-l+1,m-r+1);
    r+=n;l=d[l],r=d[r];r--;
    if(l>r)swap(l,r);
    int k=log2(r-l+1);
    return min(min(st[l][k],st[r-(1<<k)+1][k]),mx);
}

main()
{
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
    cin>>k>>(s+1)>>(t+1);
    n=strlen(s+1),m=strlen(t+1);
    mi[0]=1;
    for(int i=1;i<=n+m;i++)mi[i]=mi[i-1]*ba%mod;
    for(int i=1;i<=n;i++)g[i]=s[i];
    for(int i=1;i<=m;i++)g[i+n]=t[i];
    for(int i=1;i<=n+m;i++)h[i]=(h[i-1]*ba+g[i]-'a'+1)%mod,p[i]=i;
    sort(p+1,p+1+n+m,cmp);
    for(int i=1;i<=n+m;i++)d[p[i]]=i,st[i][0]=findlen(p[i],p[i+1]);
    for(int i=1;(1<<i)<=n+m;i++)for(int j=1;j+(1<<i)-1<=n+m;j++)st[j][i]=min(st[j][i-1],st[j+(1<<i-1)][i-1]);
    for(int i=1;i<=m;i++)
    {
        int *f[35],*g=new int[2*k+1]+k;
        for(int j=-k;j<=k;j++)g[j]=1e18;
        f[0]=new int[1];f[0][0]=0;
        for(int j=0;j<=k;j++)
        {
            f[j+1]=new int[2*j+3]+j+1;
            for(int z=-j-1;z<=j+1;z++)f[j+1][z]=0;
            for(int z=-j;z<=j;z++)if(z+f[j][z]>=0&&i+f[j][z]+z-1<=m)
            {
                // cout<<f[j][z]<<' '<<f[j][z]+z<<' '<<j<<' '<<z<<'\n';
                f[j][z]+=lcp(f[j][z]+1,i+f[j][z]+z);
                if(f[j][z]==n)g[z]=min(g[z],j);
                int w=min(n,1+f[j][z]),f1=f[j][z]<n,f2=(z+f[j][z])<m;
                if(f1&&f2)f[j+1][z]=max(f[j+1][z],w);
                if(f2)f[j+1][z+1]=max(f[j+1][z+1],f[j][z]);
                if(f1)f[j+1][z-1]=max(f[j+1][z-1],w);
            }
        }
        for(int j=-k;j<=k;j++)if(n+j>=1&&n+j<=m-i+1)
        {
            int w=1e18;
            for(int z=-k;z<=k;z++)if(n+z>=1&&n+z<=m-i+1&&g[z]<=k)w=min(w,abs(z-j)+g[z]);
            // cout<<j<<' '<<w<<'\n';
            if(w<=k)ans[w]++;
        }
    }
    for(int i=0;i<=k;i++)cout<<ans[i]<<'\n';
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 5796kb

input:

4
aaa
aabbaab

output:

0
5
15
7
1

result:

ok 5 number(s): "0 5 15 7 1"

Test #2:

score: 0
Accepted
time: 1438ms
memory: 459916kb

input:

30
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 31 numbers

Test #3:

score: -100
Wrong Answer
time: 1090ms
memory: 810964kb

input:

30
BBAAABAABBBA
ABBABBBBAABAAAABABBBAABAABBAABAAAAAABAABABBAAAABAAAAABABAABAABBABBAAAABBBBAABBABAAABAABAABBBBBABBABABBBBABBBBAAABBABABBBBAAABBBBAAAABABABABABABABAAABBBBBAABAABAABBAABBBAABBBBBBBABAABAABAABABAABAAABAABBBAABABBABBAAABAAAABABABBABBBAAABBBAAAABBBBABABABAABAABBBBBBBBBAABBBABABBBABAABBABBA...

output:

16
657
8223
50283
166630
310113
345478
280404
227214
209185
203018
198563
105119
102148
99771
97732
96060
94733
93636
92722
92060
91525
91144
90832
90587
90420
90289
90201
90120
90068
90035

result:

wrong answer 1st numbers differ - expected: '17', found: '16'