社区讨论

何意味?根号分治 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 条回复,欢迎继续交流。

正在加载回复...