首页 > 代码库 > SDUT2826:名字的价值
SDUT2826:名字的价值
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(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:名字的价值
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。