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

你的名字 2022-05-19 00:11 151阅读 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 条评论，151人围观）

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

相关阅读

相关左孩子右兄弟(Java详解)

目录一、题目描述二、题解 -------------------- 一、题目描述对于一棵多叉树，我们可以通过“左孩子右兄弟” 表示法，将其转化成一棵二叉树。

灰太狼/ 2024年02月17日 09:33/ 0 赞/ 48 阅读

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

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

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

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

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

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

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

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

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

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

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

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

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

8 8 / \ 转换 / \ 6 10

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

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

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

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

相关 UVA - 12108 Extraordinarily Tired Students

include <bits/stdc++.h> using namespace std; define N 100010 int ma

清疚/ 2022年05月07日 21:18/ 0 赞/ 73 阅读

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

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

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

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

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

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