社区讨论
何意味?根号分治 B = 0 过了???
P14719[RMI 2025] Cheap AI参与者 5已保存回复 6
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 5 条
- 当前快照
- 1 份
- 快照标识符
- @mkrp8hxb
- 此快照首次捕获于
- 2026/01/24 10:37 4 周前
- 此快照最后确认于
- 2026/01/24 18:12 4 周前
CPP
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5, B = 0;
string s;
pair<int, int> t[MAXN];
int n, k, sa[MAXN], rnk[MAXN], height[MAXN], f[MAXN], dp[MAXN], mx[MAXN], a[MAXN];
int Check(int len) {
if (f[len] > 0) return f[len];
int m = 0;
for (int i = 0; i < n; i++) {
for (; i < n - 1 && height[i] >= len; i++) {
a[sa[i]] = m;
}
a[sa[i]] = m++;
}
//cout << a[0] << ' ' << a[n - len] << '\n';
for (int i = n - len; i >= 0; i--) {
mx[a[i + len]] = dp[i + len];
dp[i] = mx[a[i]] + 1, f[len] = max(f[len], dp[i]);
//cout << dp[i] << ' ' << a[i] << " | ";
}
fill(mx, mx + m, 0);
return f[len];
}
int solve(int k, string s) {
n = s.size();
//cout << n << ' ';
for (int i = 0; i < n; i++) {
sa[i] = i, rnk[i] = s[i] - 'a' + 1;
}
for (int o = 1; ; o <<= 1) {
for (int i = 0; i < n; i++) {
t[i] = {rnk[i], (i + o < n ? rnk[i + o] : -1)};
}
sort(sa, sa + n, [](int u, int v) {
return t[u] < t[v];
});
rnk[sa[0]] = 0;
for (int i = 1; i < n; i++) {
rnk[sa[i]] = rnk[sa[i - 1]] + (t[sa[i]] > t[sa[i - 1]]);
}
if (rnk[sa[n - 1]] == n - 1) break;
}
for (int i = 0; i < n; i++) {
if (rnk[i] == n - 1) continue;
int u = sa[rnk[i] + 1];
int &k = height[rnk[i]] = max(0, height[rnk[i - 1]] - 1);
for (; i + k < n && u + k < n && s[i + k] == s[u + k]; k++);
}
for (int i = 1; i <= n; i++) {
f[i] = (i * 2 > n);
}
int ans = 0;
for (int i = 2; i <= min(B, k); i++) { // 长度 <= B
ans = max(ans, Check(i) * (i - 1));
}
// 长度 > B -> 出现次数 < n / B
if (B + 1 <= k)
for (int i = 1; i * (B + 1) <= n; i++) {
int l = B + 1, r = k;
while (l < r) {
int mid = (l + r + 1) >> 1;
Check(mid) >= i ? l = mid : r = mid - 1;
}
ans = max(ans, (l - 1) * i);
}
return n - ans;
}
回复
共 6 条回复,欢迎继续交流。
正在加载回复...