QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#367630 | #850. Edit Distance Yet Again | edisnimorF | Compile Error | / | / | C++14 | 2.8kb | 2024-03-26 11:08:42 | 2024-03-26 11:08:42 |
Judging History
answer
#include<bits/stdc++.h>
#define il inline
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define pii pair<int, int>
#define fr first
#define sc second
#define ll long long
#define mset(f, z) memset(f, z, sizeof(f))
#define mcpy(f, g) memcpy(f, g, sizeof(g))
using namespace std;
template<typename T=ll>
il T rd(){
T s=0; bool f=1; char c=getchar();
while(!isdigit(c)) f^=(c=='-'), c=getchar();
while(isdigit(c)) s=s*10+c-'0', c=getchar();
return f? s:-s;
}
template<typename T> il void ckmx(T &x, T y){if(x<y) x=y;}
template<typename T> il void ckmn(T &x, T y){if(y<x) x=y;}
char _begin;
const int N=1e6+5, Mov=1005;
const int P=19260817, M1=998244353, M2=1e9+7;
ll pw1[N], pw2[N];
struct Hsh{
ll h1[N], h2[N];
void init(char *f, int len){
for(int i=1; i<=len; i++){
h1[i]=(h1[i-1]*P+f[i]-'a'+1)%M1;
h2[i]=(h2[i-1]*P+f[i]-'a'+1)%M2;
}
}
il pii que(int l, int r){
return {
(h1[r]-h1[l-1]*pw1[r-l+1]%M1+M1)%M1,
(h2[r]-h2[l-1]*pw2[r-l+1]%M2+M2)%M2
};
}
} hs, ht;
int n, m, K, f[1005][2010], g[1005][2010];
char s[N], t[N];
int calc(int i, int j){
int l=0, r=min(n-i, n-j)+1;
while(r-l>1){
int mid=(l+r)/2;
(hs.que(i+1, i+mid)==ht.que(j+1, j+mid)) ? l=mid : r=mid;
}
return l;
}
void upd(int i, int j, int s, int typ){
if(f[i][j]<s){
f[i][j]=s;
g[i][j]=typ;
}
}
void solve(){
n=rd(), m=rd(), K=rd();
scanf("%s%s", s+1, t+1);
if(abs(n-m)>K){
puts("NO");
return;
}
while(n && m && s[n]==t[m]) n--, m--;
if(!n && !m){
printf("YES\n0\n");
return;
}
hs.init(s, n);
ht.init(t, m);
mset(f, ~63);
f[0][Mov]=0;
for(int i=0; i<K; i++){
for(int j=-K; j<=K; j++) if(f[i][j+Mov]>=0){
int s=f[i][j+Mov];
int d=calc(s, s+j);
if(s+d<n) upd(i+1, j-1+Mov, s+d+1, 0);//删除 s(s+d+1)
if(s+j+d<m) upd(i+1, j+1+Mov, s+d, 1);//在 s(s+d) 后添加字符
if(s+d<n && s+j+d<m) upd(i+1, j+Mov, s+d+1, 2);//修改 s(s+d+1)
}
}
map<pii, pii> mp;
for(int i=1; i<=K; i++){
for(int j=-K; j<=K; j++) if(f[i][j+Mov]>=0){
int s=f[i][j+Mov];
if(!mp.count({s, s+j})) mp[{s, s+j}]={i, j+Mov};
}
}
if(!mp.count({n, m})){
puts("NO");
return;
}
printf("YES\n%d\n", mp[{n, m}].fr);
while(x || y){
auto[i, j]=mp[{x, y}];
if(g[i][j]==0){
printf("DELETE %d\n", x);
x--;
}
else if(g[i][j]==1){
printf("INSERT %d %c\n", x+1, t[y]);
y--;
}
else{
printf("REPLACE %d %c\n", x, t[y]);
x--; y--;
}
while(x && y && s[x]==t[y]) x--, y--;
}
}
char _end;
signed main(){
debug("%lfMB\n", (&_end-&_begin)/1024./1024.);
pw1[0]=1; for(int i=1; i<=1e6; i++) pw1[i]=pw1[i-1]*P%M1;
pw2[0]=1; for(int i=1; i<=1e6; i++) pw2[i]=pw2[i-1]*P%M2;
int T=rd();
while(T--) solve();
return 0;
}
/*
1
3 3 100
bbb
abc
*/
详细
answer.code: In function ‘void solve()’: answer.code:103:15: error: ‘x’ was not declared in this scope 103 | while(x || y){ | ^ answer.code:103:20: error: ‘y’ was not declared in this scope; did you mean ‘yn’? 103 | while(x || y){ | ^ | yn answer.code:104:21: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions] 104 | auto[i, j]=mp[{x, y}]; | ^ answer.code:104:30: error: no match for ‘operator[]’ (operand types are ‘std::map<std::pair<int, int>, std::pair<int, int> >’ and ‘<brace-enclosed initializer list>’) 104 | auto[i, j]=mp[{x, y}]; | ^ In file included from /usr/include/c++/13/map:63, from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:152, from answer.code:1: /usr/include/c++/13/bits/stl_map.h:504:7: note: candidate: ‘std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type& std::map<_Key, _Tp, _Compare, _Alloc>::operator[](const key_type&) [with _Key = std::pair<int, int>; _Tp = std::pair<int, int>; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<const std::pair<int, int>, std::pair<int, int> > >; mapped_type = std::pair<int, int>; key_type = std::pair<int, int>]’ 504 | operator[](const key_type& __k) | ^~~~~~~~ /usr/include/c++/13/bits/stl_map.h:504:34: note: no known conversion for argument 1 from ‘<brace-enclosed initializer list>’ to ‘const std::map<std::pair<int, int>, std::pair<int, int> >::key_type&’ {aka ‘const std::pair<int, int>&’} 504 | operator[](const key_type& __k) | ~~~~~~~~~~~~~~~~^~~ /usr/include/c++/13/bits/stl_map.h:524:7: note: candidate: ‘std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type& std::map<_Key, _Tp, _Compare, _Alloc>::operator[](key_type&&) [with _Key = std::pair<int, int>; _Tp = std::pair<int, int>; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<const std::pair<int, int>, std::pair<int, int> > >; mapped_type = std::pair<int, int>; key_type = std::pair<int, int>]’ 524 | operator[](key_type&& __k) | ^~~~~~~~ /usr/include/c++/13/bits/stl_map.h:524:29: note: no known conversion for argument 1 from ‘<brace-enclosed initializer list>’ to ‘std::map<std::pair<int, int>, std::pair<int, int> >::key_type&&’ {aka ‘std::pair<int, int>&&’} 524 | operator[](key_type&& __k) | ~~~~~~~~~~~^~~ answer.code:67:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 67 | scanf("%s%s", s+1, t+1); | ~~~~~^~~~~~~~~~~~~~~~~~