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

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;

}

PAT 1152 Google Recruitment （20 分）-甲级

In July 2004, Google posted on a giant billboard along Highway 101 in Silicon Valley (shown in the picture below) for recruitment. The content is super-simple, a URL consisting of the first 10-digit prime found in consecutive digits of the natural constant e. The person who could find this prime number could go to the next step in Google’s hiring process by visiting this website.

The natural constant e is a well known transcendental number（超越数）. The first several digits are: e = 2.718281828459045235360287471352662497757247093699959574966967627724076630353547594571382178525166427427466391932003059921… where the 10 digits in bold are the answer to Google’s question.

Now you are asked to solve a more general problem: find the first K-digit prime in consecutive digits of any given L-digit number.

Input Specification:
Each input file contains one test case. Each case first gives in a line two positive integers: L (≤ 1,000) and K (< 10), which are the numbers of digits of the given number and the prime to be found, respectively. Then the L-digit number N is given in the next line.

Output Specification:
For each test case, print in a line the first K-digit prime in consecutive digits of N. If such a number does not exist, output 404 instead. Note: the leading zeroes must also be counted as part of the K digits. For example, to find the 4-digit prime in 200236, 0023 is a solution. However the first digit 2 must not be treated as a solution 0002 since the leading zeroes are not in the original number.

Sample Input 1:
20 5
23654987725541023819
Sample Output 1:
49877
Sample Input 2:
10 3
2468024680
Sample Output 2:
404

#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;

}