0316 校赛训练赛3 解题报告

时间：2014-03-19 11:59:29 阅读：562 评论：0 收藏：0 [点我收藏+]

A：

题目：

帽子

Time Limit: 1000 MS

Memory Limit: 32768 K

Total Submit: 27(6 users)

Total Accepted: 9(5 users)

Rating:

Special Judge: No

Description

由字典里其他两个单词组成的单词为帽子单词，你要找到字典里所有的帽子单词。

Input

只有一组输入数据

输入包含若干个小写单词，每行一个单词并且按照字典序排序。最多不超过50000个单词。每个单词长度不超过15.

Output

你需要按照字典序输出字典中的所有帽子单词。

Sample Input

cat
catdog
dog

Sample Output

catdog

Source

HCPC2014校赛训练赛 3

Author

曹振海

这个题可以用map水过，省时的方法还是字典树

map代码：

 1 #include<iostream>
 2 #include<string.h>
 3 #include<stdio.h>
 4 #include<map>
 5 using namespace std;
 6 
 7 map<string,int>mp;
 8 
 9 int main()
10 {
11     int k=0;
12     string str[50005];
13     //freopen("aa.txt","r",stdin);
14     while(cin>>str[k])
15     {
16         mp[str[k]]=1;
17         k++;
18     }
19     for(int i=0;i<k;i++)
20     {
21         int len=str[i].length();
22         for(int j=1;j<len;j++)
23         {
24             string s1=str[i].substr(0,j);
25             string s2=str[i].substr(j,len);
26             if(mp[s1]==1&&mp[s2]==1){
27             cout<<str[i]<<endl;
28             break;
29             }
30         }
31     }
32     return 0;
33 }

View Code

字典树数组模拟带代码：

 1 #include<iostream>
 2 #include<string.h>
 3 #include<stdio.h>
 4 using namespace std;
 5 
 6 const int maxn=1000005;
 7 
 8 int tire[maxn][26];
 9 int flag[maxn];
10 int tot;
11 
12 void Insert(char *s,int rt)
13 {
14     int len=strlen(s);
15     for(int i=0;i<len;i++)
16     {
17         int x=s[i]-‘a‘;
18         if(tire[rt][x]==0)
19         tire[rt][x]=tot++;
20         rt=tire[rt][x];
21     }
22     flag[rt]=1;
23 }
24 
25 bool Find2(char *s,int rt,int i)
26 {
27     int len=strlen(s);
28     for(int j=i;j<len;j++)
29     {
30         int x=s[j]-‘a‘;
31         if(tire[rt][x]==0)
32         return false;
33         rt=tire[rt][x];
34     }
35     return flag[rt];
36 }
37 
38 bool Find(char *s,int rt)
39 {
40 
41     int len=strlen(s);
42     for(int i=0;i<len;i++)
43     {
44         int x=s[i]-‘a‘;
45         if(tire[rt][x]==0)
46         return false;
47         if(flag[rt]&&Find2(s,0,i))
48         return true;
49         rt=tire[rt][x];
50     }
51     return false;
52 }
53 
54 int main()
55 {
56     int k=0;
57     tot=1;
58     char str[50005][20];
59     //freopen("aa.txt","r",stdin);
60     while(scanf("%s",str[k])!=EOF)
61     {
62         Insert(str[k],0);
63         k++;
64     }
65     for(int i=0;i<k;i++)
66     {
67         if(Find(str[i],0))
68         printf("%s\n",str[i]);
69     }
70     return 0;
71 }

View Code

字典树指针代码：

 1 #include<iostream>
 2 #include<string.h>
 3 #include<stdio.h>
 4 using namespace std;
 5 
 6 struct tire
 7 {
 8     tire *next[26];
 9     bool flag;
10     tire()
11     {
12         for(int i=0;i<26;i++)
13         {
14             next[i]=NULL;
15             flag=false;
16         }
17     }
18 }root;
19 
20 void Insert(char *s)
21 {
22     tire *rt=&root;
23     for(int i=0;s[i];i++)
24     {
25         int x=s[i]-‘a‘;
26         if(rt->next[x]==NULL)
27         {
28             rt->next[x]=new tire;
29         }
30         rt=rt->next[x];
31     }
32     rt->flag=true;
33 }
34 
35 bool Find2(char *s,int i)
36 {
37     tire *rt=&root;
38     for(int j=i;s[j];j++)
39     {
40         int x=s[j]-‘a‘;
41         if(rt->next[x]==NULL)
42         return false;
43 
44         rt=rt->next[x];
45     }
46     return rt->flag;
47 }
48 
49 bool Find(char *s)
50 {
51     tire *rt=&root;
52     for(int i=0;s[i];i++)
53     {
54         int x=s[i]-‘a‘;
55         if(rt->next[x]==NULL)
56         return false;
57 
58         if(rt->flag&&Find2(s,i))
59         return true;
60 
61         rt=rt->next[x];
62     }
63     return false;
64 }
65 
66 int main()
67 {
68     int k=0;
69     char str[50005][20];
70     //freopen("aa.txt","r",stdin);
71     while(scanf("%s",str[k])!=EOF)
72     {
73         Insert(str[k]);
74         k++;
75     }
76     for(int i=0;i<k;i++)
77     {
78         if(Find(str[i]))
79         printf("%s\n",str[i]);
80     }
81     return 0;
82 }

View Code

B：

背单词

Time Limit: 1000 MS

Memory Limit: 32768 K

Total Submit: 47(25 users)

Total Accepted: 29(24 users)

Rating:

Special Judge: No

Description

大四了，Leyni感觉好惆怅，因为找不到工作，所以最后决定考研了，可是Leyni的英语好差，没办法，先从最基本的背单词开始吧。那么多单词怎么才好背呢，话说考研界盛传利用前缀背单词，貌似好神奇的样子。因为英语单词很多，Leyni想要知道以一个特定字符串做前缀的单词有多少，于是他来找你帮忙了。

Input

输入首先包含若干行小写单词，表示字典里的单词，以END结束，然后是若干个询问字符串，表示单词的前缀。输入到文件结束。最多不超过50000个单词。每个单词长度不超过15。

Output

对于每一个询问字符串，每行输出一个整数，表示单词表里有多少单词以此字符串作为前缀。

Sample Input

a
ab
aba
abcaa
END
aba
a
ab
abcd

Sample Output

1
4
3
0

Source

HCPC2014校赛训练赛 3

Author

曹振海

这个题同样可以用字典树和map做：

map代码：

 1 #include<iostream>
 2 #include<string.h>
 3 #include<stdio.h>
 4 #include<map>
 5 using namespace std;
 6 
 7 map<string,int>mp;
 8 
 9 int main()
10 {
11     string s;
12     //freopen("aa.txt","r",stdin);
13     while(cin>>s)
14     {
15         if(s=="END")
16         break;
17         int len=s.length();
18         for(int i=0;i<=len;i++)
19         {
20             string s1=s.substr(0,i);
21             mp[s1]++;
22         }
23     }
24     while(cin>>s)
25     {
26         if(s=="END")
27         break;
28         cout<<mp[s]<<endl;
29     }
30     return 0;
31 }

View Code

字典树数组模拟：

 1 #include<iostream>
 2 #include<string.h>
 3 #include<stdio.h>
 4 #include<map>
 5 using namespace std;
 6 
 7 const int maxn=1000005;
 8 
 9 int tire[maxn][26];
10 int num[maxn];
11 int tot;
12 
13 void Insert(char *s,int rt)
14 {
15     int len=strlen(s);
16     for(int i=0;i<len;i++)
17     {
18         int x=s[i]-‘a‘;
19         if(tire[rt][x]==0)
20         tire[rt][x]=tot++;
21         rt=tire[rt][x];
22         num[rt]++;
23     }
24 }
25 
26 int Find(char *s,int rt)
27 {
28     int len=strlen(s);
29     for(int j=0;j<len;j++)
30     {
31         int x=s[j]-‘a‘;
32         if(tire[rt][x]==0)
33         return 0;
34         rt=tire[rt][x];
35     }
36     return num[rt];
37 }
38 
39 int main()
40 {
41     char s[maxn];
42     tot=1;
43     //freopen("aa.txt","r",stdin);
44     while(scanf("%s",s))
45     {
46         if(strcmp(s,"END")==0)
47         break;
48         Insert(s,0);
49     }
50     while(scanf("%s",s)!=EOF)
51     {
52         printf("%d\n",Find(s,0));
53     }
54     return 0;
55 }

View Code

字典树指针：

 1 #include<iostream>
 2 #include<string.h>
 3 #include<stdio.h>
 4 using namespace std;
 5 
 6 const int maxn=10005;
 7 
 8 struct tire
 9 {
10     tire *next[26];
11     int num;
12     tire()
13     {
14         for(int i=0;i<26;i++)
15         {
16             next[i]=NULL;
17             num=0;
18         }
19     }
20 }root;
21 
22 void Insert(char *s)
23 {
24     tire *rt=&root;
25     for(int i=0;s[i];i++)
26     {
27         int x=s[i]-‘a‘;
28         if(rt->next[x]==NULL)
29         {
30             rt->next[x]=new tire;
31         }
32         rt=rt->next[x];
33         rt->num++;
34     }
35 }
36 
37 int Find(char *s)
38 {
39     tire *rt=&root;
40     for(int j=0;s[j];j++)
41     {
42         int x=s[j]-‘a‘;
43         if(rt->next[x]==NULL)
44         return 0;
45         rt=rt->next[x];
46     }
47     return rt->num;
48 }
49 
50 int main()
51 {
52     char s[maxn];
53     //freopen("aa.txt","r",stdin);
54     while(scanf("%s",s))
55     {
56         if(strcmp(s,"END")==0)
57         break;
58         Insert(s);
59     }
60     while(scanf("%s",s)!=EOF)
61     {
62         printf("%d\n",Find(s));
63     }
64     return 0;
65 }

View Code

搬果子

Time Limit: 2000 MS

Memory Limit: 32768 K

Total Submit: 22(17 users)

Total Accepted: 15(15 users)

Rating:

Special Judge: No

Description

果园里面有n堆果子，每堆果子有xi个，每个果子的重量为1，小明每次把i,j两堆果子移成一堆，需要花费的体力为xi+xj。最后移成一堆，求最小花费体力值。
其中1<=n<=10000,1<=m<=10000。均为正整数。

Input

每组数据第一行输入一个正整数n，表示有n堆果子。

接下来一行有n个正整数，表示每堆果子的重量。

输入以EOF结尾。

Output

每组数据单独一行，输出所花费的最小体力值。

Sample Input

1 2 9

1 3 9 18 30

Sample Output

109

Hint

Source

HCPC2014校赛训练赛 3

Author

0316 校赛训练赛3 解题报告,布布扣,bubuko.com

0316 校赛训练赛3 解题报告

原文：http://www.cnblogs.com/zhanzhao/p/3607872.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)