[CF 965E]Short Code

danihao123 posted @ 2018年9月17日 21:04 in 题解 with tags codeforces Trie 可并堆 , 1059 阅读
转载请注明出处: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;
}
AP 2nd Inter Botany 说:
Sep 08, 2022 08:38:22 PM

In intermediate education, Botany is a very important subject for science group students for part-1 and part-2 first and the second year of junior and senior intermediate students, and the BIEAP has conducted the General Science examination tests including botany subject, download AP inter Botany Model Paper 2023 AP 2nd Inter Botany Question Paper Pdf with solutions for all 1st and 2nd-year students for paper-1 and paper-2 exams 2023.


登录 *


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