你有\(n\)个两两不同的串，你要将每个串变成其的一个前缀，使得变换后的所有串仍然两两不同，并且所有串长度和尽可能小，输出这个和。

\(n\leq 10^5\)，所有串长之和不超过\(10^5\)。

kksk（错乱）

我们考虑建出来字典树然后贪心……我们希望一个串转化成其祖先中尽可能短的一个，然后还要两两不同。我们考虑DFS这棵字典树，然后每次将子树里一个点提到当前点（之后还可以接着往上提）。这样的话就需要一个支持快速合并，查询极值的东西……这就是可并堆的任务了（我手写了一个配对堆……）

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <functional>
#include <utility>
const int maxno = 100005;
struct Node {
  Node *lc, *rb;
  int v;
  Node(int val = 0) {
    v = val;
    lc = NULL; rb = NULL;
  }
  void sc(Node *c) {
    c -> rb = lc;
    lc = c;
  }
};
Node *merge(Node *x, Node *y) {
  if(x == NULL) return y;
  if(y == NULL) return x;
  if(x -> v > y -> v) {
    x -> sc(y);
    return x;
  } else {
    y -> sc(x);
    return y;
  }
}
int top(Node *x) {
  return (x -> v);
}
Node *link(Node *x) {
  if(x == NULL) return NULL;
  Node *y = x -> rb;
  x -> rb = NULL;
  if(y == NULL) return x;
  Node *z = y -> rb;
  y -> rb = NULL;
  if(z == NULL) return merge(x, y);
  else return merge(merge(x, y), link(z));
}
Node *pop(Node *x) {
  if(x == NULL) return x;
  Node *p = x -> lc;
  x -> lc = NULL;
  return link(p);
}

int idx(char c) {
  return c - 'a';
}
int ch[maxno][26], dep[maxno];
bool val[maxno];
int cnt = 0;
inline int trace(int p, int t) {
  if(ch[p][t]) return ch[p][t];
  int np = ++ cnt;
  dep[np] = dep[p] + 1;
  return (ch[p][t] = np);
}
inline void insert(char *S) {
  int n = strlen(S); int u = 0;
  for(int i = 0; i < n; i ++) {
    u = trace(u, idx(S[i]));
#ifdef LOCAL
    printf("Node %d : (%d, %d)\n", u, i + 1, dep[u]);
#endif
  }
  val[u] = true;
}

Node *solve(int x) {
  Node *ret = NULL;
  for(int i = 0; i < 26; i ++) {
    if(ch[x][i]) {
      ret = merge(ret, solve(ch[x][i]));
    }
  }
  if(!val[x] && x != 0) {
#ifdef LOCAL
    printf("Remove %d\n", top(ret));
#endif
    ret = pop(ret);
  }
  if(x != 0) ret = merge(ret, new Node(dep[x]));
#ifdef LOCAL
    printf("Insert %d\n", dep[x]);
#endif
  return ret;
}

typedef long long ll;
int main() {
  int n; scanf("%d", &n);
  for(int i = 0; i < n; i ++) {
    static char buf[maxno]; scanf("%s", buf);
    insert(buf);
  }
  Node *tr = solve(0);
  ll ans = 0;
  while(tr != NULL) {
    ans += top(tr);
    tr = pop(tr);
  }
  printf("%I64d", ans);
  return 0;
}

• 相关文章
• 全局相关文章