PAT 1022 Digital Library
目录
题目
1022 Digital Library（数字图书馆） (30 分)
A Digital Library contains millions of books, stored according to their titles, authors, key words of their abstracts, publishers, and published years. Each book is assigned an unique 7-digit number as its ID. Given any query from a reader, you are supposed to output the resulting books, sorted in increasing order of their ID's.（以递增的顺序排序）
Input Specification:
Each input file contains one test case. For each case, the first line contains a positive integer
which is the total number of books. Then N blocks follow, each contains the information of a book in 6 lines:
Line #1: the 7-digit ID number;
Line #2: the book title -- a string of no more than 80 characters;
Line #3: the author -- a string of no more than 80 characters;
Line #4: the key words -- each word is a string of no more than 10 characters without any white space, and the keywords are separated by exactly one space;
Line #5: the publisher -- a string of no more than 80 characters;
Line #6: the published year -- a 4-digit number which is in the range [1000, 3000].
It is assumed that each book belongs to one author only（作者唯一）, and contains no more than 5 key words（不超过5个关键字）; there are no more than 1000 distinct key words in total; and there are no more than 1000 distinct publishers.
After the book information, there is a line containing a positive integer M (≤1000) which is the number of user's search queries. Then M lines follow, each in one of the formats shown below:
1: a book title
2: name of an author
3: a key word
4: name of a publisher
5: a 4-digit number representing the year
Output Specification:
For each query, first print the original query in a line, then output the resulting book ID's in increasing order, each occupying（占用） a line. If no book is found, print Not Found instead.
Sample Input:
3
1111111
The Testing Book
Yue Chen
test code debug sort keywords
ZUCS Print
2011
3333333
Another Testing Book
Yue Chen
test code sort keywords
ZUCS Print2
2012
2222222
The Testing Book
CYLL
keywords debug book
ZUCS Print2
2011
6
1: The Testing Book
2: Yue Chen
3: keywords
4: ZUCS Print
5: 2011
3: blablabla
Sample Output:
1: The Testing Book
1111111
2222222
2: Yue Chen
1111111
3333333
3: keywords
1111111
2222222
3333333
4: ZUCS Print
1111111
5: 2011
1111111
2222222
3: blablabla
Not Found
注意点：
1、getchar()回车符的吸收
2、最后的输出格式
printf("%07d\n", (*it));3、分词
我认为自己想的分词方法可能是不正确的，导致只能得25分
string keywords; //关键词
getline(cin, keywords);
//分词,这种分词方式的正确性对于此道题目不一定正确
int len = 0;
while (len<keywords.length())
{
string word;
while (len<keywords.length()&&check(keywords[len]))
{
word += keywords[len];//形成有效单词
len++;
}
m3[word].insert(bookId); //将该单词与书的id进行映射
while (check(keywords[len])==false)
{
len++;
}
}通过算法笔记，学会了一个比较全面的分词方法，并最终获得了满分，之后在自己写的代码版本中，使用了下面的分词方法，通过了所有测试用例
while (cin>>keyword)
{
mpKeywords[keyword].insert(bookId);
char c = getchar();//cin后的字符
if (c=='\n')//如果为回车，则表示输入结束
{
break;
}
}4、scanf能控制格式输入
int type;
scanf("%d: ", &type);5、对于set控制输出时的回车，无法使用it+1!= m1[query].end()来完成
for (auto it = m1[query].begin(); it != m1[query].end();it++)
{
printf("%d\n", (*it));
if (++it != m1[query].end())
{
printf("\n");
}
it--;
}
自己写的所有代码
代码版本一
#include<iostream>
#include<cstdio>
#include<map>
#include<string>
#include<set>
using namespace std;
map<string, set<int>> m1;//书名与书id的映射
map<string, set<int>> m2; //作者名与书id的映射
map<string, set<int>> m3; //关键词与书id的映射
map<string, set<int>> m4; //出版社与书id的映射
map<string, set<int>> m5; //出版时间与书id的映射
bool check(char c){//判断是否为有效字符
if(c>='a'&&c<='z')
return true;
return false;
}
int main(){
int N;//书的数量
scanf("%d", &N);
for (int i = 0; i < N; i++)
{
int bookId; //书id
cin >> bookId;//输入书id
getchar();//吸收回车符
string bookTitle; //书名
getline(cin, bookTitle);
m1[bookTitle].insert(bookId);
string author; //作者
getline(cin, author);
m2[author].insert(bookId);
string keywords; //关键词
getline(cin, keywords);
//分词
int len = 0;
while (len<keywords.length())
{
string word;
while (len<keywords.length()&&check(keywords[len]))
{
word += keywords[len];//形成有效单词
len++;
}
m3[word].insert(bookId); //将该单词与书的id进行映射
while (check(keywords[len])==false)
{
len++;
}
}
string publish; //出版社与作者id进行映射
getline(cin, publish);
m4[publish].insert(bookId);
string year; //出版年份与作者id进行映射
getline(cin, year);
m5[year].insert(bookId);
}
/*查询*/
int M; //要查询的次数
scanf("%d", &M);
getchar();//吸收回车符
for (int i = 0; i < M; i++)
{
string test;
cin >> test;
getchar();
string query;
getline(cin, query);
/*根据作者名称查询*/
cout << test << " " << query << endl; //输出查询标题
map<string, set<int>> temp;
bool flag = false;
if (m1.find(query)!=m1.end())
{
temp = m1;
flag = true;
}else if(m2.find(query)!=m2.end()){
temp = m2;
flag = true;
}
else if (m3.find(query) != m3.end())
{
temp = m3;
flag = true;
}
else if (m4.find(query) != m4.end())
{
temp = m4;
flag = true;
}
else if (m5.find(query) != m5.end())
{
temp = m5;
flag = true;
}
if (flag)//能搜索到
{
for (auto it = temp[query].begin(); it != temp[query].end(); it++)
{
printf("%d\n", (*it));
}
}else//不能搜索到
{
printf("Not Found\n");
}
}
//system("pause");
return 0;
}
代码版本二
#include<iostream>
#include<cstdio>
#include<map>
#include<string>
#include<set>
using namespace std;
map<string, set<int>> m1;//书名与书id的映射
map<string, set<int>> m2; //作者名与书id的映射
map<string, set<int>> m3; //关键词与书id的映射
map<string, set<int>> m4; //出版社与书id的映射
map<string, set<int>> m5; //出版时间与书id的映射
bool check(char c){//判断是否为有效字符
if(c>='a'&&c<='z')
return true;
return false;
}
int main(){
int N;//书的数量
scanf("%d", &N);
for (int i = 0; i < N; i++)
{
int bookId; //书id
cin >> bookId;//输入书id
getchar();//吸收回车符
string bookTitle; //书名
getline(cin, bookTitle);
m1[bookTitle].insert(bookId);
string author; //作者
getline(cin, author);
m2[author].insert(bookId);
string keywords; //关键词
getline(cin, keywords);
//分词
int len = 0;
while (len<keywords.length())
{
string word;
while (len<keywords.length()&&check(keywords[len]))
{
word += keywords[len];//形成有效单词
len++;
}
m3[word].insert(bookId); //将该单词与书的id进行映射
while (check(keywords[len])==false)
{
len++;
}
}
string publish; //出版社与作者id进行映射
getline(cin, publish);
m4[publish].insert(bookId);
string year; //出版年份与作者id进行映射
getline(cin, year);
m5[year].insert(bookId);
}
/*查询*/
int M; //要查询的次数
scanf("%d", &M);
getchar();//吸收回车符
for (int i = 0; i < M; i++)
{
string test;
cin >> test;
getchar();
string query;
getline(cin, query);
/*根据作者名称查询*/
cout << test << " " << query << endl; //输出查询标题
map<string, set<int>> *temp;
bool flag = false;
if (m1.find(query)!=m1.end())
{
temp = &m1;
flag = true;
}else if(m2.find(query)!=m2.end()){
temp = &m2;
flag = true;
}
else if (m3.find(query) != m3.end())
{
temp = &m3;
flag = true;
}
else if (m4.find(query) != m4.end())
{
temp = &m4;
flag = true;
}
else if (m5.find(query) != m5.end())
{
temp = &m5;
flag = true;
}
if (flag)//能搜索到
{
for (auto it = temp->find(query)->second.begin(); it != temp->find(query)->second.end(); it++)
{
printf("%07d\n", (*it));
}
}else//不能搜索到
{
printf("Not Found\n");
}
}
system("pause");
return 0;
}
代码版本三
#include<iostream>
#include<cstdio>
#include<map>
#include<string>
#include<set>
using namespace std;
map<string, set<int>> m1;//书名与书id的映射
map<string, set<int>> m2; //作者名与书id的映射
map<string, set<int>> m3; //关键词与书id的映射
map<string, set<int>> m4; //出版社与书id的映射
map<string, set<int>> m5; //出版时间与书id的映射
bool check(char c){//判断是否为有效字符
if(c>='a'&&c<='z')
return true;
if (c >= 'A' && c <= 'Z')
return true;
if (c >= '0' && c <= '9')
return true;
return false;
}
int main(){
int N;//书的数量
scanf("%d", &N);
for (int i = 0; i < N; i++)
{
int bookId; //书id
cin >> bookId;//输入书id
getchar();//吸收回车符
string bookTitle; //书名
getline(cin, bookTitle);
m1[bookTitle].insert(bookId);
string author; //作者
getline(cin, author);
m2[author].insert(bookId);
string keywords; //关键词
getline(cin, keywords);
//分词,这种分词方式的正确性对于此道题目不一定正确
int len = 0;
while (len<keywords.length())
{
string word;
while (len<keywords.length()&&check(keywords[len]))
{
word += keywords[len];//形成有效单词
len++;
}
m3[word].insert(bookId); //将该单词与书的id进行映射
while (check(keywords[len])==false)
{
len++;
}
}
string publish; //出版社与作者id进行映射
getline(cin, publish);
m4[publish].insert(bookId);
string year; //出版年份与作者id进行映射
getline(cin, year);
m5[year].insert(bookId);
}
/*查询*/
int M; //要查询的次数
scanf("%d", &M);
getchar();//吸收回车符
for (int i = 0; i < M; i++)
{
int type;
scanf("%d: ", &type);
string query;
getline(cin, query);
/*根据作者名称查询*/
cout << type << ": " << query << endl; //输出查询标题
map<string, set<int>> *temp;
bool flag = false;
if (m1.find(query)!=m1.end())
{
temp = &m1;
flag = true;
}else if(m2.find(query)!=m2.end()){
temp = &m2;
flag = true;
}
else if (m3.find(query) != m3.end())
{
temp = &m3;
flag = true;
}
else if (m4.find(query) != m4.end())
{
temp = &m4;
flag = true;
}
else if (m5.find(query) != m5.end())
{
temp = &m5;
flag = true;
}
if (flag)//能搜索到
{
for (auto it = temp->find(query)->second.begin(); it != temp->find(query)->second.end(); it++)
{
printf("%07d\n", (*it));
}
}else//不能搜索到
{
printf("Not Found\n");
}
}
system("pause");
return 0;
}
参考了算法笔记写的代码
代码版本四
#include<iostream>
#include<map>
#include<set>
using namespace std;
typedef map<string, set<int>> mymap;//重定义
mymap mpTitle, mpAuthor, mpKeywords, mpPublisher, mpPublishYear;
void query(mymap &m, string &text);
int main(){
int N,M,bookId;
string title, author, keyword, publisher, publisherYear;
scanf("%d", &N);//输入书的数量
for (int i = 0; i < N; i++)
{
scanf("%d", &bookId);
getchar(); //吸收回车符
getline(cin,title);
mpTitle[title].insert(bookId);
getline(cin, author);
mpAuthor[author].insert(bookId);
//分词
while (cin>>keyword)
{
mpKeywords[keyword].insert(bookId);
char c = getchar();//cin后的字符
if (c=='\n')//如果为回车，则表示输入结束
{
break;
}
}
getline(cin, publisher);
mpPublisher[publisher].insert(bookId);
getline(cin, publisherYear);
mpPublishYear[publisherYear].insert(bookId);
}
//查询
scanf("%d", &M);
getchar();//吸收回车符
for (int i = 0; i < M; i++)
{
int type;//类型
string text;//要查询的内容
scanf("%d: ", &type); //亮点，自己没想到这种输入格式
getline(cin, text);
cout << type << ": " << text << endl;
if (type==1) query(mpTitle, text);
if (type==2) query(mpAuthor, text);
if (type == 3) query(mpKeywords, text);
if (type == 4) query(mpPublisher, text);
if (type == 5) query(mpPublishYear, text);
}
system("pause");
return 0;
}
void query(mymap &m,string &text){
if (m.find(text)!=m.end())//如果能被找到
{
for (auto it = m[text].begin(); it != m[text].end(); it++)
{
printf("%07d\n", (*it));
}
}else
{
printf("Not Found\n");
}
}
代码版本五（正确代码）
结合了算法笔记上的分词方法（我之前的分词方法存在错误），我写的代码终于全部通过测试用例
#include<iostream>
#include<cstdio>
#include<map>
#include<string>
#include<set>
using namespace std;
map<string, set<int>> m1;//书名与书id的映射
map<string, set<int>> m2; //作者名与书id的映射
map<string, set<int>> m3; //关键词与书id的映射
map<string, set<int>> m4; //出版社与书id的映射
map<string, set<int>> m5; //出版时间与书id的映射
bool check(char c){//判断是否为有效字符
if(c>='a'&&c<='z')
return true;
if (c >= 'A' && c <= 'Z')
return true;
if (c >= '0' && c <= '9')
return true;
return false;
}
int main(){
int N;//书的数量
scanf("%d", &N);
for (int i = 0; i < N; i++)
{
int bookId; //书id
cin >> bookId;//输入书id
getchar();//吸收回车符
string bookTitle; //书名
getline(cin, bookTitle);
m1[bookTitle].insert(bookId);
string author; //作者
getline(cin, author);
m2[author].insert(bookId);
//分词,这种分词方式的正确性对于此道题目不一定正确
string keyword;
while (cin >> keyword)
{
m3[keyword].insert(bookId);
char c = getchar(); //cin后的字符
if (c == '\n') //如果为回车，则表示输入结束
{
break;
}
}
string publish; //出版社与作者id进行映射
getline(cin, publish);
m4[publish].insert(bookId);
string year; //出版年份与作者id进行映射
getline(cin, year);
m5[year].insert(bookId);
}
/*查询*/
int M; //要查询的次数
scanf("%d", &M);
getchar();//吸收回车符
for (int i = 0; i < M; i++)
{
int type;
scanf("%d: ", &type);
string query;
getline(cin, query);
/*根据作者名称查询*/
cout << type << ": " << query << endl; //输出查询标题
map<string, set<int>> *temp;
bool flag = false;
if (m1.find(query)!=m1.end())
{
temp = &m1;
flag = true;
}else if(m2.find(query)!=m2.end()){
temp = &m2;
flag = true;
}
else if (m3.find(query) != m3.end())
{
temp = &m3;
flag = true;
}
else if (m4.find(query) != m4.end())
{
temp = &m4;
flag = true;
}
else if (m5.find(query) != m5.end())
{
temp = &m5;
flag = true;
}
if (flag)//能搜索到
{
for (auto it = temp->find(query)->second.begin(); it != temp->find(query)->second.end(); it++)
{
printf("%07d\n", (*it));
}
}else//不能搜索到
{
printf("Not Found\n");
}
}
system("pause");
return 0;
}
结果
上一篇： [PAT-A 1022]Digital Library
下一篇： CSP 202006-2 稀疏向量
推荐阅读
-
[PAT-A 1022]Digital Library
-
PAT 1022 Digital Library
-
PAT.A1022 Digital Library
-
PAT A1022. Digital Library (30)
-
PAT甲级 1022 Digital Library (30分)
-
PAT 1022 D进制的A+B (20分)（Java）
-
【PAT甲级 映射】1022 Digital Library (30 分)
-
PAT甲级 1022 Digital Library （暨 set、map总结）
-
PAT 甲级 1022 Digital Library
-
PAT 甲级 1022 Digital Library