UVA11732 "strcmp()" Anyone?【左儿子右兄弟Trie】

LINK1

LINK2

---

题目大意

给你一些字符串，并定义了一个函数（具体见题面）

问你把任意两个字符串放到函数里面得到的值的和是多少

思路

该怎么统计答案呢？

每次考虑当前插入的串和所有已经插入过的串一起统计答案

然后考虑一下怎么统计，假设当前深度是dep

并且现在是u，即将向v移动指针

那么怎么同几当前这一层的答案呢？

所有在v的子树中的节点显然是不能在这一层统计答案的

所以就考虑统计和所有不在同一个子树的答案

具体实现很简单，读者自己思考吧

---

注意在每一次走到字符串的末尾的时候需要特判

和他相同或者包含它的字符串会比较更多的次数，所以不能直接停止也要继续移动指针，可以强行让最后一个位置变成奇怪字符

然后这题需要左兄弟右儿子的trie

具体实现参考代码（其实并不麻烦，别怕）

---

//Author: dream_maker

#include<bits/stdc++.h>

using namespace std;

//----------------------------------------------

typedef pair<int, int> pi;

typedef long long ll;

typedef double db;

#define fi first

#define se second

#define fu(a, b, c) for (int a = b; a <= c; ++a)

#define fd(a, b, c) for (int a = b; a >= c; --a)

#define fv(a, b) for (int a = 0; a < (signed)b.size(); ++a)

const int INF_of_int = 1e9;

const ll INF_of_ll = 1e18;

template <typename T>

void Read(T &x) {

  bool w = 1;x = 0;

  char c = getchar();

  while (!isdigit(c) && c != '-') c = getchar();

  if (c == '-') w = 0, c = getchar();

  while (isdigit(c)) {

    x = (x<<1) + (x<<3) + c -'0';

    c = getchar();

  }

  if (!w) x = -x;

}

template <typename T>

void Write(T x) {

  if (x < 0) {

    putchar('-');

    x = -x;

  }

  if (x > 9) Write(x / 10);

  putchar(x % 10 + '0');

}

//----------------------------------------------

const int N = 6e6 + 10;

struct Node {

  char ch;

  int val;

  Node *son, *bro;

  Node(char ch = 0, int val = 0, Node *son = NULL, Node *bro = NULL):ch(ch), val(val), son(son), bro(bro) {}

} *rt, pool[N], *cur = pool;

ll ans;

void insert(char *s) {

  int len = strlen(s);

  s[len] = '#';

  Node *u = rt, *v;

  fu(i, 0, len) {

    v = u->son;

    for (; v; v = v->bro)

      if (v->ch == s[i]) break;

    if (!v) {

      v = new (cur++) Node(s[i], 0, NULL, u->son);

      u->son = v;

    }

    ans += 1ll * (u->val - v->val) * (2 * i + 1);

    if (i == len) {

      ans += 1ll * v->val * (2 * len + 2);

      ++v->val;

    }

    ++u->val;

    u = v;

  }

}

char s[N];

int main() {

#ifdef dream_maker

  freopen("input.txt", "r", stdin);

#endif

  int n, tot = 0;

  while (1) {

    Read(n);

    if (!n) break;

    cur = pool;

    rt = new (cur++) Node();

    ans = 0;

    fu(i, 1, n) {

      scanf("%s", s);

      insert(s);

    }

    printf("Case %d: %lld\n", ++tot, ans);

  }

  return 0;

}