Engine
Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 165 Accepted Submission(s): 35
Problem Description
谷歌、百度等搜索引擎已经成为了互连网中不可或缺的一部分。在本题中,你的任务也是设计一个搜索论文的搜索引擎,当然,本题的要求比起实际的需求要少了许多。
本题的输入将首先给出一系列的论文,对于每篇论文首先给出标题,然后给出它被引用的次数。然后会有一系列的搜索询问,询问标题中包含特定关键词的论文有哪些。
每一个询问可能包含多个关键词,你需要找出标题包含所有关键词的论文。
“包含”必须是标题中有一个词正好是给定的关键词,不区分大小写。
对每个询问,都按被引用的次数从多到少输出满足条件的论文的标题。如果有被引用的次数相同的论文,则按照论文在输入中的顺序排列,先给出的论文排在前面。
本题的输入将首先给出一系列的论文,对于每篇论文首先给出标题,然后给出它被引用的次数。然后会有一系列的搜索询问,询问标题中包含特定关键词的论文有哪些。
每一个询问可能包含多个关键词,你需要找出标题包含所有关键词的论文。
“包含”必须是标题中有一个词正好是给定的关键词,不区分大小写。
对每个询问,都按被引用的次数从多到少输出满足条件的论文的标题。如果有被引用的次数相同的论文,则按照论文在输入中的顺序排列,先给出的论文排在前面。
Input
输入包含多组数据。
每组数据首先有一行包含一个整数N(1<=N<=1000),表示论文的数目,N=0表示输入结束。每组论文的信息第一行是论文的标题,由字母(大小写均可)和空格组成,不超过10个词,每个词不超过20个字符,标题总共不超过250个字符。第二行是一个整数K(0<=K<=108),表示它被引用的次数。在论文信息结束以后,有一行包含一个整数M(1<=M<=100),表示询问的数目。接下来有M行,每行是一个询问,由L(1<=L<=10)个空格分开的词构成,每个词不超过20个字符。
每组数据首先有一行包含一个整数N(1<=N<=1000),表示论文的数目,N=0表示输入结束。每组论文的信息第一行是论文的标题,由字母(大小写均可)和空格组成,不超过10个词,每个词不超过20个字符,标题总共不超过250个字符。第二行是一个整数K(0<=K<=108),表示它被引用的次数。在论文信息结束以后,有一行包含一个整数M(1<=M<=100),表示询问的数目。接下来有M行,每行是一个询问,由L(1<=L<=10)个空格分开的词构成,每个词不超过20个字符。
Output
对每个询问,按照题目给定的顺序输出满足条件的论文的标题;如果没有满足条件的论文,就不输出。在每组询问的输出之后输出一行”***”,在每组数据的输出之后输出一行”---”。
Sample Input
6 Finding the Shortest Path 120 Finding the k Shortest Path 80 Find Augmenting Path in General Graph 80 Matching in Bipartite Graph 200 Finding kth Shortest Path 50 Graph Theory and its Applications 40 6 shortest path k shortest path graph path find application 0
Sample Output
Finding the Shortest Path Finding the k Shortest Path Finding kth Shortest Path *** Finding the k Shortest Path *** Matching in Bipartite Graph Find Augmenting Path in General Graph Graph Theory and its Applications *** Finding the Shortest Path Finding the k Shortest Path Find Augmenting Path in General Graph Finding kth Shortest Path *** Find Augmenting Path in General Graph *** *** ---
Source
Recommend
lcy
本题一开始总是wa 感谢crystal提供的代码
#include<stdio.h> #include<string.h> #include<ctype.h> #include<stdlib.h> #define le 252 #define lne 1002 #define el 22 #define eel 12 struct haha { char word[eel][el],out[le]; int id,count,len;//len是单词的个数 count是论文引用的次数 id是输入编号 }a[1111]; int cmp(const void *s1,const void *s2) { return strcmp((char *)s1,(char *)s2); } int ccmp(const void *a,const void *b) { if((*(struct haha *)a).count==(*(struct haha *)b).count) return (*(struct haha *)a).id>(*(struct haha *)b).id?1:-1; else return (*(struct haha *)a).count<(*(struct haha *)b).count?1:-1; } int solve(char *str,int pos) { int i,j,t,len=strlen(str); j=t=0; int flag=0; char ss[100]; for(i=0;i<=len;i++) { if(isalpha(str[i])) { if(str[i]>='A'&&str[i]<='Z') { ss[j++]=str[i]+32; } else ss[j++]=str[i]; flag=1; } else if(flag)//注意这里很重要 因为防止空字符串加入到word中 这样可能会超过能保存的个数即12个 {//不要让空格以及空字符串保存进来 ss[j]='\0'; j=0; flag=0; strcpy(a[pos].word[t++],ss); } } return t; } int find(int pos) { int i,j,c2,c1,flag=0; c1=a[1100].len; c2=a[pos].len; if(c1>c2) return 0; for(i=0;i<c1;i++) { flag=0; for(j=0;j<c2;j++) { if(strcmp(a[1100].word[i],a[pos].word[j])==0) {flag=1; break;} } if(flag==0) return 0; } return 1; } int main() { int n,i,m; while(scanf("%d",&n)!=EOF) { if(!n) break; for(i=0;i<n;i++) { getchar(); gets(a[i].out); scanf("%d",&a[i].count); int t=solve(a[i].out,i); a[i].len = t; a[i].id=i; qsort (a[i].word,t,sizeof(a[i].word[0]),cmp); } scanf("%d",&m); qsort(a,n,sizeof(a[0]),ccmp); getchar(); while(m--) { gets(a[1100].out); int t=solve(a[1100].out,1100);//用a[1100]保存我们要查找的数据 a[1100].len=t; for(i=0;i<n;i++) { if(find(i)) { printf("%s\n",a[i].out); } } printf("***\n"); } printf("---\n"); } return 0; }
本人反思:
本题注意排序 排序的时候由于搞不清大于小于号表示的意义,WA了好几遍,一定要注意编程不能模棱两可,不能模模糊糊的就把它排出来,要严谨仔细