QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#401497 | #850. Edit Distance Yet Again | xuqin | WA | 7ms | 19368kb | C++14 | 4.3kb | 2024-04-28 20:33:15 | 2024-04-28 20:33:15 |
Judging History
answer
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cassert>
#include<set>
#include<random>
#include<chrono>
#include<bitset>
#include<map>
#include<queue>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<string>
#define eb emplace_back
using namespace std;
const int maxn=1e6+10, maxm=1e6+10, inf=2e9+10;
const double eps=1e-10;
typedef long long LL;
typedef unsigned long long ULL;
const LL INF=4e18;
typedef pair<LL, int> pli;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
inline int read() {
int x=0, f=1; char c=getchar();
for(; c<'0'||c>'9'; c=getchar()) if(c=='-') f=0;
for(; c>='0'&&c<='9'; c=getchar()) x=x*10+c-'0';
return f?x:-x;
}
int P;
mt19937 rnd((unsigned)chrono::steady_clock::now().time_since_epoch().count());
inline int ksm(int x, int y) {
int s=1;
for(; y; y>>=1, x=1LL*x*x%P)
if(y&1) s=1LL*s*x%P;
return s;
}
inline int add(int x, int y) {x+=y; return x>=P?x-P:x;}
inline int del(int x, int y) {x-=y; return x<0?x+P:x;}
LL gcd(LL x, LL y) {return y?gcd(y, x%y):x;}
const int B1=1607, B2=1609, M1=1000010747, M2=1000010749;
int pw[3][maxn];
char s[maxn], t[maxn]; int n, m, k;
struct pj{
int hsh[3][maxn];
inline void init(int sz, char ss[maxn]) {
for(int i=1; i<=sz; ++i)
hsh[1][i]=(1LL*hsh[1][i-1]*B1%M1+ss[i]-'a'+1)%M1,
hsh[2][i]=(1LL*hsh[2][i-1]*B2%M2+ss[i]-'a'+1)%M2;
}
inline pii gethsh(int l, int r) {
return make_pair((hsh[1][r]-1ll*hsh[1][l-1]*pw[1][r-l+1]%M1+M1)%M1,
(hsh[2][r]-1ll*hsh[2][l-1]*pw[2][r-l+1]%M2+M2)%M2);
}
} S, T;
inline int lcp(int p, int q) {//lcp(s[p, n] t[q, m])
int l=0, r=min(n-p+1, m-q+1);
while(l<r) {
int mid=(l+r+1)>>1;
if(S.gethsh(p, p+mid-1)==T.gethsh(q, q+mid-1)) l=mid; else r=mid-1;
}
return l;
}
int dp[1010][2020], f[2020];
int pr[1010][2020];
inline void sol() {
n=read(), m=read(), k=read();
scanf("%s", s+1); S.init(n, s);
scanf("%s", t+1); T.init(m, t);
int M=1010;
dp[0][M]=lcp(1, 1);//(x, x+i) (n, n+(m-n))
if(m==n&&dp[0][M]==n) return printf("YES\n0\n"), void();
int ii=-1, jj=-1;
for(int i=1; i<=k; ++i) {
for(int j=M-i; j<=M+i; ++j) f[j]=-1;
for(int j=M-(i-1); j<=M+(i-1); ++j) {
int x=dp[i-1][j];
if(x==-1) continue;
int y=x+(j-M);
//(x, y)->(x+1, y)
if(x<n) {
int nx=x+1, ny=y, d=lcp(nx+1, ny+1);
nx+=d, ny+=d;
if(nx>f[ny-nx+M]) {
f[ny-nx+M]=nx;
pr[i][ny-nx+M]=j;
}
}
//(x, y)->(x, y+1)
if(y<m) {
int nx=x, ny=y+1, d=lcp(nx+1, ny+1);
nx+=d, ny+=d;
if(nx>f[ny-nx+M]) {
f[ny-nx+M]=nx;
pr[i][ny-nx+M]=j;
}
}
//(x, y)->(x+1, y+1)
if(x<n&&y<m) {
int nx=x+1, ny=y+1, d=lcp(nx+1, ny+1);
nx+=d, ny+=d;
if(nx>f[ny-nx+M]) {
f[ny-nx+M]=nx;
pr[i][ny-nx+M]=j;
}
}
}
// printf("th=%d\n", i);
for(int j=M-i; j<=M+i; ++j) {
dp[i][j]=f[j];
// if(f[j]!=-1) printf("(%d, %d)\n", f[j], f[j]+j-M);
}
//chk
if(-i<=m-n&&m-n<=i&&dp[i][M+m-n]==n) {
ii=i, jj=M+m-n; break;
}
}
if(ii==-1) return puts("NO"), void();
printf("YES\n%d\n", ii);
return;
while(ii>0) {
int nw=dp[ii][jj], pre=pr[ii][jj];
// printf("pre=%d\n", pre-M);
int p=dp[ii-1][pre];
//(nw, nw+jj-M)
//(p, p+pre-M)
if(jj==pre) {
printf("REPLACE %d %c\n", p+1, t[p+pre-M+1]);
} else if(jj==pre+1) {
printf("INSERT %d %c\n", p+1, t[p+pre-M+1]);
} else if(jj==pre-1) {
printf("DELETE %d\n", p+1);
}
--ii; jj=pre;
}
}
int main() {
pw[1][0]=pw[2][0]=1;
for(int i=1; i<=1000000; ++i)
pw[1][i]=1LL*pw[1][i-1]*B1%M1, pw[2][i]=1LL*pw[2][i-1]*B2%M2;
int T=read();
while(T--) sol();
return 0;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 7ms
memory: 19368kb
input:
2 3 4 3 kot plot 5 7 3 zycie porazka
output:
YES 2 NO
result:
wrong answer Test 0: incorrect operation in output