[湖南大学程序设计实训训练作业二]8.Engine-字符串(字符串切割+结构体map存储+切割vector查询)

el/2024/6/24 19:25:15

8.Engine-字符串

  • 写在前面
  • 【问题描述】
  • 【输入形式】
  • 【输出形式】
  • 【样例输入1】
  • 【样例输出1】
  • 【样例输入2】
  • 【样例输出2】
  • 题解
    • 思路
    • 代码

写在前面

这题真的是支棱了一个上午,可恶啊,中间出了些简单的bug但是找了好久,可恶啊!!!

【问题描述】

谷歌、百度等搜索引擎已经成为了互连网中不可或缺的一部分。在本题中,你的任务也是设计一个搜索论文的搜索引擎,当然,本题的要求比起实际的需求要少了许多。

   本题的输入将首先给出一系列的论文,对于每篇论文首先给出标题,然后给出它被引用的次数。然后会有一系列的搜索询问,询问标题中包含特定关键词的论文有哪些。每一个询问可能包含多个关键词,你需要找出标题包含所有关键词的论文。
“包含”必须是标题中有一个词正好是给定的关键词,不区分大小写。对每个询问,都按被引用的次数从多到少输出满足条件的论文的标题。如果有被引用的次数相同的论文,则按照论文在输入中的顺序排列,先给出的论文排在前面。

【输入形式】

每组数据首先有一行包含一个整数N(1<=N<=1000),表示论文的数目,N=0表示输入结束。每组论文的信息第一行是论文的标题,由字母(大小写均可)和空格组成,不超过10个词,每个词不超过20个字符,标题总共不超过250个字符。第二行是一个整数K(0<=K<=108),表示它被引用的次数。在论文信息结束以后,有一行包含一个整数M(1<=M<=100),表示询问的数目。接下来有M行,每行是一个询问,由L(1<=L<=10)个空格分开的词构成,每个词不超过20个字符。

【输出形式】

对每个询问,按照题目给定的顺序输出满足条件的论文的标题;如果没有满足条件的论文,就不输出。在每组询问的输出之后输出一行“***”,在每组数据的输出之后输出一行“—”。

【样例输入1】

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

【样例输出1】

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

【样例输入2】

1
Finding the Shortest Path
120
2
PathPat
0

【样例输出2】

Finding the Shortest Path******---

题解

思路

  • 1.name不区分大小写,所以我们统一转换为小写,但是又要保留原来的名字,所以,我们写一个结构体,有name和ture_name
  • 2.我们的查询是单词查询,比如查询find,那么finding是不匹配的,所以,我们用map来存储切割好的单词,用find和count方便查询
  • 3.我们查询的时候同样要切割,vector存储,每个单词就查询,每个单词都有,就是我们的结构
  • 4.当然我们输出的结果是需要排序的,所以,我们前面的结构体配合vector可以进行排序
  • 注意:先排序再查询输出出来的结果也是排序的,因为我们是从引用数从大到小的开始找的,所以输出的也是这个顺序。

代码

#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<algorithm>
#include<sstream>
using namespace std;
/******************将字符串全部转换为小写的函数************************/
string to_lower(string str){for(int i=0;i<str.length();i++){if(isupper(str[i])){str[i]=tolower(str[i]);}}return str;
}
/******************将字符串切割为单词存储到map,方便查询************************/
map<string,int> to_word_map(string str){map<string,int> temp;stringstream ss;ss<<str;while(ss>>str){temp[str]=1;} return temp;
}
/******************将字符串切割为单词存储到vector,方便查询************************/
vector<string> to_word_vector(string str){vector<string> temp;stringstream ss;ss<<str;while(ss>>str){temp.push_back(str);} return temp;
}
/*****************************论文结构体*******************************/
struct paper{map<string,int> name;//忽略大小写,用于查询 string true_name; int quote;
}; 
/***************************vector排序规则*****************************/
bool cmp(paper a,paper b){return a.quote>b.quote;
} 
int main(){int n,k;while(cin>>n){if(!n) break; vector<paper> res;while(n--){paper temp;cin.ignore();//忽略换行符 getline(cin,temp.true_name);//获取整行字符串 temp.name=to_word_map(to_lower(temp.true_name));//转换为小写再切割单词存到mapcin>>temp.quote;res.push_back(temp);} sort(res.begin(),res.end(),cmp);//先进行排序后再查询出来的结构自然是排序的 cin>>k;cin.ignore();while(k--){string check;getline(cin,check);check=to_lower(check);/**********************查询比较麻烦,不能直接find**************************/ /**********************所以我们要做一个单词切割****************************/ vector<string> check_word=to_word_vector(check);//切割存储到vectorfor(int i=0;i<res.size();i++){//遍历排序好的论文 int j;for(j=0;j<check_word.size();j++){//一个单词一个单词的去找 if(res[i].name.find(check_word[j])==res[i].name.end())	break;} if(j==check_word.size()) cout<<res[i].true_name<<endl; //如果每个单词都找到了就输出 }cout<<"***"<<endl;	} cout<<"---"<<endl;		}return 0;
} 

http://www.ngui.cc/el/3573932.html

相关文章

[湖南大学程序设计实训训练作业二]9.字符串压缩(贪心递归模拟)

9.字符串压缩【问题描述】【输入形式】【输出形式】【样例输入1】【样例输出1】【样例输入2】【样例输出2】【样例输入3】【样例输出3】题解思路代码【问题描述】 给定一个由n个小写字母组成的字符串s&#xff0c;需要使用最少数量的钱币来压缩它。 压缩该字符串&#xff0c;…

[湖南大学程序设计实训训练作业二]10.拼写检查(正难则反!)

10.拼写检查【问题描述】【输入形式】【输出形式】【样例输入】【样例输出】题解思路代码【问题描述】 作为一个新的拼写检查程序开发团队的成员&#xff0c;您将编写一个模块&#xff0c;用已知的所有形式正确的词典来检查给定单词的正确性。 如果字典中没有这个词&#xff0…

[湖南大学程序设计实训训练作业二]11.最小的k个数(认识set)

11.最小的k个数【问题描述】【输入形式】【输出形式】【样例输入】【样例输出】【Tips】题解思路代码【问题描述】 输入n个整数&#xff0c;找出其中最小的k&#xff08;k<n&#xff09;个不同数。例如输入4,5,1,6,1,7,3,8这8个数字&#xff0c;则最小的4个数字是1,3,4,5。…

[湖南大学程序设计实训训练作业二]12. 绩点计算

12. 绩点计算【问题描述】【输入形式】【输出形式】【样例输入】【样例输出】题解思路代码【问题描述】 学校对本科生的成绩施行绩点制&#xff08;GPA&#xff09;。将学生的实际考分根据不同学科的不同学分按一定的公式进行计算。规定如下&#xff1a; 实际成绩绩点90-1004…

[湖南大学程序设计实训训练作业二]13.xxx定律(用递归装起来!)

13.xxx定律【问题描述】【输入形式】【输出形式】【样例输入】【样例输出】题解思路代码【问题描述】 对于一个正整数n&#xff0c;如果是偶数&#xff0c;就把n砍掉一半&#xff1b;如果是奇数&#xff0c;把n变成 3*n 1后砍掉一半&#xff0c;直到该数变为1为止。 请计算需要…

[湖南大学程序设计实训训练作业二]14.数的距离差

14.数的距离差【问题描述】【输入形式】【输出形式】【样例输入1】【样例输出1】【样例输入2】【样例输出2】题解思路代码【问题描述】 给定一组正整数&#xff0c;其中最大值和最小值分别为Max和Min, 其中一个数x到Max和Min的距离差定义为&#xff1a; abs(abs(x-Max)-(x-Min…

[湖南大学程序设计实训训练作业二]16.金币

16.金币【问题描述】【输入形式】【输出形式】【样例输入】【样例输出】题解思路代码【问题描述】 国王为他的忠诚的骑士支付金币。在他服役的第一天&#xff0c;骑士收到一枚金币。在接下来2天&#xff08;第二天和第三天的服务&#xff09;&#xff0c;骑士每天收到2金币。在…

[湖南大学程序设计实训训练作业二]15.亲和数

15.亲和数【问题描述】【输入形式】【输出形式】【样例输入】【样例输出】题解思路代码【问题描述】 古希腊数学家毕达哥拉斯在自然数研究中发现&#xff0c;220 的所有真约数(即不是自身的约数)之和为&#xff1a; 1245101120224455110&#xff1d;284。而 284 的所有真约数为…

[湖南大学程序设计实训训练作业二]17.小A的计算器

17.小A的计算器【问题描述】【输入形式】【输出形式】【样例输入】【样例输出】题解思路代码【问题描述】 以往的操作系统内部的数据表示都是二进制方式&#xff0c;小A新写了一个操作系统&#xff0c;系统内部的数据表示为26进制&#xff0c;其中0-25分别由a-z表示。 现在小A…

[湖南大学程序设计实训训练作业二]18.小丑排序

18.小丑排序【问题描述】【输入形式】【输出形式】【样例输入】【样例输出】题解思路代码【问题描述】 你在信天翁马戏团&#xff08;是的&#xff0c;它是由一群小丑组成&#xff09;从事管理工作&#xff0c;你刚刚写完一个程序的输出是将他们的姓名按长度为非递减的方式排列…