[F] Teacher's Problem(处理大数时,优化很重要)
1、http://acm.nbut.edu.cn/Problem/view.xhtml?id=1546 2、题目大意: 有n个字符串,每个字符串都有一个价值,如果第i个字符串是第j个字符串的前缀,那么第i个字符串就是第j个字符串的父亲,这样就会组成一棵树,子节点的价值都更新到父节点的价值上,然后按顺序输出即可 3、题目: [F] Teacher's ProblemOne day my teacher gave me a problem to solve. I was given N unique names andeach name has a value. Name is a string consisting of lowercase Latin letters withlength less than 10. Value is a positive integer less than 100. Initially these namesare sorted in lexicographic order. Now if the j-th name is the prefix of the i-th nameand has the max length,j is thefather of i. Then numbers 1 to N form a tree. Fromleafto root,each son's value should be added to father's value. After I added thesevalues,my teacher ask me to show allthese values. Can you help me with the problem?
First line there is an integer T (T < 20) following T test cases.
For each test case,first line is an integer N (0 < N <= 10^5),second line is N names,third line is N values. Names and values are separate by a space. There is no space at the end of line. Names are all unique and are given in Lexicographic order.???????????
For each test case,please output one line with N integers. The i-th integer is the i-th value after added.
Please do not output a space at the end of line.??????????? 2 3 a ab ac 5 10 15 5 a ab abb ac b 5 10 100 15 6 30 10 15 130 110 100 15 6 Huge input,scanf is recommended. zzxchavo @HEU 4、Ac代码: #include<stdio.h> #include<string.h> #include<algorithm> using namespace std; #define N 100005 char s[N][12]; int w[N]; int check(int a,int b) { int len=strlen(s[a]); for(int i=0;i<len;i++) { if(s[a][i]!=s[b][i]) return 0; } return 1; } int main() { int t,n; scanf("%d",&t); while(t--) { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%s",s[i]); } for(int i=1;i<=n;i++) scanf("%d",&w[i]); for(int i=1;i<n;i++) { int sum=0; sum+=w[i]; for(int j=i+1;j<=n;j++) { if(check(i,j)) sum+=w[j]; else break; } printf("%d ",sum); } printf("%dn",w[n]); } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |