首页 > ACM题库 > HDU-杭电 > hdu 2532 Engine-字符串-[解题报告]C++
2014
02-09

hdu 2532 Engine-字符串-[解题报告]C++

Engine

问题描述 :

谷歌、百度等搜索引擎已经成为了互连网中不可或缺的一部分。在本题中,你的任务也是设计一个搜索论文的搜索引擎,当然,本题的要求比起实际的需求要少了许多。
本题的输入将首先给出一系列的论文,对于每篇论文首先给出标题,然后给出它被引用的次数。然后会有一系列的搜索询问,询问标题中包含特定关键词的论文有哪些。
每一个询问可能包含多个关键词,你需要找出标题包含所有关键词的论文。
“包含”必须是标题中有一个词正好是给定的关键词,不区分大小写。
对每个询问,都按被引用的次数从多到少输出满足条件的论文的标题。如果有被引用的次数相同的论文,则按照论文在输入中的顺序排列,先给出的论文排在前面。

输入:

输入包含多组数据。
每组数据首先有一行包含一个整数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个字符。

样例输入:

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

样例输出:

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
***
***
---

本来可以把这篇文章放入上一篇文章里,不过做这个题花了一点时间,也有一点收获,同时觉得网上的这个题目可供参考的文章有些少,那么就单独成篇吧。

首先分析下题目思路:

这个题目是个模拟题,步骤也很清晰。

首先需要每行读入,将论文的名字,序号,与被引数放到一个结构体里,同时需要一步处理:将文章名称分为关键字存储。

然后程序进行一次排序,以被引数为第一关键字,以号数为第二关键字排序。

排序之后,按照类似方式读入查询命令,将查询命令分为不同关键字,将这些关键字挨着与论文关键字比较,相同即可输出。

按照这些步骤就可以写出靠谱的代码了,结果我还是wa了三次。。

先上代码,收获就放后面,可忽略。。

#include<stdio.h>
 #include<string.h>
 #include<stdlib.h>
 typedef struct record
 {
     int num;
     int count;
     int keyL;
     char name[300];
     char afname[300];
     char key[11][21];
 }Record;
 Record rec[1001];
 Record qy;
 int divide(char a[],char b[11][21],int n)
 {
     int cur=0,j=0;
     for(int i=0;i<n;i++)
     {
         if(a[i]==' ')
         {cur++;j=0;}
         else
             b[cur][j++]=a[i];
     }
     return cur+1;
 }
 int cmp(const void *a,const void *b)
 {
     Record c = *(Record *)a;
     Record d = *(Record *)b;
     if(c.count==d.count)
         return c.num - d.num;
     else return d.count - c.count;//优先按coun排序,大的在前
 }
 
 int match(char qry[11][21],char tar[11][21],int qn,int tn)
 {
     int num=0;
     for(int x=0;x<qn;x++)
     {
         for(int y=0;y<tn;y++)
             if(strcmp(qry[x],tar[y])==0)
             {
                 num++;
                 break;
             }
     }
     if(num==qn)
         return 1;
     else
         return 0;
 }
 
 void init(char a[],int n,char b[])
 {
     for(int ii=0;ii<n;ii++)
     {
         if(a[ii]<='Z'&&a[ii]>='A')
             {
              b[ii]=char(a[ii]+32);
             }
         else
             b[ii]=a[ii];
     }
 
 }
 int main()
 {
     int T,i;
     while(scanf("%d",&T))
     {
         if(T==0)break;
         memset(rec,0,sizeof(Record)*T);
         getchar();
         for(i=0;i<T;i++)
         {
             gets(rec[i].name);
             init(rec[i].name,strlen(rec[i].name),rec[i].afname);
             scanf("%d",&rec[i].count);
             getchar();
             rec[i].keyL=divide(rec[i].afname,rec[i].key,strlen(rec[i].name));
             rec[i].num=i+1;
         }
         qsort(rec,T,sizeof(Record),cmp);
         int k;
         scanf("%d",&k);getchar();
         for(i=0;i<k;i++)
         {
             memset(&qy,0,sizeof(Record));
             gets(qy.name);
             init(qy.name,strlen(qy.name),qy.afname);
             qy.keyL=divide(qy.afname,qy.key,strlen(qy.name));
             for(int j=0;j<T;j++)
             {
                 if(match(qy.key,rec[j].key,qy.keyL,rec[j].keyL))
                 {
                     puts(rec[j].name);
                 }
             }
             printf("***\n");
         }
         printf("---\n");
     }
     return 0;
 }

 

代码方面这是第一次全用C写的结构体+重载比较函数构成的多关键字排序,(之前常用C++),

第一次碰到读入一行的问题,解决方法是在用scanf读入之后,要用getchar+gets配合,

第一次处理memset多组初始化问题memset(rec,0,sizeof(Record)*T);+memset(&qy,0,sizeof(Record));配合使用。

其他的一些辅助函数用来模拟的就不值一提了。

非代码方面,这题大体思路昨晚已经有了,但wa了两次,在不知道错误原因的情况下担心wa之后是TLE,所以当时有点心灰意冷,其实最近也一直很忐忑,面试的通知一直没下来,今天妹妹升学宴又出去一天,可晚上回来没想到只用了半小时就调了两个bug出来,而且A了这个少有人问津的题目。虽然心中依然忐忑,依然对未知的错误充满恐惧,但是我相信会好起来的。

—一个事情,自己找不到原因,非常可怕。

解题转自:http://www.cnblogs.com/holyprince/p/3283681.html


  1. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  2. #include <stdio.h>
    int main()
    {
    int n,p,t[100]={1};
    for(int i=1;i<100;i++)
    t =i;
    while(scanf("%d",&n)&&n!=0){
    if(n==1)
    printf("Printing order for 1 pages:nSheet 1, front: Blank, 1n");
    else {
    if(n%4) p=n/4+1;
    else p=n/4;
    int q=4*p;
    printf("Printing order for %d pages:n",n);
    for(int i=0;i<p;i++){
    printf("Sheet %d, front: ",i+1);
    if(q>n) {printf("Blank, %dn",t[2*i+1]);}
    else {printf("%d, %dn",q,t[2*i+1]);}
    q–;//打印表前
    printf("Sheet %d, back : ",i+1);
    if(q>n) {printf("%d, Blankn",t[2*i+2]);}
    else {printf("%d, %dn",t[2*i+2],q);}
    q–;//打印表后
    }
    }
    }
    return 0;
    }