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個字符。
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
The 6th UESTC Programming Contest
Recommend
lcy
本題一開始總是wa 感謝crystal提供的代碼
[cpp] 、
#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;
}
#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;
}
