点击打开UVa题目链接

题意

给你N个字符串,每两个字符串之间要用strcmp函数进行比较,共需要调用(N-1)*N/2次,问你所有比较完成后共比较了多少次

分析

用传统的Trie树由于节点太多,浪费空间容易造成TLE,所以用左儿子右兄弟表示法。就是每个节点下面都有一个儿子,并且维护一个父节点相同的兄弟“链表”。在插入的同时进行统计,遇到与自己当前字符不同时进行统计,最后还要加上跟自己完全相同的字符串的情况。

C++代码

#include <bits/stdc++.h>
using namespace std;

long long ans = 0;
struct Node {
    int son, bro, cnt;
    char cur;
    Node(int son = 0, int bro = 0, int cnt = 0, char cur = 0):
            son(son), bro(bro), cnt(cnt), cur(cur) {}
};
struct Trie {
    Node node[4000100]; int sz;
    Trie() { clear(); }
    void clear() { sz = 1; node[0] = Node(); ans = 0; }
    void insert(const char *s) {
        int u = 0, v;
        for(int i = 0; ; ++i) {
            for(v = node[u].son; v; v = node[v].bro) {
                if(node[v].cur == s[i])
                    break;
            }
            if(v == 0) {
                node[sz] = Node(0, node[u].son, 0, s[i]);
                v = node[u].son = sz++;
            }
            ans += (node[u].cnt - node[v].cnt) * (2 * i + 1);
            if(!s[i]) {
                ans += node[v].cnt * (2 * i + 2);
                ++node[v].cnt;
            }
            ++node[u].cnt;
            u = v;
            if(!s[i]) break;
        }
    }
}trie;

int main() {
    int n, kase = 0;
    char buf[1024];
    while(~scanf("%d", &n), n) {
        trie.clear();
        for(int i = 0; i < n; ++i) {
            scanf("%s", buf);
            trie.insert(buf);
        }
        printf("Case %d: %lld\n", ++kase, ans);
    }
    return 0;
}

欢迎留言