首页 > 代码库 > SDUT2826:名字的价值

SDUT2826:名字的价值

2024-07-20 01:28:03   212人阅读

http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2806

名字的价值

 

Time Limit: 1000ms   Memory limit: 65536K  有疑问？点这里^_^

题目描述

每 个人都有名字，名字都是唯一的不存在重复现象。现在假设名字都是由小写字母组成并且长度不超过10，我们赋予每个名字一个初始价值。价值是正整数并且不超 过100，如果第j个人的名字是第i个人的前缀并且前缀长度最大，我们就说j是i的父节点，比如：名字A为：a;名字B为ab;名字C为abc; A是C 的前缀，B也是C的前缀，但是B的长度为2比A的长度大，那么B就是C的父节点. 由此规则建树，从叶子节点到根，父节点的价值=父节点本身的价值+孩子 节点的价值。 求最后各个名字的价值

输入

 一个整数T，代表数据组数
对于每一组数据输入第一行为一个整数N(0<N<=10^5)代表N个名字，第二行为N个名字，第三行为N个名字的价值
名字都是唯一的

输出

 输出N个对应的名字的价值,按照输入的顺序输出(操作完成后最终价值)

示例输入

13a ab abc10 20 30

示例输出

60 50 30

提示

 大数据输入，建议用scanf
题解：就是水水的字典树，没什么好讲的。
#include <iostream>#include <stdio.h>#include <string.h>#include <stdlib.h>using namespace std;int w[100001];char a[100001][11];typedef struct Node{    struct Node *next[26];    int flag;} Node,*Tree;void creat(Tree &T){    T=(Node *)malloc(sizeof(Node));    T->flag=0;    for(int i=0; i<26; i++)        T->next[i]=NULL;}void inseart(Tree &T,char *s,int key){    int l=strlen(s);    int t;    Tree p=T;    for(int i=0; i<l; i++)    {        t=s[i]-‘a‘;        if(p->next[t]==NULL)            creat(p->next[t]);        p=p->next[t];        p->flag+=key;    }}int search(Tree T,char *s){    int t;    Tree p=T;    int l=strlen(s);    for(int i=0; i<l; i++)    {        t=s[i]-‘a‘;        p=p->next[t];    }    return p->flag;}void D(Tree p){    for(int i=0; i<26; i++)    {        if(p->next[i]!=NULL)            D(p->next[i]);    }    free(p);}int main(){    int K,n,tt;    scanf("%d",&K);    while(K--)    {        Tree T;        scanf("%d",&n);        creat(T);        for(int i=0; i<n; i++)        {            scanf("%s",a[i]);        }        for(int i=0; i<n; i++)        {            scanf("%d",&w[i]);        }        for(int i=0; i<n; i++)        {            inseart(T,a[i],w[i]);        }        for(int i=0; i<n; i++)        {            tt=search(T,a[i]);            if(i==0)                printf("%d",tt);            else printf(" %d",tt);        }        printf("\n");        D(T);    }    return 0;}

 

SDUT2826:名字的价值


联系
我们