1012 The Best Rank (25 分)
To evaluate the performance of our first year CS majored students, we consider their grades of three courses only: C - C Programming Language, M - Mathematics (Calculus or Linear Algrbra), and E - English. At the mean time, we encourage students by emphasizing on their best ranks — that is, among the four ranks with respect to the three courses and the average grade, we print the best rank for each student.
For example, The grades of C, M, E and A - Average of 4 students are given as the following:
StudentID C M E A 310101 98 85 88 90 310102 70 95 88 84 310103 82 87 94 88 310104 91 91 91 91
Then the best ranks for all the students are No.1 since the 1st one has done the best in C Programming Language, while the 2nd one in Mathematics, the 3rd one in English, and the last one in average.
Input Specification:
Each input file contains one test case. Each case starts with a line containing 2 numbers N and M (≤2000), which are the total number of students, and the number of students who would check their ranks, respectively. Then N lines follow, each contains a student ID which is a string of 6 digits, followed by the three integer grades (in the range of [0, 100]) of that student in the order of C, M and E. Then there are M lines, each containing a student ID.
Output Specification:
For each of the M students, print in one line the best rank for him/her, and the symbol of the corresponding rank, separated by a space.
The priorities of the ranking methods are ordered as A > C > M > E. Hence if there are two or more ways for a student to obtain the same best rank, output the one with the highest priority.
If a student is not on the grading list, simply output N/A.
Sample Input:
5 6 310101 98 85 88 310102 70 95 88 310103 82 87 94 310104 91 91 91 310105 85 90 90 310101 310102 310103 310104 310105 999999
结尾无空行
Sample Output:
1 C 1 M 1 E 1 A 3 A N/A
结尾无空行
#include <iostream>#include <vector>#include <algorithm>#include <cmath>#include <unordered_map>using namespace std;unordered_map<string, vector<int>> grades;vector<int> q[4];// q0 A, q1 C, q2 M，q3 E//二分法，求排名int get_rank(vector<int>& a, int x){int l = 0, r= a.size() -1;while(l < r){int mid = l + r +1 >> 1;if(a[mid] <= x) l = mid;else r = mid -1;}return a.size() -r;}int main(){int n, m;cin >> n >> m;for(int i = 0; i < n; i ++){string id;cin >> id;int t[4] = {0};for( int j = 1; j < 4; j ++){cin >> t[j];t[0] += t[j];}t[0] = round(t[0]/ 3.0);//存入vectorfor( int j =0; j < 4; j ++){q[j].push_back(t[j]);grades[id].push_back(t[j]);}}for(int i =0; i < 4; i ++) sort(q[i].begin(),q[i].end());char names[] = "ACME";while(m --){string id;cin >> id;if(grades.count(id) == 0) puts("N/A");else{int res = n + 1;char c;for(int i =0; i < 4; i ++){int rank = get_rank(q[i], grades[id][i]);if(rank < res){res = rank;c = names[i];}}cout << res << ' ' << c << endl;}}}
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 (≤104) 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; 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结尾无空行
#include <iostream>#include <algorithm>#include <vector>#include <set>#include <sstream>using namespace std;//创建book的struct，比较特殊的是keyword用set存struct Book{string id, name, author;set<string> keyword;string publisher, year;};int main(){int n, m;cin >> n;vector<Book> books;while(n --){string id, name, author;cin >> id;getchar();getline(cin, name), getline(cin, author);//sstream读入keyword的setstring line;getline(cin, line);stringstream ssin(line);string keyword;set<string> keywords;while(ssin >> keyword) keywords.insert(keyword);string publisher, year;getline(cin, publisher);cin >> year;books.push_back({id, name, author, keywords, publisher, year});}cin >> m;getchar();string line;while( m --){getline(cin, line);cout << line << endl;string info = line.substr(3);char t = line[0];vector<string> res;if( t == '1' ){for(auto& book : books){if (book.name == info)res.push_back(book.id);}}else if( t == '2' ) {for(auto& book : books){if (book.author == info)res.push_back(book.id);}}else if( t == '3' ){for(auto& book : books){if (book.keyword.count(info))res.push_back(book.id);}}else if( t == '4'){for( auto& book : books){if(book.publisher == info)res.push_back(book.id);}}else{for( auto& book : books){if(book.year == info){res.push_back(book.id);}}}if(res.empty()) puts("Not Found");else{sort(res.begin(), res.end());for( auto id : res) cout << id << endl;}}return 0;}
主要是该怎么存book的信息，代码都是重复代码
1025 PAT Ranking (25 分)
Programming Ability Test (PAT) is organized by the College of Computer Science and Technology of Zhejiang University. Each test is supposed to run simultaneously in several places, and the ranklists will be merged immediately after the test. Now it is your job to write a program to correctly merge all the ranklists and generate the final rank.
Input Specification:
Each input file contains one test case. For each case, the first line contains a positive number N (≤100), the number of test locations. Then N ranklists follow, each starts with a line containing a positive integer K (≤300), the number of testees, and then K lines containing the registration number (a 13-digit number) and the total score of each testee. All the numbers in a line are separated by a space.
Output Specification:
For each test case, first print in one line the total number of testees. Then print the final ranklist in the following format:
registrationnumber final_rank location_number local_rank
The locations are numbered from 1 to _N. The output must be sorted in nondecreasing order of the final ranks. The testees with the same score must have the same rank, and the output must be sorted in nondecreasing order of their registration numbers.
Sample Input:
2 5 1234567890001 95 1234567890005 100 1234567890003 95 1234567890002 77 1234567890004 85 4 1234567890013 65 1234567890011 25 1234567890014 100 1234567890012 85结尾无空行
Sample Output:
9 1234567890005 1 1 1 1234567890014 1 2 1 1234567890001 3 1 2 1234567890003 3 1 2 1234567890004 5 1 4 1234567890012 5 2 2 1234567890002 7 1 5 1234567890013 8 2 3 1234567890011 9 2 4结尾无空行
#include <iostream>#include <vector>#include <algorithm>using namespace std;const int N = 110;struct Student{string id;int grade;int location_number,local_rank, final_rank;//成绩升序，id降序bool operator< (const Student& t) const{if(grade != t.grade) return grade > t.grade;return id < t.id;}};vector<Student> grades[N];vector<Student> all;int main(){int n;cin >> n;for( int i = 1; i <= n; i ++){int k;cin >> k;for(int j = 0; j < k; j ++ ){string id;int grade;cin >> id >> grade;grades[i].push_back({id, grade, i});}//取gauto& g =grades[i];sort(g.begin(), g.end());for( int j = 0;j < g.size(); j ++){if(!j || g[j].grade != g[j-1].grade) g[j].local_rank = j + 1;else g[j].local_rank = g[j-1].local_rank;all.push_back(g[j]);}}sort(all.begin(), all.end());for (int i = 0; i < all.size(); i ++){if(!i || all[i].grade != all[i-1].grade) all[i].final_rank = i + 1;else all[i].final_rank = all[i-1].final_rank;}cout << all.size() << endl;for (auto& s: all){cout << s.id << ' ' << s.final_rank <<' ' << s.location_number;cout <<' '<< s.local_rank << endl;}}
1028 List Sorting (25 分)
Excel can sort records according to any column. Now you are supposed to imitate this function.
Input Specification:
Each input file contains one test case. For each case, the first line contains two integers N (≤105) and C, where N is the number of records and C is the column that you are supposed to sort the records with. Then N lines follow, each contains a record of a student. A student’s record consists of his or her distinct ID (a 6-digit number), name (a string with no more than 8 characters without space), and grade (an integer between 0 and 100, inclusive).
Output Specification:
For each test case, output the sorting result in N lines. That is, if C = 1 then the records must be sorted in increasing order according to ID’s; if C = 2 then the records must be sorted in non-decreasing order according to names; and if C = 3 then the records must be sorted in non-decreasing order according to grades. If there are several students who have the same name or grade, they must be sorted according to their ID’s in increasing order.
Sample Input 1:
3 1 000007 James 85 000010 Amy 90 000001 Zoe 60
Sample Output 1:
000001 Zoe 60 000007 James 85 000010 Amy 90
Sample Input 2:
4 2 000007 James 85 000010 Amy 90 000001 Zoe 60 000002 James 98
Sample Output 2:
000010 Amy 90 000002 James 98 000007 James 85 000001 Zoe 60
Sample Input 3:
4 3 000007 James 85 000010 Amy 90 000001 Zoe 60 000002 James 9
Sample Output 3:
000002 James 9 000001 Zoe 60 000007 James 85 000010 Amy 90
鸣谢用户 wangzhj 补充数据！
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n;
//建立row的结构体
struct Row{
string id, name;
int grade;
}rows[N];
//定义三种排序方式
bool cmp1(Row a, Row b){
return a.id < b.id;
}
bool cmp2(Row a, Row b){
if (a.name != b.name) return a.name < b.name;
return a.id < b.id;
}
bool cmp3(Row a, Row b){
if(a.grade != b.grade) return a.grade < b.grade;
return a.id < b.id;
}
int main(){
int c;
scanf("%d%d", &n, &c);
char id[10], name[10];
for (int i = 0; i < n; i ++){
int grade;
scanf("%s%s%d",id, name, &grade);
rows[i] = {id, name ,grade};
}
if ( c == 1) sort(rows, rows+n, cmp1);
else if ( c == 2) sort(rows, rows+n, cmp2);
else sort(rows, rows + n, cmp3);
for (int i = 0; i < n; i ++){
printf("%s %s %d\n",rows[i].id.c_str(), rows[i].name.c_str(), rows[i].grade);
}
return 0;
}
1039 Course List for Student (25 分)
Zhejiang University has 40000 students and provides 2500 courses. Now given the student name lists of all the courses, you are supposed to output the registered course list for each student who comes for a query.
Input Specification:
Each input file contains one test case. For each case, the first line contains 2 positive integers: N (≤40,000), the number of students who look for their course lists, and K (≤2,500), the total number of courses. Then the student name lists are given for the courses (numbered from 1 to K) in the following format: for each course i, first the course index i and the number of registered students Ni (≤200) are given in a line. Then in the next line, Ni student names are given. A student name consists of 3 capital English letters plus a one-digit number. Finally the last line contains the N names of students who come for a query. All the names and numbers in a line are separated by a space.
Output Specification:
For each test case, print your results in N lines. Each line corresponds to one student, in the following format: first print the student’s name, then the total number of registered courses of that student, and finally the indices of the courses in increasing order. The query results must be printed in the same order as input. All the data in a line must be separated by a space, with no extra space at the end of the line.
Sample Input:
11 5 4 7 BOB5 DON2 FRA8 JAY9 KAT3 LOR6 ZOE1 1 4 ANN0 BOB5 JAY9 LOR6 2 7 ANN0 BOB5 FRA8 JAY9 JOE4 KAT3 LOR6 3 1 BOB5 5 9 AMY7 ANN0 BOB5 DON2 FRA8 JAY9 KAT3 LOR6 ZOE1 ZOE1 ANN0 BOB5 JOE4 JAY9 FRA8 DON2 AMY7 KAT3 LOR6 NON9结尾无空行
Sample Output:
ZOE1 2 4 5 ANN0 3 1 2 5 BOB5 5 1 2 3 4 5 JOE4 1 2 JAY9 4 1 2 4 5 FRA8 3 2 4 5 DON2 2 4 5 AMY7 1 5 KAT3 3 2 4 5 LOR6 4 1 2 4 5 NON9 0结尾无空行
#include <iostream>
#include <unordered_map>
#include <algorithm>
#include <vector>
using namespace std;
unordered_map<string, vector<int>> students;
int main(){
int n, k;
cin >> n >> k;
while( k --){
int id, m;
cin >> id >> m;
while( m --){
string name;
cin >> name;
students[name].push_back(id);
}
}
while( n --){
string name;
cin >> name;
auto& ls = students[name];
cout << name <<' ' << ls.size();
sort(ls.begin(), ls.end());
for(auto l : ls) cout << ' ' << l;
cout << endl;
}
}
1052 Linked List Sorting (25 分)
A linked list consists of a series of structures, which are not necessarily adjacent in memory. We assume that each structure contains an integer key and a Next pointer to the next structure. Now given a linked list, you are supposed to sort the structures according to their key values in increasing order.
Input Specification:
Each input file contains one test case. For each case, the first line contains a positive N (<105) and an address of the head node, where _N_ is the total number of nodes in memory and the address of a node is a 5-digit positive integer. NULL is represented by −1.
Then N lines follow, each describes a node in the format:
Address Key Next
where Address is the address of the node in memory, Key is an integer in [−105,105], and Next is the address of the next node. It is guaranteed that all the keys are distinct and there is no cycle in the linked list starting from the head node.
Output Specification:
For each test case, the output format is the same as that of the input, where N is the total number of nodes in the list and all the nodes must be sorted order.
Sample Input:
5 00001 11111 100 -1 00001 0 22222 33333 100000 11111 12345 -1 33333 22222 1000 12345结尾无空行
Sample Output:
5 12345 12345 -1 00001 00001 0 11111 11111 100 22222 22222 1000 33333 33333 100000 -1结尾无空行
#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_map>
using namespace std;
//定义node
struct Node{
string address;
int key;
string next;
bool operator< (const Node& t) const{
return key < t.key;
}
};
int main(){
int n;
char head[10];
scanf("%d%s", &n, head);
//用哈希表存nodes
unordered_map<string, Node>map;
char address[10], next[10];
while (n --){
int key;
scanf("%s%d%s",address, &key, next);
map[address] = {address, key, next};
}
//把整个链表找出放入vector,next是下一个节点的地址
vector<Node> nodes;
for( string i = head; i != "-1"; i = map[i].next ){
nodes.push_back(map[i]);
}
printf("%d ",nodes.size());
if(nodes.empty()) puts("-1");
else{
sort(nodes.begin(), nodes.end());
printf("%s\n",. nodes[0].address.c_str());
for (int i =0; i < nodes.size(); i ++ ){
if(i + 1 == nodes.size() ){
printf("%s %d -1\n",nodes[i].address.c_str(), nodes[i].key);
}else{
printf("%s %d %s\n",nodes[i].address.c_str(), nodes[i].key, nodes[i + 1].address.c_str());
}
}
}
}
地址五位数，用字符串保存，存入数组，sort排序
如果需要练习链表排序，acw有单链表快排 acw1451
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <vector>
using namespace std;
const int K = 6;
int n, k, m;
int p_score[K];
struct Student{
string id;
int grade[K];
int total, cnt; //cnt 满分成绩的状态
//学生初始化
Student(){}
Student(string _id) : id(_id){
for (int i = 1; i <=k ; i ++) grade[i] = -2;//所有题目初始化为-2, 没有提交过
total = cnt = 0;
}
//定义计算的函数
void calc(){
for (int i = 1; i <= k; i ++){
total += max(0, grade[i]);// grade在-1， -2情况下不会倒扣分，所以和0一起取max
if (grade[i] == p_score[i]) cnt ++;// 计算满分的数量
}
}
//判断同学有没有提交过
bool has_submit(){
for (int i =1; i <= k; i ++){
if(grade[i] >= 0) return true;
}
return false;
}
//按照分数排序， 按照满分题目数量排序， id小的排在前面
bool operator< (const Student& t) const{
if (total != t.total) return total > t.total;
if (cnt != t.cnt) return cnt > t.cnt;
return id < t.id;
}
};
int main(){
//哈希表存储所有的student
unordered_map<string, Student> students;
scanf("%d%d%d", &n, &k, &m);
for (int i = 1; i <= k; i ++) cin >> p_score[i];
while (m --){
string u_id;//学生id
char u_id_s[6];
int p_id, grade; //题目的id和得分
scanf("%s %d %d", u_id_s, &p_id, &grade);
u_id = u_id_s;
//学生没出现过，要进行初始化
if (students.count(u_id) == 0 ) {
students[u_id] = Student(u_id);
}
//学生的分数加进来
students[u_id].grade[p_id] = max(students[u_id].grade[p_id], grade);
}
vector<Student> res;
//算分数，遍历所有同学
for (auto& item : students){
auto& s= item.second;
if (s.has_submit()){
s.calc();
res.push_back(s);
}
}
sort(res.begin(), res.end());
//定义rank
for (int i = 0, rank =1; i < res.size(); i ++){
if ( i && res[i].total != res[i -1].total) rank = i + 1;
printf("%d %s %d", rank, res[i].id.c_str(), res[i].total);
// 输出各科成绩
for ( int j = 1; j <= k; j ++){
if (res[i].grade[j] == -2) printf(" -");
else printf(" %d", max(0, res[i].grade[j]));
}
puts("");
}
return 0;
}
从未提交过 -2
提交了但未编译通过 -1
编译通过 >= 0
id其实是字符串，用哈希表进行映射
若有收获，就点个赞吧
0 人点赞
