本人35->AC经历,可能会帮到你~
查看原帖
本人35->AC经历,可能会帮到你~
753553
Resonate楼主2024/8/1 10:33

第一次,35pts,5WA 3TLE 1RE 5AC

#include<bits/stdc++.h>
#define int long long
using namespace std;
string a,b;
int a_len,b_len;
int z[22222222];
int l,r;
int p[22222222];
int z_qz,p_qz;
signed main()
{
    cin>>a>>b;
    a_len=a.size(),b_len=b.size();
    a='0'+a,b='0'+b;
    z[1]=b_len;
    for(int i=2;i<=b_len;i++)
    {
        if(i<=r)
        {
            z[i]=min(z[i-l+1],r-i+1);
        }
        while(b[i+z[i]]==b[1+z[i]])
        {
            z[i]++;
        }
        if(i+z[i]-1>r)
        {
            l=i,r=i+z[i]-1;
        }
    }
    for(int i=1;i<=b_len;i++)
    {
        z_qz^=(i*(z[i]+1));
    }
    printf("%lld",z_qz);
    puts("");
    l=0,r=0;
    for(int i=1;i<=a_len;i++)
    {
        if(i<=r)
        {
            p[i]=min(p[i-l+1],r-i+1);
        }
        while(a[i+p[i]]==b[1+p[i]])
        {
            p[i]++;
        }
        if(i+p[i]-1>r)
        {
            l=i,r=i+p[i]-1;
        }
    }
    for(int i=1;i<=a_len;i++)
    {
        p_qz^=(i*(p[i]+1));
    }
    printf("%lld",p_qz);
}

第二次,93pts,13AC 1RE

将(位置后半段if判断里)

p[i]=min(p[i-l+1],r-i+1);

改为

p[i]=min(z[i-l+1],r-i+1);

第三次,12AC 2TLE

添加防越界条件

while(i+z[i]<=b_len and b[i+z[i]]==b[1+z[i]])

andand

while(i+p[i]<=a_len and a[i+p[i]]==b[1+p[i]])

第四次,AC( •̀ ω •́ )y

添加快读,cin太慢了(数据大于10^6建议使用快读)

2024/8/1 10:33
加载中...