UVA - 11732 （左孩子右兄弟Tire）

你的名字 2022-05-19 00:11 139阅读 0赞

#include<bits/stdc++.h>
    using namespace std;
    const int N=5005;
    const int INF=0x3f3f3f3f;
    typedef long long ll;
    int n, root, L;
    ll ans=0;
    char s[1005];
    struct node{
        char ch;
        int l, r;
        ll cnt;
    }trie[4005*1005];
    
    int newnode(char ch){
        trie[L].ch=ch;
        trie[L].l=trie[L].r=-1;
        trie[L].cnt=1;
    
        return L++;
    }
    
    void init(){
        ans=0;
        L=0;
        root=newnode('&');
    }
    
    void Insert(char buf[]){
        int now=root;
        int len=strlen(buf);
    
        for(int i=0; i<=len; i++){
            bool found=false;
            int las;
    
            for(int to=trie[now].l; to!=-1; to=trie[to].r){
                if(trie[to].ch==buf[i]){
                    found=true;
                    ans+=2*trie[to].cnt++;
                    now=to;
                }
                else{
                    ans+=trie[to].cnt;
                }
                las=to;
            }
    
            if(!found){
                int tmp=newnode(buf[i]);
    
                if(trie[now].l==-1)
                    trie[now].l=tmp;
                else{
                    trie[las].r=tmp;
                }
                now=tmp;
            }
        }
    }
    
    int main()
    {
        int cas=0;
        while(~scanf("%d", &n) && n){
            init();
            for(int i=1; i<=n; i++){
                scanf("%s", s);
                Insert(s);
            }
    
            printf("Case %d: %lld\n", ++cas, ans);
    
        }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，139人围观）

还没有评论，来说两句吧...

相关阅读

相关 C++左值、右值、左值引用、右值引用

左值(lvalue)和右值(rvalue) 左值（lvalue）：locator value，存储在内存中、有明确的的地址（可寻址）的数据能够取地址，有名字的值就是左

一时失言乱红尘/ 2023年01月13日 06:23/ 0 赞/ 197 阅读

相关数据结构——树——孩子兄弟表示法

数据结构——树——孩子兄弟表示法任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此，我们设置两个指针，分别指向该结点的第一个孩子和此

怼烎@/ 2023年01月08日 12:25/ 0 赞/ 150 阅读

相关 left-child right-sibling representation - 左孩子右兄弟表示

left-child right-sibling representation - 左孩子右兄弟表示 Left-Child Right-Sibling Represent

Bertha 。/ 2023年01月04日 14:42/ 0 赞/ 83 阅读

相关 left-child right-sibling representation of tree - 左孩子右兄弟表示树

left-child right-sibling representation of tree - 左孩子右兄弟表示树 child-sibling representat

小咪咪/ 2023年01月03日 11:30/ 0 赞/ 116 阅读

相关 Tiree Tree

字典树的结构是多叉树，每个节点有n个出度，每个出度表示一个字符。字典树的节点分为普通节点和终止节点，如图，红色的节点即为终止节点，往字典树中插入一个单词，这个单词的最后一个字符

ゞ浴缸里的玫瑰/ 2022年10月22日 04:06/ 0 赞/ 88 阅读

相关树左孩子于右孩子交换

8 8 / \ 转换 / \ 6 10

心已赠人/ 2022年09月21日 12:00/ 0 赞/ 140 阅读

相关 UVA - 11732 （左孩子右兄弟Tire）

include<bits/stdc++.h> using namespace std; const int N=5005; const int

你的名字/ 2022年05月19日 00:11/ 0 赞/ 140 阅读

相关 JavaScript专题实例学习二左到右右到左！

<html> <head> <meta http-equiv="content-type" content="text/html; charset=UT

爱被打了一巴掌/ 2022年05月09日 22:04/ 0 赞/ 187 阅读

相关左值、左值引用、右值、右值引用

关于左值右值示例可看[这里][Link 1] 1、左值和右值的概念左值是可以放在赋值号左边可以被赋值的值；左值必须要在内存中有实体；

布满荆棘的人生/ 2022年04月13日 14:56/ 0 赞/ 259 阅读

相关 UVA 11732 strcmp() Anyone? strcmp()函数（Trie）

题意：就是给你n个单词，让他们两两比较，要求他们运用strcmp时，进行比较的次数。分析：Trie树的一道水题，计个数就行了。代码（LRJ）： i

谁借莪１个温暖的怀抱￠/ 2021年12月11日 14:17/ 0 赞/ 214 阅读