第1章 字符串处理
1001. A+B Format
笔记
- 用字符串处理
- 用
to_string()把int转成字符串string - 字符串头插
res = ch + res;
#include<iostream>
using namespace std;
int main() {
int a, b;
cin >> a >> b;
string c = to_string(a + b);
string res;
for (int i = c.size() - 1, j = 0; i >= 0; i--) {
res = c[i] + res;
j++;
if (j % 3 == 0 && i && c[i - 1] != '-') res = "," + res;
}
cout << res << endl;
return 0;
}
1005. Spell It Right
笔记
- 用
char数组代替switch语句块 - 为了避免输出末尾多空格，可以先输出第1个，然后再输出其余部分
#include <iostream>
using namespace std;
int main() {
string n;
cin >> n;
int sum = 0;
for (auto ch : n) sum += ch - '0';
char words[10][10] = {
"zero", "one", "two", "three", "four",
"five", "six", "seven", "eight", "nine"
};
string res = to_string(sum);
cout << words[res[0] - '0']; // 避免末尾空格
for (int i = 1; i < res.size(); i ++)
cout << " " << words[res[i] - '0'];
return 0;
}
1006. Sign In and Sign Out
笔记
- 用
!i || condition实现首次读入数据时先保存，之后读入时再比较，前提是for从0开始 - 题目本质是找进门最早的ID和出门最晚的ID，没必要存储所有数据
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
string id, in_time, out_time;
string open_id, open_time, close_id, close_time;
for (int i = 0; i < n; i++) {
cin >> id >> in_time >> out_time;
if (!i || in_time < open_time) {
open_id = id;
open_time = in_time;
}
if (!i || out_time > close_time) {
close_id = id;
close_time = out_time;
}
}
cout << open_id << " " << close_id;
return 0;
}
1035. Password
#include <iostream>
using namespace std;
const int N = 1010;
string names[N], pwds[N];
string convert(string s) {
string res = "";
for (auto c : s)
if (c == '1') res += '@';
else if (c == '0') res += '%';
else if (c == 'l') res += 'L';
else if (c == 'O') res += 'o';
else res += c;
return res;
}
int main() {
int n, m, k = 0;
cin >> n;
m = n;
string name, pwd;
while(m--) {
cin >> name >> pwd;
string change = convert(pwd);
if (change != pwd) {
names[k] = name;
pwds[k] = change;
k++;
}
}
if (k == 0) {
if (n == 1) printf("There is 1 account and no account is modified");
else printf("There are %d accounts and no account is modified", n);
} else {
cout << k << endl;
for (int i = 0; i < k; i++) cout << names[i] << " " << pwds[i] << endl;
}
return 0;
}
1036. Boys vs Girls
#include <iostream>
using namespace std;
const int N = 102;
int main() {
string name, sex, id;
int n, score;
cin >> n;
string girl_name, girl_id, boy_name, boy_id;
int girl_score = -1, boy_score = -1;
while(n--) {
cin >> name >> sex >> id >> score;
if (sex == "M" && (boy_score == -1 || score < boy_score)) {
boy_name = name;
boy_id = id;
boy_score = score;
} else if (sex == "F" && (girl_score == -1 || score > girl_score)) {
girl_name = name;
girl_id = id;
girl_score = score;
}
}
if (girl_score != -1) cout << girl_name << " " << girl_id << endl;
else puts("Absent");
if (boy_score != -1) cout << boy_name << " " << boy_id << endl;
else puts("Absent");
if (girl_score == -1 || boy_score == -1) puts("NA");
else cout << girl_score - boy_score;
return 0;
}
1050. String Subtraction
笔记
- 用
getline(cin, s)读入包含空格的字符串 - 用哈希表
unordered_set加快查找
#include <iostream>
#include <unordered_set>
using namespace std;
int main() {
string s1, s2;
getline(cin, s1);
getline(cin, s2);
unordered_set<char> h;
for (auto c : s2)
h.insert(c);
string res = "";
for (auto c : s1)
if (!h.count(c))
res += c;
cout << res << endl;
return 0;
}
1071. Speech Patterns
笔记
- 用哈希表统计次数
- 注意怎么用条件表示多关键字比较（统计次数降序，单词字典序）
#include <iostream>
#include <unordered_map>
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() {
unordered_map<string, int> hash;
string s;
getline(cin, s);
for (int i = 0; i < s.size(); i++)
if (check(s[i])) {
string word;
int j = i;
while(j < s.size() && check(s[j]))
word += tolower(s[j++]);
hash[word]++;
i = j;
}
string max_word;
int max_times = -1;
for (auto item : hash)
if (item.second > max_times
|| item.second == max_times && item.first < max_word) {
// 多关键字比较（出现次数，单词字典序）
max_times = item.second;
max_word = item.first;
}
cout << max_word << " " << max_times;
return 0;
}
1061. Dating
笔记
- 注意条件不仅要满足是大写字母，而且还是指定范围内的大写字母，例如
A~G，A~N
#include <iostream>
using namespace std;
int main() {
string s1, s2, s3, s4;
cin >> s1 >> s2 >> s3 >> s4;
string weekdays[7] = {"MON", "TUE", "WED", "THU", "FRI", "SAT", "SUN"};
int i;
for (i = 0; i < s1.size() && i < s2.size(); i++)
if (s1[i] == s2[i] && s1[i] >= 'A' && s1[i] <= 'G') {
cout << weekdays[s1[i] - 'A'];
break;
}
for (i = i + 1; i < s1.size() && i < s2.size(); i++)
if (s1[i] == s2[i]) {
if (s1[i] >= '0' && s1[i] <= '9') {
printf(" %02d:", s1[i] - '0');
break;
} else if (s1[i] >= 'A' && s1[i] <= 'N') {
printf(" %02d:", 10 + s1[i] - 'A');
break;
}
}
for (i = 0; i < s3.size() && i < s4.size(); i++)
if (s3[i] == s4[i] &&
(s3[i] >= 'a' && s3[i] <= 'z' || s3[i] >= 'A' && s3[i] <= 'Z')) {
printf("%02d", i);
break;
}
return 0;
}
1016. Phone Bills
笔记
- 在用
for each遍历map时，返回的迭代次序是按key升序排序的，对于string类型的key，顺序指的是ASCII顺序，因此在用map的key保存人名后，迭代次序就是题目要求的次序 - 如果每次都用
for按时间段计算费用，时间开销很大，可采用前缀和保存前i分钟的费用，i<=1440。在这用sum[t2] - sum[t1]计算时间，而不是sum[t2] - sum[t1 - 1] - 在用
printf("%s", s)输出string类型的变量时，需要用c_str()转换成char数组 - 当一个客户存在合法的通话时，才输出这个人的账单，这个在代码逻辑里体现为
if(!total) char数组能自动转成string
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
const int N = 24, M = 30 * 1440 + 10;
int cost[N]; // 时段价格
double sum[M]; // 前缀和
struct Record {
int minutes; // time
string state; // on-line = true, off-line = false
string format_time; // format time for output
bool operator<(const Record& p) const{
return minutes < p.minutes;
}
};
map<string, vector<Record>> persons;
int main() {
// 读入每个时段的价格
for (int i = 0; i < N; i++)
cin >> cost[i];
// 计算价格前缀和（分钟）
for (int i = 1; i < M; i++)
sum[i] = sum[i - 1] + cost[(i - 1) % 1440 / 60] / 100.0; // 分转化成元
// 读入通话记录
int n;
cin >> n;
char name[30], state[10], format_time[20];
int month, day, hour, minute;
while (n--) {
scanf("%s %d:%d:%d:%d %s", name, &month, &day, &hour, &minute, state);
int minutes = (day - 1) * 1440 + hour * 60 + minute;
sprintf(format_time, "%02d:%02d:%02d", day, hour, minute);
persons[name].push_back({minutes, state, format_time});
}
// 输出账单
for (auto &person : persons) {
string name = person.first;
auto records = person.second;
sort(records.begin(), records.end()); // sort by time
double total = 0;
for (int i = 0; i < records.size() - 1; i++) {
if (records[i].state == "on-line" && records[i + 1].state == "off-line") {
if (!total) printf("%s %02d\n", name.c_str(), month);
cout << records[i].format_time << " " << records[i + 1].format_time;
int d = records[i + 1].minutes - records[i].minutes;
double c = sum[records[i + 1].minutes] - sum[records[i].minutes];
printf(" %d $%.2f\n", d, c);
total += c;
}
}
if (total) printf("Total amount: $%.2f\n", total);
}
return 0;
}
1017. Queueing at Bank
笔记
- 用小根堆（优先队列）模拟窗口服务，其值表示可服务的时刻，初值为上班开始时间，若用秒表示，则为
8 * 3600 - 让所有用户按到达时间升序排序，然后每次从小根堆弹出一个可服务时刻最小的窗口，然后更新改窗口的下次服务时刻，放入小根堆中，如此反复
- 按到达时间排序后，可根据到达时间剪枝
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 1e4 + 10;
struct Person{
int arrive_time; // 到达时间（秒）
int service_time; // 服务时间（秒）
bool operator<(const Person& person) const {
return arrive_time < person.arrive_time;
}
} persons[N];
int main() {
int n, k;
cin >> n >> k;
int hour, minute, second, service_time;
for (int i = 0; i < n; i++) {
scanf("%d:%d:%d %d", &hour, &minute, &second, &service_time);
int arrive_time = hour * 3600 + minute * 60 + second;
service_time = min(service_time, 60); // 服务不超过60分钟
persons[i] = {arrive_time, service_time * 60}; // 用秒表示
}
sort(persons, persons + n); // 按到达时间排序
priority_queue<int, vector<int>, greater<int>> windows; // 小根堆
for (int i = 0; i < k; i++)
windows.push(8 * 3600); // work at 8:00
int total = 0, cnt = 0;
for (int i = 0; i < n; i++) {
int w = windows.top();
windows.pop();
if (persons[i].arrive_time > 17 * 3600) break; // 后边全都来晚了
int start_time = max(persons[i].arrive_time, w);
total += start_time - persons[i].arrive_time;
cnt++;
windows.push(start_time + persons[i].service_time);
}
printf("%.1lf\n", (double)total / cnt / 60); // 分钟
return 0;
}
1026. Table Tennis
笔记
- 核心思路
- 让vip和普通会员分开排队，如果存在可用vip桌子，且存在vip排队（这里指到vip到达时间小于vip桌子的可用时刻），则先把vip分配到vip桌子
- 如果不存在vip桌子，则所有人都看成普通人；如果不存在vip排队，则所有桌子都看成普通桌子。综上当不存在vip桌子或没有vip排队时，就不存在特权情况，但由于桌子是按vip分开记录的，因此需要比较vip桌子和普通桌子哪个的可用时刻更近一些。
- 为了加快查找，用小根堆保存所有人和桌子，并按vip分开保存
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cmath>
using namespace std;
const int M = 110, INF = 2E9;
int n, k, m;
struct Person {
int arrive_time, play_time;
int start_time, waiting_time;
bool operator< (const Person& person) const{
if (start_time != person.start_time)
return start_time < person.start_time;
else
return arrive_time < person.arrive_time;
}
bool operator> (const Person& person) const{
return arrive_time > person.arrive_time;
}
};
struct Table {
int id;
int end_time;
bool operator> (const Table& table) const{
if (end_time != table.end_time) return end_time > table.end_time;
else return id > table.id;
}
};
bool is_vip_table[M];
int table_cnt[M];
vector<Person> all_persons;
void assign(priority_queue<Person, vector<Person>, greater<Person>>& persons,
priority_queue<Table, vector<Table>, greater<Table>>& tables) {
Person person = persons.top();
persons.pop();
Table table = tables.top();
tables.pop();
person.start_time = table.end_time;
person.waiting_time = round((table.end_time - person.arrive_time) / 60.0); // 化成分钟
table.end_time = table.end_time + person.play_time;
table_cnt[table.id]++;
tables.push(table);
all_persons.push_back(person);
}
string get_time(int secs) {
char res[20];
sprintf(res, "%02d:%02d:%02d", secs / 3600, (secs % 3600) / 60, secs % 60);
return res;
}
int main() {
priority_queue<Person, vector<Person>, greater<Person>> vip_persons, normal_persons;
priority_queue<Table, vector<Table>, greater<Table>> vip_tables, normal_tables;
vip_persons.push({INF});
normal_persons.push({INF});
vip_tables.push({-1, INF});
normal_tables.push({-1, INF});
cin >> n;
int hour, minute, sec, play_time, is_vip;
for (int i = 0; i < n; i++) {
scanf("%d:%d:%d %d %d", &hour, &minute, &sec, &play_time, &is_vip);
int arrive_time = hour * 3600 + minute * 60 + sec;
play_time = min(play_time, 120);
play_time *= 60; // 转换成秒
if (is_vip) vip_persons.push({arrive_time, play_time});
else normal_persons.push({arrive_time, play_time});
}
cin >> k >> m;
int id;
for (int i = 0; i < m; i++) {
cin >> id;
is_vip_table[id] = true;
}
for (int i = 1; i <= k; i++)
if (is_vip_table[i]) vip_tables.push({i, 8 * 3600});
else normal_tables.push({i, 8 * 3600});
while (normal_persons.size() > 1 || vip_persons.size() > 1) {
Person np = normal_persons.top();
Person vp = vip_persons.top();
int arrive_time = min(np.arrive_time, vp.arrive_time);
// 更新桌子时间
while(normal_tables.top().end_time < arrive_time) {
Table nt = normal_tables.top();
normal_tables.pop();
nt.end_time = arrive_time;
normal_tables.push(nt);
}
while(vip_tables.top().end_time < arrive_time) {
Table vt = vip_tables.top();
vip_tables.pop();
vt.end_time = arrive_time;
vip_tables.push(vt);
}
// 分配
Table nt = normal_tables.top();
Table vt = vip_tables.top();
int end_time = min(nt.end_time, vt.end_time);
if (end_time >= 21 * 3600) break; // 超过下班时间
if (vp.arrive_time <= end_time && vt.end_time == end_time)
assign(vip_persons, vip_tables);
else if (np.arrive_time < vp.arrive_time) {
if (nt > vt) assign(normal_persons, vip_tables);
else assign(normal_persons, normal_tables);
} else {
if (nt > vt) assign(vip_persons, vip_tables);
else assign(vip_persons, normal_tables);
}
}
sort(all_persons.begin(), all_persons.end());
for (auto person : all_persons) {
cout << get_time(person.arrive_time) << " ";
cout << get_time(person.start_time) << " ";
cout << person.waiting_time << endl;
}
cout << table_cnt[1];
for (int i = 2; i <= k; i++)
cout << " " << table_cnt[i];
cout << endl;
return 0;
}
1060. Are They Equal
笔记
- 根据小数点所在下标确定题目规定格式的指数初值（如果是纯整数，则在末尾补小数点，转化成相同问题）
- 去掉前导零，调整初值
- 补上其它信息
0.、*10^即可转换成题目要求的格式
#include <iostream>
using namespace std;
string change(string a, int n) {
int k = a.find('.'); // 指数
if (k == -1) {
a += '.'; // 整数末尾补小数点
k = a.find('.');
}
a = a.substr(0, k) + a.substr(k + 1); // 去掉小数点
// 去掉前导0
while(a.size() && a[0] == '0') {
a = a.substr(1);
k--;
}
if (a.empty()) k = 0; // 规定0的指数为0
if (a.size() > n) a = a.substr(0, n); // 保留n位
else if (a.size() < n) a += string(n - a.size(), '0'); // 末尾补0
return "0." + a + "*10^" + to_string(k);
}
int main() {
int n;
string a, b;
cin >> n >> a >> b;
a = change(a, n);
b = change(b, n);
if (a == b) cout << "YES " << a << endl;
else cout << "NO " << a << ' ' << b << endl;
return 0;
}
1073. Scientific Notation
笔记
- 根据题目规定的科学计数法格式，可以发现小数部分一定位于下标$1$ ~ $k - 1$，其中$k$是字符
E所在的下标，然后指数部分就是a.substr(k + 1)，这样就能分离小数部分和整数部分 - 指数部分可以通过
stoi转换成整数，记为$b$，分类讨论- 当$b \leqslant 0$时，向左补$-(b + 1)$个$0$
- 当$b \gt a.\text{size()}$时，即超出小数部分的精度范围且指数是正数，则向右补$b - a.\text{size()}$个$0$
- 当$0 \lt b \leqslant a.\text{size()}$时，在小数部分$a$的第$b+1$个位置插入小数点
#include <iostream>
#include <cstring>
using namespace std;
int main() {
string a;
cin >> a;
if (a[0] == '-') cout << '-';
int k = a.find("E");
string b = a[1] + a.substr(3, k - 3); // substr(int begin, int length)
int c = stoi(a.substr(k + 1)); // 指数部分
c += 1; // 修正
// cout << b << ' ' << c << endl;
if (c <= 0) b = "0." + string(-c, '0') + b;
else if (c >= b.size()) b += string(c - b.size(), '0');
else b = b.substr(0, c) + '.' + b.substr(c);
cout << b << endl;
return 0;
}
1077. Kuchiguse
笔记
- 求最长公共后缀，直接从后向前穷举即可
- 注意读入$n$后，需要清掉换行符，否则
getline(cin, s)会读入该换行符，导致读入数据不对
#include <iostream>
#include <cstring>
using namespace std;
const int N = 102;
string s[N];
int main() {
int n;
cin >> n;
getchar(); // 清掉换行符
for (int i = 0; i < n; i++)
getline(cin, s[i]);
bool flag = true;
int k = 1;
while(flag) {
char c = s[0][s[0].size() - k];
for (int i = 1; i < n; i++)
if (k > s[i].size() || s[i][s[i].size() - k] != c) {
flag = false;
break;
}
if (!flag) {
if (k == 1) puts("nai");
else cout << s[0].substr(s[0].size() - k + 1) << endl;
}
k++;
}
return 0;
}
1082. Read Number in Chinese
笔记
-
分两个层次
- 每4位转换，即亿和万
- 4位内转换，即千百十
-
如果当前位非0，且上一位是0，则要先输出1个0
- 如果当前是最高位且有前导0，则去掉前导0
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
int b[4], c[3];
vector<string> ans;
string num[10] = {"ling", "yi", "er", "san", "si",
"wu", "liu", "qi", "ba", "jiu"};
string name1[4] = {"", "Shi", "Bai", "Qian"};
string name2[4] = {"", "Wan", "Yi"};
void inner(int x, bool is_high) {
// 小于10000的数
vector<string> res;
if (x == 0) res.push_back(num[0]);
else {
for (int i = 0; i < 4; i++) {
b[i] = x % 10;
x /= 10;
}
for (int i = 3; i >= 0; i--)
if (b[i]) {
if (i < 3 && b[i + 1] == 0)
res.push_back(num[0]);
res.push_back(num[b[i]]);
if (i > 0) res.push_back(name1[i]);
}
}
int i = 0;
if (is_high && res[0] == num[0]) i = 1; // 跳过最前的0
while(i < res.size())
ans.push_back(res[i++]);
}
void outer(int x) {
if (x == 0) ans.push_back(num[0]);
else {
for (int i = 0; i < 3; i++) {
c[i] = x % 10000;
x /= 10000;
}
bool is_first = true;
for (int i = 2; i >= 0; i--)
if (c[i]) {
if (i < 2 && c[i + 1] == 0 && !is_first)
ans.push_back(num[0]);
inner(c[i], is_first);
if (i > 0) ans.push_back(name2[i]);
is_first = false;
}
}
}
void print() {
cout << ans[0];
for (int i = 1; i < ans.size(); i++) {
if (ans[i] == num[0] && ans[i] == ans[i - 1])
continue; // 连续两个0，跳过
cout << ' ' << ans[i];
}
cout << endl;
}
int main() {
int n;
cin >> n;
if (n < 0) {
cout << "Fu ";
n = -n;
}
outer(n);
print();
return 0;
}
1084. Broken Keyboard
笔记
- 因为
char字符至多有256个，因此可用大小为256的bool数组记录键盘坏的情况 - 在比较之前可以先用
toupper转成大写 - 实际键入的字符串不会超过应该键入的字符串，遍历时可能会出现应该键入的字符串未遍历完，但实际键入的字符串已遍历完，可通过在实际键入的字符串末尾加上一个实际键入字符串中不会存在的字符来避免对比终止
#include <iostream>
#include <cstring>
using namespace std;
string a, b, res;
bool st[256]; // 至多256个ASCII字符，true表示损坏
int main() {
cin >> a >> b;
b += "#"; // 加入一个a一定没有的字符，避免b已经到末尾，但a还没到
for (int i = 0, j = 0; i < a.size(); i++) {
char p = toupper(a[i]), q = toupper(b[j]);
if (p == q) j++;
else if (!st[p]) {
st[p] = true;
res += p;
}
}
cout << res << endl;
return 0;
}
1108. Finding Average
笔记
stof能尝试把字符串转成浮点数，若不能转换会抛出异常。但像1.23abc也会认为能转换，不过第2个参数能指出能转换到的位置，如果传入的第2个参数不等于字符串长度，说明存在上述错误的情况，应当视为不能转换成浮点数- 可用
try{ } catch(...) { }结构捕获异常，其中catch中的...表示任意异常
#include <iostream>
#include <cstring>
using namespace std;
int main() {
int n;
cin >> n;
int cnt = 0;
double sum = 0;
string x;
while(n--) {
cin >> x;
double y;
bool success = true;
try{
size_t index;
y = stof(x, &index); // 尝试转成浮点数
if (index < x.size())
success = false; // 末尾含有非法字符
} catch(...) {
success = false; // 转换失败
}
if (success) {
// 转换成功的情况下
if (y > 1000 || y < -1000) success = false; // 超出范围
else {
int k = x.find('.');
if (k != -1 && k < x.size() - 3)
success = false; // 超出两位精度
}
}
if (success) {
cnt++;
sum += y;
} else
printf("ERROR: %s is not a legal number\n", x.c_str());
}
if (cnt > 1)
printf("The average of %d numbers is %.2lf\n", cnt, sum / cnt);
else if (cnt == 1)
printf("The average of 1 number is %.2lf\n", sum);
else
puts("The average of 0 numbers is Undefined");
return 0;
}
1124. Raffle for Weibo Followers
笔记
- 模拟即可，可用哈希表加快查找
#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
const int N = 1010;
string name[N];
unordered_set<string> set;
vector<string> res;
int main() {
int n, k, s;
cin >> n >> k >> s;
for (int i = 1; i <= n; i++)
cin >> name[i];
int i = s;
while(i <= n) {
if (set.count(name[i]) == 0) {
set.insert(name[i]);
res.push_back(name[i]);
i += k;
} else i++;
}
if (res.size() == 0) puts("Keep going...");
else {
for (string s : res)
cout << s << endl;
}
return 0;
}
1141. PAT Ranking of Institutions
笔记
- 分别统计学校在顶级、甲级、乙级的得分，然后再统一计算就能避免浮点数精度问题
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <vector>
#include <cstring>
using namespace std;
struct school{
string name;
int cnt, score;
int t_score, a_score, b_score;
school(): cnt(0), score(0), t_score(0), a_score(0), b_score(0) {}
bool operator<(const school& s) const {
if (score != s.score)
return score > s.score;
else if (cnt != s.cnt)
return cnt < s.cnt;
else
return name < s.name;
}
};
unordered_map<string, school> h;
string lower(string s) {
for (auto& c : s)
c = tolower(c);
return s;
}
int main() {
int n;
cin >> n;
string name, sch;
int score;
while(n--) {
cin >> name >> score >> sch;
sch = lower(sch);
if (h.count(sch) == 0)
h[sch].name = sch;
if (name[0] == 'T') h[sch].t_score += score;
else if (name[0] == 'A') h[sch].a_score += score;
else h[sch].b_score += score;
h[sch].cnt++;
}
vector<school> res;
for (auto item : h) {
school s = item.second;
s.score = (int)s.t_score * 1.5 + s.a_score + s.b_score / 1.5;
res.push_back(s);
}
sort(res.begin(), res.end());
cout << res.size() << endl;
int rank = 1;
for (int i = 0; i < res.size(); i++) {
if (i && res[i].score != res[i - 1].score)
rank = i + 1;
cout << rank << ' ' << res[i].name << ' ' <<
res[i].score << ' ' << res[i].cnt << endl;
}
return 0;
}
1153. Decode Registration Card of PAT
笔记
- 模拟题，需要用
scanf和printf减少常数才能过
#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_map>
#include <cstring>
using namespace std;
const int N = 1e4 + 10;
int n, m;
struct student {
string id;
int score;
bool operator< (const student& s) const {
if (score != s.score)
return score > s.score;
else
return id < s.id;
}
// student(_id, _score): id(_id), score(_score) {}
} students[N];
struct place {
string id;
int num;
bool operator< (const place& p) const {
if (num != p.num)
return num > p.num;
else
return id < p.id;
}
place(): num(0) {}
};
int main() {
scanf("%d%d", &n, &m);
char s[14];
int score;
for (int i = 0; i < n; i++) {
scanf("%s%d", s, &score);
students[i] = {s, score};
}
int op;
char param[10];
for (int i = 1; i <= m; i++) {
scanf("%d%s", &op, param);
printf("Case %d: %d %s\n", i, op, param);
if (op == 1) {
vector<student> res;
for (int i = 0; i < n; i++)
if (students[i].id[0] == param[0])
res.push_back(students[i]);
sort(res.begin(), res.end());
if (res.empty()) printf("NA\n");
else {
for (auto stu : res)
printf("%s %d\n",stu.id.c_str(), stu.score);
}
} else if (op == 2) {
int cnt = 0, sum = 0;
for (int i = 0; i < n; i++)
if (students[i].id.substr(1, 3) == param) {
sum += students[i].score;
cnt++;
}
if (cnt == 0) printf("NA\n");
else printf("%d %d\n", cnt, sum);
} else {
unordered_map<string, place> h;
for (int i = 0; i < n; i++)
if (students[i].id.substr(4, 6) == param) {
string p_id = students[i].id.substr(1, 3);
if (h.count(p_id) == 0) h[p_id].id = p_id;
h[p_id].num++;
}
vector<place> res;
for (auto item : h)
res.push_back(item.second);
sort(res.begin(), res.end());
if (res.empty()) printf("NA\n");
else {
for (auto p : res)
printf("%s %d\n", p.id.c_str(), p.num);
}
}
}
return 0;
}
哇好厉害
过奖了哈哈