QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #85895 | #850. Edit Distance Yet Again | eyiigjkn | AC ✓ | 3294ms | 52608kb | C++14 | 2.2kb | 2023-03-08 20:45:12 | 2023-03-08 20:45:14 |
Judging History
answer
# include <bits/stdc++.h>
using namespace std;
using ll=long long;
using Hash=pair<int,int>;
constexpr int N=1e6,p1=1e9+7,p2=1e9+9,Base=998244353;
int n,m,K;
char s1[1000010],s2[1000010];
Hash pw[1000010],sum1[1000010],sum2[1000010];
struct Info
{
int v,x,y;
Info(){}
Info(int v,int x,int y):v(v),x(x),y(y){}
Info &operator+=(const Info &t)
{
if(v<t.v) *this=t;
return *this;
}
}f[1010][2010];
inline Hash operator+(const Hash &x,const Hash &y){return {(x.first+y.first)%p1,(x.second+y.second)%p2};}
inline Hash operator-(const Hash &x,const Hash &y){return {(x.first-y.first+p1)%p1,(x.second-y.second+p2)%p2};}
inline Hash operator*(const Hash &x,const Hash &y){return {(ll)x.first*y.first%p1,(ll)x.second*y.second%p2};}
inline Hash geths1(int l,int r){return sum1[r]-pw[r-l+1]*sum1[l-1];}
inline Hash geths2(int l,int r){return sum2[r]-pw[r-l+1]*sum2[l-1];}
int calc(int x,int y)
{
int l=0,r=min(n-x+1,m-y+1),mid;
while(l<r)
{
mid=(l+r+1)/2;
if(geths1(x,x+mid-1)==geths2(y,y+mid-1)) l=mid;
else r=mid-1;
}
return l;
}
void getans(int k,int x,int y)
{
printf("YES\n%d\n",k);
for(;k;k--)
{
Info t=f[k][y-x+K];
int tx=t.x,ty=t.y;
if(y-x==ty-tx) printf("REPLACE %d %c\n",tx+1,s2[ty+1]);
else if(y-x==ty-tx-1) printf("DELETE %d\n",tx+1);
else printf("INSERT %d %c\n",tx+1,s2[ty+1]);
x=tx;y=ty;
}
}
int main()
{
int T;
cin>>T;
pw[0]={1,1};
for(int i=1;i<=N;i++) pw[i]=pw[i-1]*Hash{Base,Base};
while(T--)
{
bool ok=0;
scanf("%d%d%d%s%s",&n,&m,&K,s1+1,s2+1);
for(int i=1;i<=n;i++) sum1[i]=sum1[i-1]*Hash{Base,Base}+Hash{s1[i],s1[i]};
for(int i=1;i<=m;i++) sum2[i]=sum2[i-1]*Hash{Base,Base}+Hash{s2[i],s2[i]};
for(int i=0;i<=K;i++) fill(f[i],f[i]+2*K+1,Info(-1,0,0));
f[0][K]=Info(calc(1,1),0,0);
for(int i=0;i<=K && !ok;i++)
for(int j=-K;j<=K;j++)
if(~f[i][j+K].v)
{
int x=f[i][j+K].v,y=x+j;
if(x==n && y==m)
{
ok=1;getans(i,x,y);
break;
}
if(i<K && x<n && y<m) f[i+1][j+K]+=Info(x+1+calc(x+2,y+2),x,y);
if(i<K && x<n && j>-K) f[i+1][j-1+K]+=Info(x+1+calc(x+2,y+1),x,y);
if(i<K && y<m && j<K) f[i+1][j+1+K]+=Info(x+calc(x+1,y+2),x,y);
}
if(!ok) puts("NO");
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 6ms
memory: 11420kb
input:
2 3 4 3 kot plot 5 7 3 zycie porazka
output:
YES 2 INSERT 2 l REPLACE 1 p NO
result:
ok OK!
Test #2:
score: 0
Accepted
time: 12ms
memory: 12072kb
input:
100 100 100 0 mmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm mmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm 16 7 100 vvvvvvvvvvvvvvvv qydopaq 37 33 43 ggggggggggggggggggggggggggggggggggggg osk...
output:
YES 0 YES 16 REPLACE 16 q REPLACE 15 a REPLACE 14 p REPLACE 13 o REPLACE 12 d REPLACE 11 y REPLACE 10 q DELETE 9 DELETE 8 DELETE 7 DELETE 6 DELETE 5 DELETE 4 DELETE 3 DELETE 2 DELETE 1 YES 28 REPLACE 37 o REPLACE 36 o REPLACE 35 a REPLACE 34 a REPLACE 31 p REPLACE 29 k REPLACE 28 c REPLACE 27 o REPL...
result:
ok OK!
Test #3:
score: 0
Accepted
time: 2029ms
memory: 35092kb
input:
100 3211 3185 685 wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww...
output:
YES 552 REPLACE 3211 f REPLACE 3201 b REPLACE 3198 a REPLACE 3192 v REPLACE 3188 g REPLACE 3181 l REPLACE 3176 q REPLACE 3173 j REPLACE 3168 y REPLACE 3158 y REPLACE 3149 m REPLACE 3147 x REPLACE 3113 p REPLACE 3109 n REPLACE 3108 n REPLACE 3105 g REPLACE 3102 g REPLACE 3096 e REPLACE 3095 d REPLACE...
result:
ok OK!
Test #4:
score: 0
Accepted
time: 2700ms
memory: 52456kb
input:
5 999000 998976 995 llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll...
output:
YES 894 REPLACE 998911 h REPLACE 996108 x REPLACE 996096 g REPLACE 994700 i REPLACE 994360 u REPLACE 993105 q REPLACE 993027 q REPLACE 992787 w REPLACE 991955 u REPLACE 990316 v REPLACE 989560 d REPLACE 989480 y REPLACE 989317 n REPLACE 988977 d REPLACE 988162 w REPLACE 988083 e REPLACE 985762 v REP...
result:
ok OK!
Test #5:
score: 0
Accepted
time: 3294ms
memory: 52404kb
input:
5 999000 998971 1000 lllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll...
output:
NO NO NO NO NO
result:
ok OK!
Test #6:
score: 0
Accepted
time: 696ms
memory: 52608kb
input:
5 1000000 1000000 1000 faafaffaaffafaafaffafaaffaafaffaaffafaaffaafaffafaafaffaaffafaafaffafaaffaafaffafaafaffaaffafaaffaafaffaaffafaafaffafaaffaafaffaaffafaaffaafaffafaafaffaaffafaaffaafaffaaffafaafaffafaaffaafaffafaafaffaaffafaafaffafaaffaafaffaaffafaaffaafaffafaafaffaaffafaafaffafaaffaafaffafaafa...
output:
YES 246 INSERT 2049 f REPLACE 2047 a INSERT 2045 f INSERT 2042 f INSERT 2041 a INSERT 2036 f INSERT 2035 a INSERT 2034 a INSERT 2033 f INSERT 2024 f INSERT 2023 a INSERT 2022 a INSERT 2021 f INSERT 2020 a INSERT 2019 f INSERT 2018 f INSERT 2017 a INSERT 1970 f REPLACE 1967 a INSERT 1965 f DELETE 195...
result:
ok OK!
Test #7:
score: 0
Accepted
time: 2780ms
memory: 52508kb
input:
5 999900 999925 992 ejqwvowvntrtmokrfeqeybcvgsupftozhkdsyytrioxrzbahikexefgyhpwbcztcydqiibxukojvgedldgmjufkzwttpvftctkpajgpwiklfzrkjxzsltqdbfdyxqpswrrlkdbmwckbhbfpqqgnhcixcnmphjulyykqfvdrqsdskbxqlqvekhwmvzmtqannmxrjgqcpdpofmqozyicaiqjikqxkeolandjydgvtjhnzubpdtkxymaxffnopnnrpnedobnfljcvtqwmuxdctutidm...
output:
YES 938 INSERT 999192 g DELETE 999157 REPLACE 998754 g INSERT 998259 b INSERT 998188 g DELETE 998145 REPLACE 997378 t DELETE 997088 INSERT 994695 t REPLACE 993971 b DELETE 990472 REPLACE 988552 t DELETE 987640 DELETE 985945 DELETE 985429 DELETE 983806 INSERT 983299 t REPLACE 981534 g INSERT 978807 t...
result:
ok OK!