QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #367674 | #850. Edit Distance Yet Again | Slongod | AC ✓ | 2901ms | 44984kb | C++14 | 4.4kb | 2024-03-26 11:41:27 | 2024-03-26 11:41:27 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
namespace Slongod{
const int N = 1e6+7 , M = 1005 , mod1 = 998244353 , mod2 = 1e9+7 , inf = 0x3f3f3f3f;
namespace hash
{
int seed1 , seed2 , pw1[N] , pw2[N]; mt19937 rd(time(nullptr));
inline void inithash()
{
seed1 = uniform_int_distribution<>(1,100)(rd);
seed2 = uniform_int_distribution<>(1,100)(rd);
pw1[0] = 1; for (int i = 1; i < N; i++){pw1[i] = 1ll * pw1[i-1] * seed1 % mod1;}
pw2[0] = 1; for (int i = 1; i < N; i++){pw2[i] = 1ll * pw2[i-1] * seed2 % mod2;}
}
inline void makehash(const int n , const char s[] , pair<int,int> hash[])
{
hash[0] = {0 , 0};
for (int i = 1; i <= n; i++) {
hash[i].first = (1ll * hash[i-1].first * seed1 + s[i]) % mod1;
hash[i].second = (1ll * hash[i-1].second * seed2 + s[i]) % mod2;
}
}
inline pair<int,int> gethash(int l , int r , pair<int,int> hash[])
{
int res1 = (hash[r].first - 1ll * hash[l-1].first * pw1[r - l + 1] % mod1 + mod1) % mod1;
int res2 = (hash[r].second - 1ll * hash[l-1].second * pw2[r - l + 1] % mod2 + mod2) % mod2;
return {res1 , res2};
}
}
int T , n , m , k , *rk[M] , *fa[M];
char s[N] , t[N];
pair<int,int> hs[N] , ht[N];
inline int lcp(int x , int y)
{
int l = 0 , r = min(n - x + 1 , m - y + 1) , res = 0;
while(l <= r) {
int mid = (r - l) / 2 + l;
if (hash::gethash(x , x + mid - 1 , hs) == hash::gethash(y , y + mid - 1 , ht)) {
res = mid; l = mid + 1;
} else {
r = mid - 1;
}
} return res;
}
int output(int dep , int j)
{
if (dep == 0){return 0;}
int delta = output(dep - 1 , fa[dep][j]);
int x = rk[dep][j] , y = x - j;
int tx = rk[dep-1][fa[dep][j]] , ty = tx - fa[dep][j];
if (x - tx > y - ty) {
cout << "DELETE " << tx + 1 + delta << '\n';
return delta - 1;
}
if (y - ty > x - tx) {
cout << "INSERT " << tx + 1 + delta << ' ' << t[ty + 1] << '\n';
return delta + 1;
}
cout << "REPLACE " << tx + 1 + delta << ' ' << t[ty + 1] << '\n';
return delta;
}
void main()
{
for (int i = 0; i < M; i++) {
rk[i] = new int[M*2]; rk[i] += M;
fa[i] = new int[M*2]; fa[i] += M;
} hash::inithash();
for (cin >> T; T; T--) {
//Input and Inithash/DP
cin >> n >> m >> k >> (s + 1) >> (t + 1);
hash::makehash(n , s , hs); hash::makehash(m , t , ht);
for (int i = 0; i <= k; i++) {
for (int j = -k; j <= k; j++) {
rk[i][j] = -inf; fa[i][j] = 0;
}
}
//DongPlan
rk[0][0] = lcp(1 , 1);
for (int i = 0; i <= k; i++) {
for (int j = -k , x , y , tmp; j <= k; j++) {
if (rk[i][j] != -inf) {
x = rk[i][j]; y = rk[i][j] - j;
//S 走一步
if (x < n) {
tmp = lcp(x + 2 , y + 1);
if (x + 1 + tmp > rk[i+1][j+1]) {
rk[i+1][j+1] = x + 1 + tmp;
fa[i+1][j+1] = j;
}
}
//T 走一步
if (y < m) {
tmp = lcp(x + 1 , y + 2);
if (x + tmp > rk[i+1][j-1]) {
rk[i+1][j-1] = x + tmp;
fa[i+1][j-1] = j;
}
}
//同时走一步
if (x < n and y < m) {
tmp = lcp(x + 2 , y + 2);
if (x + 1 + tmp > rk[i+1][j]) {
rk[i+1][j] = x + 1 + tmp;
fa[i+1][j] = j;
}
}
}
}
}
int ans = -1;
if (abs(n - m) <= k) {
for (int i = 0; i <= k; i++) {
if (rk[i][n-m] == n) {
ans = i; break;
}
}
}
if (ans == -1){cout << "NO\n";}
else{cout << "YES\n" << ans << '\n'; output(ans , n - m);}
}
}
}int main()
{
ios :: sync_with_stdio(0);
cin.tie(0) , cout.tie(0);
return Slongod :: main(),0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 7ms
memory: 19616kb
input:
2 3 4 3 kot plot 5 7 3 zycie porazka
output:
YES 2 INSERT 1 p REPLACE 2 l NO
result:
ok OK!
Test #2:
score: 0
Accepted
time: 23ms
memory: 20372kb
input:
100 100 100 0 mmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm mmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm 16 7 100 vvvvvvvvvvvvvvvv qydopaq 37 33 43 ggggggggggggggggggggggggggggggggggggg osk...
output:
YES 0 YES 16 REPLACE 1 q REPLACE 2 y REPLACE 3 d REPLACE 4 o REPLACE 5 p REPLACE 6 a REPLACE 7 q DELETE 8 DELETE 8 DELETE 8 DELETE 8 DELETE 8 DELETE 8 DELETE 8 DELETE 8 DELETE 8 YES 28 REPLACE 1 o REPLACE 2 s REPLACE 3 k REPLACE 5 m REPLACE 6 l REPLACE 8 j REPLACE 9 t REPLACE 10 u REPLACE 11 a REPLA...
result:
ok OK!
Test #3:
score: 0
Accepted
time: 2901ms
memory: 27444kb
input:
100 3211 3185 685 wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww...
output:
YES 552 REPLACE 4 i REPLACE 16 b REPLACE 17 s REPLACE 20 u REPLACE 29 j REPLACE 31 b REPLACE 33 z REPLACE 39 l REPLACE 67 l REPLACE 68 s REPLACE 70 i REPLACE 73 p REPLACE 91 g REPLACE 101 x REPLACE 111 y REPLACE 113 x REPLACE 115 s REPLACE 117 f REPLACE 121 m REPLACE 123 a REPLACE 130 h REPLACE 132 ...
result:
ok OK!
Test #4:
score: 0
Accepted
time: 2469ms
memory: 44928kb
input:
5 999000 998976 995 llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll...
output:
YES 894 REPLACE 1682 u REPLACE 2752 y REPLACE 2983 z REPLACE 4433 b REPLACE 7318 m REPLACE 8237 b REPLACE 8898 n REPLACE 9049 m REPLACE 9504 n REPLACE 9903 n REPLACE 13572 q REPLACE 14221 v REPLACE 14615 y REPLACE 16903 j REPLACE 17197 e REPLACE 18073 v REPLACE 19408 b REPLACE 20512 p REPLACE 21033 ...
result:
ok OK!
Test #5:
score: 0
Accepted
time: 2703ms
memory: 44812kb
input:
5 999000 998971 1000 lllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll...
output:
NO NO NO NO NO
result:
ok OK!
Test #6:
score: 0
Accepted
time: 1154ms
memory: 44984kb
input:
5 1000000 1000000 1000 faafaffaaffafaafaffafaaffaafaffaaffafaaffaafaffafaafaffaaffafaafaffafaaffaafaffafaafaffaaffafaaffaafaffaaffafaafaffafaaffaafaffaaffafaaffaafaffafaafaffaaffafaaffaafaffaaffafaafaffafaaffaafaffafaafaffaaffafaafaffafaaffaafaffaaffafaaffaafaffafaafaffaaffafaafaffafaaffaafaffafaafa...
output:
YES 246 INSERT 1 a REPLACE 3 f INSERT 7 a INSERT 13 a INSERT 15 f INSERT 25 a INSERT 27 f INSERT 29 f INSERT 31 a INSERT 49 a INSERT 51 f INSERT 53 f INSERT 55 a INSERT 57 f INSERT 59 a INSERT 61 a INSERT 63 f INSERT 97 a REPLACE 99 f INSERT 103 a DELETE 109 REPLACE 111 f DELETE 114 INSERT 129 f REP...
result:
ok OK!
Test #7:
score: 0
Accepted
time: 2414ms
memory: 44924kb
input:
5 999900 999925 992 ejqwvowvntrtmokrfeqeybcvgsupftozhkdsyytrioxrzbahikexefgyhpwbcztcydqiibxukojvgedldgmjufkzwttpvftctkpajgpwiklfzrkjxzsltqdbfdyxqpswrrlkdbmwckbhbfpqqgnhcixcnmphjulyykqfvdrqsdskbxqlqvekhwmvzmtqannmxrjgqcpdpofmqozyicaiqjikqxkeolandjydgvtjhnzubpdtkxymaxffnopnnrpnedobnfljcvtqwmuxdctutidm...
output:
YES 938 DELETE 1984 DELETE 2243 INSERT 4441 b DELETE 5841 DELETE 6398 INSERT 6785 b REPLACE 6948 t INSERT 6988 g REPLACE 7101 b INSERT 7373 b DELETE 10782 INSERT 12028 g REPLACE 13721 g INSERT 14908 t DELETE 14925 INSERT 15582 b REPLACE 17831 b INSERT 19811 b DELETE 22361 REPLACE 22445 t INSERT 2508...
result:
ok OK!