[CF 965E]Short Code

danihao123 posted @ 2018年9月17日 21:04 in 题解 with tags codeforces Trie 可并堆 , 29 阅读
转载请注明出处:http://danihao123.is-programmer.com/

你有\(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;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter