Uva 11732

Uva 11732

需要左儿子右兄弟优化按照他的模板打一遍基本就会了

但本题的关键在于计算

对于线段树的每个节点（不是标记的节点，是所有节点），我们增加一个变量cnt，表示这个点需要比较多少次。如果你学会了左儿子右兄弟的表示方法，那么应该知道对于要插入的串str的i号位置，需要遍历他的兄弟链表判断他是否存在，如果存在，那么ans应该加上当前节点的cnt*2，如果不存在，ans应该加上当前节点的cnt，对于大多数博客说的特殊判断‘\0’，其实我们只要在遍历str时从1遍历到n即可（即把他的'\0'也考虑在内），这样就可以不用特判完美解决问题了

看到这里你可能还是云里雾里的，推荐自己手动演算，别被博客误导了思路，一般把样例的以及than、that / the、 the的过程模拟出来就差不多明白了，代码只是个参考

最后还有一个很严重的问题：要用lld，不能用I64d！！！

#include #include using namespace std;typedef long long ll;const int maxn = 5 * 1e6 + 10;int flag, n, total;ll ans;struct Trie { char c; int cnt, L, R;}trie[maxn];void init() { total = ans = trie[0]-t = trie[0].L = trie[0].R = 0;}void update(char *str) { int len = strlen(str), i, j, k, root = 0; for (i = 0; i <= len; i++) { k = 0; for (j = trie[root].L; j; j = trie[j].R) { if (trie[j].c == str[i]) { ans += (ll)trie[j]-t * 2; k = j; } else { ans += (ll)trie[j]-t; } } if (!k) { k = ++total; trie[k].c = str[i]; trie[k]-t = trie[k].L = 0; trie[k].R = trie[root].L; trie[root].L = k; } trie[k]-t++; root = k; }}int main() { char str[5000]; while (~scanf("%d", &n) && n) { init(); for (int i = 0; i < n; i++) { scanf("%s", str); update(str); } printf("Case %d: %lld\n", ++flag, ans); }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。