模拟赛出到加强版了,一点不会所以记录下。
枚举每个后缀。设 \(f_{i,j}\) 为操作 \(i\) 次,长度增加 \(j\),即插入的次数减删除的次数,所能匹配到的最大位置。也就是 \(A\) 的前 \(f_{i,j}\) 位匹配 \(B\) 的前 \(f_{i,j}+j\) 位。
考虑转移。假如已经操作完了,那显然有 \(f_{i,j} \gets f_{i,j}+\text{LCP}(A[f_{i,j}+1:|A|],B[f_{i,j}+j+1:|B|])\)。
进行操作的转移:
- 替换:\(f_{i+1,j} \gets f_{i,j}+1\)
- 删除:\(f_{i+1,j-1} \gets f_{i,j}+1\)
- 添加:\(f_{i+1,j+1}\gets f_{i,j}\)
一些解释:添加操作的时候,\(A\) 多了一个虚拟的点,但最后一个匹配到的真正存在的点还是 \(f_{i,j}\)。删除操作的时候,那个被删的点也看做完成了匹配。
转移时注意多判边界。
LCP 可以直接用二分哈希,其实 SA 可以更快,但二分哈希完全够用。
最后统计答案记得找到最小操作次数后要跳出循环。
复杂度 \(O(nk^2\log n)\)。如果用 SA 的话是 \(O(nk^2)\)。
#include <bits/stdc++.h>
using namespace std;
using ubt = unsigned long long;
const int maxN = 1e5 + 7;
int k;
int n, m;
string s, t;
const ubt Base = 13331;
ubt H[maxN], S[maxN], T[maxN];
void inithash() {
H[0] = 1, S[0] = T[0] = 0;
for (int i = 1; i <= n || i <= m; i++) {
if (i <= n) S[i] = S[i - 1] * Base + s[i];
if (i <= m) T[i] = T[i - 1] * Base + t[i];
H[i] = H[i - 1] * Base;
}
}
ubt gets(int l, int r) {
return S[r] - S[l - 1] * H[r - l + 1];
}
ubt gett(int l, int r) {
return T[r] - T[l - 1] * H[r - l + 1];
}
int LCP(int ss, int st) {
int l = 1, r = min(n - ss + 1, m - st + 1);
int pos = 0;
while (l <= r) {
int mid = (l + r) >> 1;
if (gets(ss, ss + mid - 1) == gett(st, st + mid - 1))
l = mid + 1, pos = mid;
else r = mid - 1;
}
return pos;
}
const int inf = 1e9;
int ans[7];
int st;
int f[7][17];
void Main() {
memset(f, ~0x3f, sizeof(f));
f[0][k] = 0;
for (int i = 0; i <= k; i++)
for (int j = 0; j <= k * 2; j++) {
if (f[i][j] <= -inf) continue;
int p = j - k;
if (f[i][j] + p < 0) continue;
if (st - 1 + f[i][j] + p > m) continue;
f[i][j] += LCP(f[i][j] + 1, st - 1 + f[i][j] + p + 1);
if (i != k) {
if (j)
f[i + 1][j - 1] = max(f[i + 1][j - 1], min(f[i][j] + 1, n));
if (f[i][j] != n)
f[i + 1][j] = max(f[i + 1][j], min(f[i][j] + 1, n));
if (j != k * 2)
f[i + 1][j + 1] = max(f[i + 1][j + 1], f[i][j]);
}
}
for (int i = 0; i <= k * 2; i++)
for (int j = 0; j <= k; j++)
if (f[j][i] == n)
{ ans[j]++; break; }
}
int main() {
//ifstream cin("in.in");
//ofstream cout("out.out");
cin >> k >> s >> t;
n = s.length(), m = t.length();
s = '@' + s, t = '$' + t;
inithash();
for (st = 1; st <= m; st++)
Main();
int res = 0;
for (int i = 0; i <= k; i++)
res += ans[i];
cout << res << '\n';
}
标签:const,int,BJOI2015,mid,st,473,maxN,gets,隐身术
From: https://www.cnblogs.com/ccxswl/p/18534359