PAT

目录

1100 Mars Numbers (20分)

1054 The Dominant Color (20分)

1071 Speech Patterns (25分)

1022 Digital Library (30分)

---

1100 Mars Numbers (20分)

People on Mars count their numbers with base 13:

Zero on Earth is called "tret" on Mars.The numbers 1 to 12 on Earth is called "jan, feb, mar, apr, may, jun, jly, aug, sep, oct, nov, dec" on Mars, respectively.For the next higher digit, Mars people name the 12 numbers as "tam, hel, maa, huh, tou, kes, hei, elo, syy, lok, mer, jou", respectively.

For examples, the number 29 on Earth is called "hel mar" on Mars; and "elo nov" on Mars corresponds to 115 on Earth. In order to help communication between people from these two planets, you are supposed to write a program for mutual translation between Earth and Mars number systems.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (<100). Then N lines follow, each contains a number in [0, 169), given either in the form of an Earth number, or that of Mars.

Output Specification:

For each number, print in a line the corresponding number in the other language.

Sample Input:

4 29 5 elo nov tam

Sample Output:

hel mar may 115 13

样例解释：

29=2*13+3  ->（取十位数字2，个位数字3）结果 hel mar

elo nov =8*13 +11 =115 

思路：

map<string,int> mp;   string numTostr[170]; 打表存放最终结果

#include<cstdio> #include<cstdlib> #include<algorithm> #include<iostream> #include<string> #include<cstring> #include<vector> #include<set> #include<map> #include<cmath> #define pb push_back using namespace std; string str1[13]={"tret","jan","feb", "mar", "apr", "may", "jun", "jly", "aug", "sep", "oct", "nov", "dec"};//0-12 string str2[13]={"tret","tam","hel", "maa", "huh", "tou", "kes", "hei", "elo", "syy", "lok", "mer", "jou"};//13 26 39 52 65...156=12*13 int n; map<string,int> mp; //火星文->数字 string numTostr[170]; //数字->火星文 void init(){ for(int i=0;i<13;i++){ numTostr[i]=str1[i]; mp[str1[i]]=i; numTostr[i*13]=str2[i]; mp[str2[i]]=i*13; } for(int i=1;i<13;i++){ //十位 for(int j=1;j<13;j++){ //个位 string str=str2[i]+" "+str1[j]; numTostr[i*13+j]=str; mp[str]=i*13+j; } } } int main(){ init(); scanf("%d",&n); getchar(); string tmp; while(n--){ getline(cin,tmp); if(tmp[0]>='0' && tmp[0]<='9'){ //数字型 int res=0; for(int i=0;i<tmp.length();i++){ res=res*10+(tmp[i]-'0'); } printf("%s\n",numTostr[res].c_str()); //c_str() //cout<<numTostr[res]<<"\n"; }else{ printf("%d\n",mp[tmp]); } } return 0; }

 

1054 The Dominant Color (20分)

Behind the scenes in the computer's memory, color is always talked about as a series of 24 bits of information for each pixel. In an image, the color with the largest proportional area is called the dominant color.

A strictly dominant color takes more than half of the total area. Now given an image of resolution M by N (for example, 800×600), you are supposed to point out the strictly dominant color.

Input Specification:

Each input file contains one test case. For each case, the first line contains 2 positive numbers: M (≤800) and N (≤600) which are the resolutions of the image. Then N lines follow, each contains M digital colors in the range [0,2​24​​). It is guaranteed that the strictly dominant color exists for each input image. All the numbers in a line are separated by a space.

Output Specification:

For each test case, simply print the dominant color in a line.

Sample Input:

5 3 0 0 255 16777215 24 24 24 0 0 24 24 0 24 24 24

Sample Output:

24

题意：给定M*N的矩阵，找出其中出现次数超过一半且出现次数最多的数字

思路：map<int,int> 

#include<cstdio> #include<cstdlib> #include<algorithm> #include<iostream> #include<string> #include<cstring> #include<vector> #include<set> #include<map> #include<cmath> #define pb push_back using namespace std; map<int,int> mp; int n,m; int main(){ scanf("%d%d",&n,&m); int num; for(int i=0;i<n*m;i++){ scanf("%d",&num); if(mp.find(num)!=mp.end()){ mp[num]++; }else{ mp[num]=1; } } int key,maxn=-1; for(map<int,int>::iterator it=mp.begin();it!=mp.end();it++){ if(it->second>maxn){ maxn=it->second; key=it->first; } } printf("%d",key); return 0; }

 

1071 Speech Patterns (25分)

People often have a preference among synonyms of the same word.

For example, some may prefer "the police", while others may prefer "the cops".

Analyzing such patterns can help to narrow down a speaker's identity,

which is useful when validating, for example, whether it's still the same person behind an online avatar.

Now given a paragraph of text sampled from someone's speech, can you find the person's most commonly used word（口头禅）?

Input Specification:

Each input file contains one test case. For each case, there is one line of text no more than 1048576 characters in length, terminated by a carriage return \n. The input contains at least one alphanumerical character, i.e., one character from the set [0-9 A-Z a-z].

Output Specification:

For each test case, print in one line the most commonly occurring word in the input text, followed by a space and the number of times it has occurred in the input. If there are more than one such words, print the lexicographically smallest one. The word should be printed in all lower case. Here a "word" is defined as a continuous sequence of alphanumerical characters separated by non-alphanumerical characters or the line beginning/end.

Note that words are case insensitive.

Sample Input:

Can1: "Can a can can a can? It can!"

Sample Output:

can 5

思路：map<string,int> ;

注意点：一个句子中单词的划分

code：

#include<cstdio> #include<cstdlib> #include<algorithm> #include<iostream> #include<string> #include<cstring> #include<vector> #include<set> #include<map> #include<cmath> #define pb push_back using namespace std; bool check(char c){ if(c>='0' && c<='9')return true; if(c>='a' && c<='z')return true; if(c>='A' && c<='Z')return true; return false; } int main(){ string str; map<string,int> mp; getline(cin,str); int i=0; while(i<str.length()){ string word; while(i<str.length() && check(str[i])){ if(str[i]>='A' && str[i]<='Z'){//大写-小写 str[i]+=32; } //cout<<str[i]<<endl; word+=str[i]; i++; } if(word!=""){ if(mp.find(word)==mp.end())mp[word]=1; else mp[word]++; } while(i<str.length() && !check(str[i]))i++; } int maxn=-1;string ans; for(map<string,int>::iterator it=mp.begin();it!=mp.end();it++){ if(it->second>maxn){ ans=it->first; maxn=it->second; } } //printf("%s %d",ans.c_str(),maxn); cout<<ans<<" "<<maxn<<"\n"; return 0; }

 

 

 

 

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 N (≤10^​4​​) which is the total number of books.

Then Nblocks 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;

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 title2: name of an author3: a key word4: name of a publisher5: 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

 思路：map<string,set<int> >

#include <iostream> #include <bits/stdc++.h> using namespace std; //由于均是查询Id，故可将Id看做value，其余属性每一项看做key 构建map map<string,set<int> > title, author, key, pub, year; void query(map<string,set<int> >&mp, string &str){//取消引用最后一个测试用例会超时 if(mp.find(str) != mp.end()){ for(set<int>::iterator it = mp[str].begin(); it != mp[str].end(); it++){ //注意迭代器的格式，不是map //也可用 auto c++11特性PAT支持 printf("%07d\n",*it);//*不确定宽度，错两个样例 } } else printf("Not Found\n"); } int main() { int n,m,id,num; scanf("%d",&n); string _title,_author,_key,_pub,_year; for(int i = 0; i < n; i++){ scanf("%d",&id); getchar();//* 或者直接scanf("%d\n",&id); getline(cin,_title); title[_title].insert(id); getline(cin,_author); author[_author].insert(id); while(cin >> _key){ //* key[_key].insert(id); if(getchar()=='\n') break; } getline(cin,_pub); pub[_pub].insert(id); getline(cin, _year); year[_year].insert(id); } scanf("%d",&m); while(m--){ scanf("%d: ",&num);//* string str; getline(cin,str); cout << num << ": " << str << "\n"; if(num==1) query(title,str); else if(num==2) query(author,str); else if(num==3) query(key,str); else if(num==4) query(pub,str); else if(num==5) query(year,str); } return 0; }