liuchuo – 第25页 – 我不管，反正我最萌～

1095 解码PAT准考证（25 point(s)） – PAT乙级真题

PAT 准考证号由 4 部分组成：
第 1 位是级别，即 T 代表顶级；A 代表甲级；B 代表乙级；
第 2~4 位是考场编号，范围从 101 到 999；
第 5~10 位是考试日期，格式为年、月、日顺次各占 2 位；
最后 11~13 位是考生编号，范围从 000 到 999。
现给定一系列考生的准考证号和他们的成绩，请你按照要求输出各种统计信息。

输入格式：
输入首先在一行中给出两个正整数 N（≤10⁴ ）和 M（≤100），分别为考生人数和统计要求的个数。

接下来 N 行，每行给出一个考生的准考证号和其分数（在区间 [0,100] 内的整数），其间以空格分隔。

考生信息之后，再给出 M 行，每行给出一个统计要求，格式为：类型指令，其中

类型为 1 表示要求按分数非升序输出某个指定级别的考生的成绩，对应的指令则给出代表指定级别的字母；
类型为 2 表示要求将某指定考场的考生人数和总分统计输出，对应的指令则给出指定考场的编号；
类型为 3 表示要求将某指定日期的考生人数分考场统计输出，对应的指令则给出指定日期，格式与准考证上日期相同。
输出格式：
对每项统计要求，首先在一行中输出 Case #: 要求，其中 # 是该项要求的编号，从 1 开始；要求即复制输入给出的要求。随后输出相应的统计结果：

类型为 1 的指令，输出格式与输入的考生信息格式相同，即准考证号成绩。对于分数并列的考生，按其准考证号的字典序递增输出（题目保证无重复准考证号）；
类型为 2 的指令，按人数总分的格式输出；
类型为 3 的指令，输出按人数非递增顺序，格式为考场编号总人数。若人数并列则按考场编号递增顺序输出。
如果查询结果为空，则输出 NA。

输入样例：
8 4
B123180908127 99
B102180908003 86
A112180318002 98
T107150310127 62
A107180908108 100
T123180908010 78
B112160918035 88
A107180908021 98
1 A
2 107
3 180908
2 999
输出样例：
Case 1: 1 A
A107180908108 100
A107180908021 98
A112180318002 98
Case 2: 2 107
3 260
Case 3: 3 180908
107 2
123 2
102 1
Case 4: 2 999
NA

分析：先把所有考生的准考证和分数记录下来～
1、按照等级查询，枚举选取匹配的学生，然后排序即可
2、按照考场查询，枚举选取匹配的学生，然后计数、求和
3、按日期查询每个考场人数，用unordered_map存储，最后排序汇总～

注意：1、第三个用map存储会超时，用unordered_map就不会超时啦～
2、排序传参建议用引用传参，这样更快，虽然有时候不用引用传参也能通过，但还是尽量用，养成好习惯～

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
struct node {
    string t;
    int value;
};
bool cmp(const node &a, const node &b) {
    return a.value != b.value ? a.value > b.value : a.t < b.t;
}
int main() {
    int n, k, num;
    string s;
    cin >> n >> k;
    vector<node> v(n);
    for (int i = 0; i < n; i++)
        cin >> v[i].t >> v[i].value;
    for (int i = 1; i <= k; i++) {
        cin >> num >> s;
        printf("Case %d: %d %s\n", i, num, s.c_str());
        vector<node> ans;
        int cnt = 0, sum = 0;
        if (num == 1) {
            for (int j = 0; j < n; j++)
                if (v[j].t[0] == s[0]) ans.push_back(v[j]);
        } else if (num == 2) {
            for (int j = 0; j < n; j++) {
                if (v[j].t.substr(1, 3) == s) {
                    cnt++;
                    sum += v[j].value;
                }
            }
            if (cnt != 0) printf("%d %d\n", cnt, sum);
        } else if (num == 3) {
            unordered_map<string, int> m;
            for (int j = 0; j < n; j++)
                if (v[j].t.substr(4, 6) == s) m[v[j].t.substr(1, 3)]++;
            for (auto it : m) ans.push_back({it.first, it.second});
        }
        sort(ans.begin(), ans.end(),cmp);
        for (int j = 0; j < ans.size(); j++)
            printf("%s %d\n", ans[j].t.c_str(), ans[j].value);
        if (((num == 1 || num == 3) && ans.size() == 0) || (num == 2 && cnt == 0)) printf("NA\n");
    }
    return 0;
}

#include <iostream>

#include <vector>

#include <unordered_map>

#include <algorithm>

using namespace std;

struct node {

string t;

int value;

};

bool cmp(const node &a, const node &b) {

return a.value != b.value ? a.value > b.value : a.t < b.t;

}

int main() {

int n, k, num;

string s;

cin >> n >> k;

vector<node> v(n);

for (int i = 0; i < n; i++)

cin >> v[i].t >> v[i].value;

for (int i = 1; i <= k; i++) {

cin >> num >> s;

printf("Case %d: %d %s\n", i, num, s.c_str());

vector<node> ans;

int cnt = 0, sum = 0;

if (num == 1) {

for (int j = 0; j < n; j++)

if (v[j].t[0] == s[0]) ans.push_back(v[j]);

} else if (num == 2) {

for (int j = 0; j < n; j++) {

if (v[j].t.substr(1, 3) == s) {

cnt++;

sum += v[j].value;

}

if (cnt != 0) printf("%d %d\n", cnt, sum);

} else if (num == 3) {

unordered_map<string, int> m;

for (int j = 0; j < n; j++)

if (v[j].t.substr(4, 6) == s) m[v[j].t.substr(1, 3)]++;

for (auto it : m) ans.push_back({it.first, it.second});

}

sort(ans.begin(), ans.end(),cmp);

for (int j = 0; j < ans.size(); j++)

printf("%s %d\n", ans[j].t.c_str(), ans[j].value);

if (((num == 1 || num == 3) && ans.size() == 0) || (num == 2 && cnt == 0)) printf("NA\n");

}

return 0;

}

1094 谷歌的招聘（20 point(s)） – PAT乙级真题

2004 年 7 月，谷歌在硅谷的 101 号公路边竖立了一块巨大的广告牌（如下图）用于招聘。内容超级简单，就是一个以 .com 结尾的网址，而前面的网址是一个 10 位素数，这个素数是自然常数 e 中最早出现的 10 位连续数字。能找出这个素数的人，就可以通过访问谷歌的这个网站进入招聘流程的下一步。

自然常数 e 是一个著名的超越数，前面若干位写出来是这样的：e = 2.718281828459045235360287471352662497757247093699959574966967627724076630353547594571382178525166427427466391932003059921… 其中粗体标出的 10 位数就是答案。

本题要求你编程解决一个更通用的问题：从任一给定的长度为 L 的数字中，找出最早出现的 K 位连续数字所组成的素数。

输入格式：
输入在第一行给出 2 个正整数，分别是 L（不超过 1000 的正整数，为数字长度）和 K（小于 10 的正整数）。接下来一行给出一个长度为 L 的正整数 N。

输出格式：
在一行中输出 N 中最早出现的 K 位连续数字所组成的素数。如果这样的素数不存在，则输出 404。注意，原始数字中的前导零也计算在位数之内。例如在 200236 中找 4 位素数，0023 算是解；但第一位 2 不能被当成 0002 输出，因为在原始数字中不存在这个 2 的前导零。

输入样例 1：
20 5
23654987725541023819
输出样例 1：
49877
输入样例 2：
10 3
2468024680
输出样例 2：
404

题目大意：给出一个l长度的字符串，求出其中第一个k位的素数
分析: 枚举每个k位的子串，转换成整数，判断是否是素数（判断素数的时候要把0和1也考虑进去）～

#include <iostream>
#include <string>
using namespace std;
bool isPrime(int n) {
    if (n == 0 || n == 1) return false;
    for (int i = 2; i * i <= n; i++)
        if (n % i == 0) return false;
    return true;
}
int main() {
    int l, k;
    string s;
    cin >> l >> k >> s;
    for (int i = 0; i <= l - k; i++) {
        string t = s.substr(i, k);
        int num = stoi(t);
        if (isPrime(num)) {
            cout << t;
            return 0;
        }
    }
    cout << "404\n";
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

bool isPrime(int n) {

if (n == 0 || n == 1) return false;

for (int i = 2; i * i <= n; i++)

if (n % i == 0) return false;

return true;

}

int main() {

int l, k;

string s;

cin >> l >> k >> s;

for (int i = 0; i <= l - k; i++) {

string t = s.substr(i, k);

int num = stoi(t);

if (isPrime(num)) {

cout << t;

return 0;

}

cout << "404\n";

return 0;

}

1093 字符串A+B （20 point(s)） – PAT乙级真题

给定两个字符串 A 和 B，本题要求你输出 A+B，即两个字符串的并集。要求先输出 A，再输出 B，但重复的字符必须被剔除。

输入格式：
输入在两行中分别给出 A 和 B，均为长度不超过 106 的、由可见 ASCII 字符 (即码32~126)和空格组成的、由回车标识结束的非空字符串。

输出格式：
在一行中输出题面要求的 A 和 B 的和。

输入样例：
This is a sample test
to show you_How it works
输出样例：
This ampletowyu_Hrk

题目大意：求出两个字符串的并集，按照原有顺序输出。意思是按顺序输出，第一次出现的所有字符。
分析：用数组hash标记一下是否是第一次输出即可（字符本身是一个ASCII码值，可当作整数用）

#include <iostream>
using namespace std;
int main() {
    string s1, s2, s;
    int hash[200] = {0};
    getline(cin, s1);
    getline(cin, s2);
    s = s1 + s2;
    for (int i = 0; i < s.size(); i++) {
        if (hash[s[i]] == 0) cout << s[i];
        hash[s[i]] = 1;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

string s1, s2, s;

int hash[200] = {0};

getline(cin, s1);

getline(cin, s2);

s = s1 + s2;

for (int i = 0; i < s.size(); i++) {

if (hash[s[i]] == 0) cout << s[i];

hash[s[i]] = 1;

}

return 0;

}

1092 最好吃的月饼（20 point(s)）- PAT乙级真题

月饼是久负盛名的中国传统糕点之一，自唐朝以来，已经发展出几百品种。

若想评比出一种“最好吃”的月饼，那势必在吃货界引发一场腥风血雨…… 在这里我们用数字说话，给出全国各地各种月饼的销量，要求你从中找出销量冠军，认定为最好吃的月饼。

输入格式：
输入首先给出两个正整数 N（≤1000）和 M（≤100），分别为月饼的种类数（于是默认月饼种类从 1 到 N 编号）和参与统计的城市数量。

接下来 M 行，每行给出 N 个非负整数（均不超过 1 百万），其中第 i 个整数为第 i 种月饼的销量（块）。数字间以空格分隔。

输出格式：
在第一行中输出最大销量，第二行输出销量最大的月饼的种类编号。如果冠军不唯一，则按编号递增顺序输出并列冠军。数字间以 1 个空格分隔，行首尾不得有多余空格。

输入样例：
5 3
1001 992 0 233 6
8 0 2018 0 2008
36 18 0 1024 4
输出样例：
2018
3 5

分析：用sum数组统计每种月饼的总销量，并且求出最大销量。然后遍历每种月饼的销量，等于最大值的就保存输出～

#include <iostream>
#include <vector>
using namespace std;
int sum[1005];
int main() {
    int m, n, temp, maxn = 0;
    vector<int> ans;
    cin >> m >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> temp;
            sum[j] += temp;
            maxn = max(maxn, sum[j]);
        }
    }
    cout << maxn << endl;
    for (int i = 1; i <= m; i++)
        if (sum[i] == maxn) ans.push_back(i);
    for (int i = 0; i < ans.size(); i++) {
        if (i != 0) cout << " ";
        cout << ans[i];
    }
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int sum[1005];

int main() {

int m, n, temp, maxn = 0;

vector<int> ans;

cin >> m >> n;

for (int i = 1; i <= n; i++) {

for (int j = 1; j <= m; j++) {

cin >> temp;

sum[j] += temp;

maxn = max(maxn, sum[j]);

}

cout << maxn << endl;

for (int i = 1; i <= m; i++)

if (sum[i] == maxn) ans.push_back(i);

for (int i = 0; i < ans.size(); i++) {

if (i != 0) cout << " ";

cout << ans[i];

}

return 0;

}

1091 N-自守数（15 point(s)） – PAT乙级真题

如果某个数 K 的平方乘以 N 以后，结果的末尾几位数等于 K，那么就称这个数为“N-自守数”。例如 3×922 = 25392，而 25392 的末尾两位正好是 92，所以 92 是一个 3-自守数。

本题就请你编写程序判断一个给定的数字是否关于某个 N 是 N-自守数。

输入格式：
输入在第一行中给出正整数 M（≤20），随后一行给出 M 个待检测的、不超过 1000 的正整数。

输出格式：
对每个需要检测的数字，如果它是 N-自守数就在一行中输出最小的 N 和 NK2 的值，以一个空格隔开；否则输出 No。注意题目保证 N<10。

输入样例：
3
92 5 233
输出样例：
3 25392
1 25
No

分析：从1-9枚举，判断是否存在N。通过to_string把乘积转成字符串，再通过substr取末尾子串比较即可～

#include <iostream>
#include <string>
using namespace std;
int main() {
    int m;
    cin >> m;
    while (m--) {
        int k, flag = 0;
        cin >> k;
        for (int n = 1; n < 10; n++) {
            int mul = n * k * k;
            string smul = to_string(mul), sk = to_string(k);
            string smulend = smul.substr(smul.length() - sk.length());
            if (smulend == sk) {
                printf("%d %d\n", n, mul);
                flag = 1;
                break;
            }
        }
        if (flag == 0) printf("No\n");
    }
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

int main() {

int m;

cin >> m;

while (m--) {

int k, flag = 0;

cin >> k;

for (int n = 1; n < 10; n++) {

int mul = n * k * k;

string smul = to_string(mul), sk = to_string(k);

string smulend = smul.substr(smul.length() - sk.length());

if (smulend == sk) {

printf("%d %d\n", n, mul);

flag = 1;

break;

}

if (flag == 0) printf("No\n");

}

return 0;

}

PAT 1153 Decode Registration Card of PAT （25 分）- 甲级

A registration card number of PAT consists of 4 parts:

the 1st letter represents the test level, namely, T for the top level, A for advance and B for basic;
the 2nd – 4th digits are the test site number, ranged from 101 to 999;
the 5th – 10th digits give the test date, in the form of yymmdd;
finally the 11th – 13th digits are the testee’s number, ranged from 000 to 999.
Now given a set of registration card numbers and the scores of the card owners, you are supposed to output the various statistics according to the given queries.

Input Specification:
Each input file contains one test case. For each case, the first line gives two positive integers N (≤104) and M (≤100), the numbers of cards and the queries, respectively.

Then N lines follow, each gives a card number and the owner’s score (integer in [0,100]), separated by a space.

After the info of testees, there are M lines, each gives a query in the format Type Term, where

Type being 1 means to output all the testees on a given level, in non-increasing order of their scores. The corresponding Term will be the letter which specifies the level;
Type being 2 means to output the total number of testees together with their total scores in a given site. The corresponding Term will then be the site number;
Type being 3 means to output the total number of testees of every site for a given test date. The corresponding Term will then be the date, given in the same format as in the registration card.
Output Specification:
For each query, first print in a line Case #: input, where # is the index of the query case, starting from 1; and input is a copy of the corresponding input query. Then output as requested:

for a type 1 query, the output format is the same as in input, that is, CardNumber Score. If there is a tie of the scores, output in increasing alphabetical order of their card numbers (uniqueness of the card numbers is guaranteed);
for a type 2 query, output in the format Nt Ns where Nt is the total number of testees and Ns is their total score;
for a type 3 query, output in the format Site Nt where Site is the site number and Nt is the total number of testees at Site. The output must be in non-increasing order of Nt’s, or in increasing order of site numbers if there is a tie of Nt.
If the result of a query is empty, simply print NA.

Sample Input:
8 4
B123180908127 99
B102180908003 86
A112180318002 98
T107150310127 62
A107180908108 100
T123180908010 78
B112160918035 88
A107180908021 98
1 A
2 107
3 180908
2 999
Sample Output:
Case 1: 1 A
A107180908108 100
A107180908021 98
A112180318002 98
Case 2: 2 107
3 260
Case 3: 3 180908
107 2
123 2
102 1
Case 4: 2 999
NA

题目大意：给出一组学生的准考证号和成绩，准考证号包含了等级(乙甲顶)，考场号，日期，和个人编号信息，并有三种查询方式
查询一：给出考试等级，找出该等级的考生，按照成绩降序，准考证升序排序
查询二：给出考场号，统计该考场的考生数量和总得分
查询三：给出考试日期，查询改日期下所有考场的考试人数，按照人数降序，考场号升序排序
分析：先把所有考生的准考证和分数记录下来～
1、按照等级查询，枚举选取匹配的学生，然后排序即可
2、按照考场查询，枚举选取匹配的学生，然后计数、求和
3、按日期查询每个考场人数，用unordered_map存储，最后排序汇总～

注意：1、第三个用map存储会超时，用unordered_map就不会超时啦～
2、排序传参建议用引用传参，这样更快，虽然有时候不用引用传参也能通过，但还是尽量用，养成好习惯～

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
struct node {
    string t;
    int value;
};
bool cmp(const node &a, const node &b) {
    return a.value != b.value ? a.value > b.value : a.t < b.t;
}
int main() {
    int n, k, num;
    string s;
    cin >> n >> k;
    vector<node> v(n);
    for (int i = 0; i < n; i++)
        cin >> v[i].t >> v[i].value;
    for (int i = 1; i <= k; i++) {
        cin >> num >> s;
        printf("Case %d: %d %s\n", i, num, s.c_str());
        vector<node> ans;
        int cnt = 0, sum = 0;
        if (num == 1) {
            for (int j = 0; j < n; j++)
                if (v[j].t[0] == s[0]) ans.push_back(v[j]);
        } else if (num == 2) {
            for (int j = 0; j < n; j++) {
                if (v[j].t.substr(1, 3) == s) {
                    cnt++;
                    sum += v[j].value;
                }
            }
            if (cnt != 0) printf("%d %d\n", cnt, sum);
        } else if (num == 3) {
            unordered_map<string, int> m;
            for (int j = 0; j < n; j++)
                if (v[j].t.substr(4, 6) == s) m[v[j].t.substr(1, 3)]++;
            for (auto it : m) ans.push_back({it.first, it.second});
        }
        sort(ans.begin(), ans.end(),cmp);
        for (int j = 0; j < ans.size(); j++)
            printf("%s %d\n", ans[j].t.c_str(), ans[j].value);
        if (((num == 1 || num == 3) && ans.size() == 0) || (num == 2 && cnt == 0)) printf("NA\n");
    }
    return 0;
}

#include <iostream>

#include <vector>

#include <unordered_map>

#include <algorithm>

using namespace std;

struct node {

string t;

int value;

};

bool cmp(const node &a, const node &b) {

return a.value != b.value ? a.value > b.value : a.t < b.t;

}

int main() {

int n, k, num;

string s;

cin >> n >> k;

vector<node> v(n);

for (int i = 0; i < n; i++)

cin >> v[i].t >> v[i].value;

for (int i = 1; i <= k; i++) {

cin >> num >> s;

printf("Case %d: %d %s\n", i, num, s.c_str());

vector<node> ans;

int cnt = 0, sum = 0;

if (num == 1) {

for (int j = 0; j < n; j++)

if (v[j].t[0] == s[0]) ans.push_back(v[j]);

} else if (num == 2) {

for (int j = 0; j < n; j++) {

if (v[j].t.substr(1, 3) == s) {

cnt++;

sum += v[j].value;

}

if (cnt != 0) printf("%d %d\n", cnt, sum);

} else if (num == 3) {

unordered_map<string, int> m;

for (int j = 0; j < n; j++)

if (v[j].t.substr(4, 6) == s) m[v[j].t.substr(1, 3)]++;

for (auto it : m) ans.push_back({it.first, it.second});

}

sort(ans.begin(), ans.end(),cmp);

for (int j = 0; j < ans.size(); j++)

printf("%s %d\n", ans[j].t.c_str(), ans[j].value);

if (((num == 1 || num == 3) && ans.size() == 0) || (num == 2 && cnt == 0)) printf("NA\n");

}

return 0;

}