Code – 第2页 – 柳婼の blog

1161 Merging Linked Lists – PAT甲级真题

Given two singly linked lists L1=a1→a2→⋯→an−1→an and L2=b1→b2→⋯→bm−1→bm. If n≥2m, you are supposed to reverse and merge the shorter one into the longer one to obtain a list like a1→a2→bm→a3→a4→bm−1⋯. For example, given one list being 6→7 and the other one 1→2→3→4→5, you must output 1→2→7→3→4→6→5.

Input Specification:

Each input file contains one test case. For each case, the first line contains the two addresses of the first nodes of L1 and L2, plus a positive N (≤105) which is the total number of nodes given. The address of a node is a 5-digit nonnegative integer, and NULL is represented by -1.

Then N lines follow, each describes a node in the format:

Address Data Next

where Address is the position of the node, Data is a positive integer no more than 105, and Next is the position of the next node. It is guaranteed that no list is empty, and the longer list is at least twice as long as the shorter one.

Output Specification:

For each case, output in order the resulting linked list. Each node occupies a line, and is printed in the same format as in the input.

Sample Input:

00100 01000 7
02233 2 34891
00100 6 00001
34891 3 10086
01000 1 02233
00033 5 -1
10086 4 00033
00001 7 -1

Sample Output:

01000 1 02233
02233 2 00001
00001 7 34891
34891 3 10086
10086 4 00100
00100 6 00033
00033 5 -1

题目大意：给定两个单链表L1 = a1 → a2 → … → an-1 → an，和L2 = b1 → b2 → … → bm-1 → bm，如果n ≥2m，你的任务是将较短的那个链表逆序，然后将之并入比较长的那个链表，得到一个形如a1 → a2 → bm → a3 → a4 → bm-1 … 的结果，例如给定两个链表分别为6→7和1→2→3→4→5，你应该输出1→2→7→3→4→6→5。输入首先在第一行中给出两个链表L1和L2的头结点的地址、以及给定的结点总数N，一个结点的地址是一个5位数的非负整数，空地址 NULL用-1表示。随后N行，每行按以下格式给出一个结点的信息：Address Data Next，其中Address是结点的地址，Data是不超过10的5次方的正整数，Next是下一个结点的地址，题目保证没有空链表，并且较长的链表至少是较短链表的两倍长。按顺序输出结果列表，每个结点占一行，格式与输入相同。
分析：用vector<int> L1、L2存储题目中给定的两个链表，vector<int> ans保存合并后的链表。将较长的一个链表存储在L1中，如果原本L1较短，则将L1与L2用swap函数互相置换~在链表合并的过程中，i从0开始，将L1中每个结点添加到ans中，如果当前i是奇数（i & 1不等于0）就把L2的一个结点添加到ans中，直到L2中没有剩余元素~如此反复，就大功告成啦。

#include <iostream>
#include <vector>
using namespace std;
struct node {
    int data, next;
}A[100000];
vector<int> L1, L2, ans;
int sa, sb, n, a, ta, tb, c;
int main() {
    cin >> sa >> sb >> n;
    for (int i = 0; i < n; i++) {
        cin >> a >> A[a].data >> A[a].next;
    }
    ta = sa;
    while (ta != -1) {
        L1.push_back(ta);
        ta = A[ta].next;
    }
    tb = sb;
    while (tb != -1) {
        L2.push_back(tb);
        tb = A[tb].next;
    }
    if (L1.size() < L2.size()) swap(L1, L2);
    for (int i = 0, c = L2.size() - 1; i < L1.size(); i++) {
        ans.push_back(L1[i]);
        if (i & 1 && c >= 0) ans.push_back(L2[c--]);
    }
    for (int i = 1; i < ans.size(); i++) {
        printf("%05d %d %05d\n", ans[i-1], A[ans[i-1]].data, ans[i]);
    }
    printf("%05d %d -1", ans.back(), A[ans.back()].data);
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

struct node {

int data, next;

}A[100000];

vector<int> L1, L2, ans;

int sa, sb, n, a, ta, tb, c;

int main() {

cin >> sa >> sb >> n;

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

cin >> a >> A[a].data >> A[a].next;

}

ta = sa;

while (ta != -1) {

L1.push_back(ta);

ta = A[ta].next;

}

tb = sb;

while (tb != -1) {

L2.push_back(tb);

tb = A[tb].next;

}

if (L1.size() < L2.size()) swap(L1, L2);

for (int i = 0, c = L2.size() - 1; i < L1.size(); i++) {

ans.push_back(L1[i]);

if (i & 1 && c >= 0) ans.push_back(L2[c--]);

}

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

printf("%05d %d %05d\n", ans[i-1], A[ans[i-1]].data, ans[i]);

}

printf("%05d %d -1", ans.back(), A[ans.back()].data);

return 0;

}

1160 Forever – PAT甲级真题

“Forever number” is a positive integer A with K digits, satisfying the following constrains:

the sum of all the digits of A is m;
the sum of all the digits of A+1 is n; and
the greatest common divisor of m and n is a prime number which is greater than 2.

Now you are supposed to find these forever numbers.

Input Specification:

Each input file contains one test case. For each test case, the first line contains a positive integer N (≤5). Then N lines follow, each gives a pair of K (3<K<10) and m (1<m<90), of which the meanings are given in the problem description.

Output Specification:

For each pair of K and m, first print in a line Case X, where X is the case index (starts from 1). Then print n and A in the following line. The numbers must be separated by a space. If the solution is not unique, output in the ascending order of n. If still not unique, output in the ascending order of A. If there is no solution, output No Solution.

Sample Input:

2
6 45
7 80

Sample Output:

Case 1
10 189999
10 279999
10 369999
10 459999
10 549999
10 639999
10 729999
10 819999
10 909999
Case 2
No Solution

题目大意：“天长地久数”是指一个K位正整数A，其满足条件为A的各位数字之和为m，A+1的各位数字之和为n，且m与n的最大公约数是一个大于2的素数。本题就请你找出这些天长地久数。输入在第一行给出正整数N（≤5），随后N行，每行给出一对K（3<K<10）和m（1<m<90）。对每一对输入的K和m，首先在一行中输出Case X，其中X是输出的编号（从1开始）；然后一行输出对应的n和A，数字间以空格分隔。如果解不唯一，则每组解占一行，按n的递增序输出；若仍不唯一，则按A的递增序输出。若解不存在，则在一行中输出No Solution。
分析：sum记录A的各位数字之和，sum2记录A+1的各位数字之和，I与II分别为数A与A+1。由打表观察可得，所有天长地久数最后两位为”99″，那么将末尾的两个’9’隐藏后可直接带入暴力循环判断。将所有可能答案存储后排序输出即可~

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
struct node {
    int n, num;
    friend bool operator < (node &a, node &b) {
        if (a.n != b.n) return a.n < b.n;
        return a.num < b.num;
    }
}T;
int N, K, m, temp, sum, sum2, I, II;
vector<node> A;
int is_prime(int x) {
    if (x <= 2) return 0;
    for (int i = 2; i <= sqrt(x); i++) {
        if (x % i == 0) return 0; 
    }
    return 1;
}
int main() {
    cin >> N;
    for (int i = 1 ; i <= N; i++) {
        A.clear();
        cout << "Case " << i << '\n';
        cin >> K >> m;
        if (K * 9 < m) cout << "No Solution\n";
        else {
            temp = pow(10, K - 2);
            for (int i = temp / 10; i < temp; i++) {
                sum = 18, sum2 = 0, I = i, II = i + 1;
                while (I) {
                    sum += I % 10;
                    I /= 10;
                    if (sum > m) break;
                }
                while (II) {
                    sum2 += II % 10;
                    II /= 10;
                }
                if (sum == m && is_prime(__gcd(m, sum2))) {
                    T.n = sum2, T.num = i;
                    A.push_back(T);
                }
            }
            sort(A.begin(), A.end());
            if (A.empty()) cout << "No Solution\n";
            for (auto &it : A) {
                cout << it.n << ' ' << it.num << "99\n";
            }
        }
        
    }
    return 0;
}

#include <iostream>

#include <vector>

#include <cmath>

#include <algorithm>

using namespace std;

struct node {

int n, num;

friend bool operator < (node &a, node &b) {

if (a.n != b.n) return a.n < b.n;

return a.num < b.num;

}

}T;

int N, K, m, temp, sum, sum2, I, II;

vector<node> A;

int is_prime(int x) {

if (x <= 2) return 0;

for (int i = 2; i <= sqrt(x); i++) {

if (x % i == 0) return 0;

}

return 1;

}

int main() {

cin >> N;

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

A.clear();

cout << "Case " << i << '\n';

cin >> K >> m;

if (K * 9 < m) cout << "No Solution\n";

else {

temp = pow(10, K - 2);

for (int i = temp / 10; i < temp; i++) {

sum = 18, sum2 = 0, I = i, II = i + 1;

while (I) {

sum += I % 10;

I /= 10;

if (sum > m) break;

}

while (II) {

sum2 += II % 10;

II /= 10;

}

if (sum == m && is_prime(__gcd(m, sum2))) {

T.n = sum2, T.num = i;

A.push_back(T);

}

sort(A.begin(), A.end());

if (A.empty()) cout << "No Solution\n";

for (auto &it : A) {

cout << it.n << ' ' << it.num << "99\n";

}

return 0;

}

1159 Structure of a Binary Tree – PAT甲级真题

Suppose that all the keys in a binary tree are distinct positive integers. Given the postorder and inorder traversal sequences, a binary tree can be uniquely determined.

Now given a sequence of statements about the structure of the resulting tree, you are supposed to tell if they are correct or not. A statment is one of the following:

A is the root
A and B are siblings
A is the parent of B
A is the left child of B
A is the right child of B
A and B are on the same level
It is a full tree

Note:

Two nodes are on the same level, means that they have the same depth.
A full binary tree is a tree in which every node other than the leaves has two children.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (≤30), the total number of nodes in the binary tree. The second line gives the postorder sequence and the third line gives the inorder sequence. All the numbers in a line are no more than 103 and are separated by a space.

Then another positive integer M (≤30) is given, followed by M lines of statements. It is guaranteed that both A and B in the statements are in the tree.

Output Specification:

For each statement, print in a line Yes if it is correct, or No if not.

Sample Input:

9
16 7 11 32 28 2 23 8 15
16 23 7 32 11 2 28 15 8
7
15 is the root
8 and 2 are siblings
32 is the parent of 11
23 is the left child of 16
28 is the right child of 2
7 and 11 are on the same level
It is a full tree

Sample Output:

Yes
No
Yes
No
Yes
Yes
Yes

题目大意：假设二叉树中的所有值都是不同的正整数，给定后序和中序遍历可以唯一确定一棵二叉树。给出一系列关于二叉树结构的语句，判断它们是否正确，语句是以下之一：A是根结点，A和B是兄弟姐妹，A是B的父结点，A是B的左孩子，A是B的右孩子，A和B在同一层，这是一棵full tree。（两个结点在同一层，意味着这两个结点具有同样深度；full binary tree是指除了叶子结点外，每个结点都有两个孩子）。输入样例：第一行给出正整数N，即二叉树中结点的总数；第二行给出后序遍历序列，第三行给出中序遍历序列。一行中所有数字不超过10的3次方，并且用空格分隔。然后给出一个正整数M，然后是M行语句，保证语句的A和B都在树中。输出样例：对于每条语句，如果正确，则输出Yes，否则输出No。
分析：中序存储在In数组中，后序存储在Post数组中，根据中序和后序建树，Tree中存储树上结点的相关信息，下标即表示结点的值，其中lchild存储左孩子下标，rchild存储右孩子下标，parent存储父结点下标，将这些初始化为-1表示不存在，level存储深度，此外，root为根节点的值，Full标记是否是full tree，f判断当前语句是否正确，最后根据f的值输出Yes或No~

#include<iostream>
using namespace std;
struct node {
    int lchild, rchild, parent, level;
    node() {
        lchild = rchild = parent = -1;
    }
}Tree[1002];
int n, m, a, b, root, f, Full;
int In[32], Post[32];
string t;
int deal(int R, int start, int end, int Pa) {
    if(start > end) return -1;
    int i = start;
    while(i < end && In[i] != Post[R]) i++;
    Tree[Post[R]].parent = Pa;
    Tree[Post[R]].level = Tree[Pa].level + 1;
    Tree[Post[R]].lchild = deal(R - 1 - end + i, start, i - 1, Post[R]);
    Tree[Post[R]].rchild = deal(R - 1, i + 1, end, Post[R]);
    if (Tree[Post[R]].lchild * Tree[Post[R]].rchild < 0) Full = 1;
    return Post[R];
}
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> Post[i];
    } 
    for (int i = 0; i < n; i++) 
        cin >> In[i];
    root = Post[n - 1];
    deal(n - 1, 0, n - 1, 1001);
    cin >> m;
    while (m--) {
        f = 0;
        cin >> t;
        if (t == "It") {
            cin >> t >> t >> t >> t;
            if (Full) cout << "No\n";
            else cout << "Yes\n";
            continue;
        } 
        a = stoi(t);
        cin >> t;
        if (t == "is") {
            cin >> t >> t;
            if (t == "root") {
                if (a == root) f = 1;
            } else if (t == "parent") {
                cin >> t >> b;
                if (Tree[b].parent == a) f = 1;
            } else if (t == "left") {
                cin >> t >> t >> b;
                if (Tree[b].lchild == a) f = 1;
            } else {
                cin >> t >> t >> b;
                if (Tree[b].rchild == a) f = 1;
            }
        } else {
            cin >> b >> t >> t;
            if (t == "siblings") {
                if (Tree[a].parent == Tree[b].parent) f = 1;
            } else {
                cin >> t >> t >> t;
                if (Tree[a].level == Tree[b].level) f = 1;
            }
        }
        cout << (f ? "Yes\n" : "No\n");
    }
    return 0;
}

#include<iostream>

using namespace std;

struct node {

int lchild, rchild, parent, level;

node() {

lchild = rchild = parent = -1;

}

}Tree[1002];

int n, m, a, b, root, f, Full;

int In[32], Post[32];

string t;

int deal(int R, int start, int end, int Pa) {

if(start > end) return -1;

int i = start;

while(i < end && In[i] != Post[R]) i++;

Tree[Post[R]].parent = Pa;

Tree[Post[R]].level = Tree[Pa].level + 1;

Tree[Post[R]].lchild = deal(R - 1 - end + i, start, i - 1, Post[R]);

Tree[Post[R]].rchild = deal(R - 1, i + 1, end, Post[R]);

if (Tree[Post[R]].lchild * Tree[Post[R]].rchild < 0) Full = 1;

return Post[R];

}

int main() {

cin >> n;

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

cin >> Post[i];

}

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

cin >> In[i];

root = Post[n - 1];

deal(n - 1, 0, n - 1, 1001);

cin >> m;

while (m--) {

f = 0;

cin >> t;

if (t == "It") {

cin >> t >> t >> t >> t;

if (Full) cout << "No\n";

else cout << "Yes\n";

continue;

}

a = stoi(t);

cin >> t;

if (t == "is") {

cin >> t >> t;

if (t == "root") {

if (a == root) f = 1;

} else if (t == "parent") {

cin >> t >> b;

if (Tree[b].parent == a) f = 1;

} else if (t == "left") {

cin >> t >> t >> b;

if (Tree[b].lchild == a) f = 1;

} else {

cin >> t >> t >> b;

if (Tree[b].rchild == a) f = 1;

}

} else {

cin >> b >> t >> t;

if (t == "siblings") {

if (Tree[a].parent == Tree[b].parent) f = 1;

} else {

cin >> t >> t >> t;

if (Tree[a].level == Tree[b].level) f = 1;

}

cout << (f ? "Yes\n" : "No\n");

}

return 0;

}

1158 Telefraud Detection – PAT甲级真题

Telefraud（电信诈骗） remains a common and persistent problem in our society. In some cases, unsuspecting victims lose their entire life savings. To stop this crime, you are supposed to write a program to detect those suspects from a huge amount of phone call records.

A person must be detected as a suspect if he/she makes more than K short phone calls to different people everyday, but no more than 20% of these people would call back. And more, if two suspects are calling each other, we say they might belong to the same gang. A makes a short phone call to B means that the total duration of the calls from A to B is no more than 5 minutes.

Input Specification:

Each input file contains one test case. For each case, the first line gives 3 positive integers K (≤500, the threshold（阈值） of the amount of short phone calls), N (≤103, the number of different phone numbers), and M (≤105, the number of phone call records). Then M lines of one day’s records are given, each in the format:

caller receiver duration

where caller and receiver are numbered from 1 to N, and duration is no more than 1440 minutes in a day.

Output Specification:

Print in each line all the detected suspects in a gang, in ascending order of their numbers. The gangs are printed in ascending order of their first members. The numbers in a line must be separated by exactly 1 space, and there must be no extra space at the beginning or the end of the line.

If no one is detected, output None instead.

Sample Input 1:

5 15 31
1 4 2
1 5 2
1 5 4
1 7 5
1 8 3
1 9 1
1 6 5
1 15 2
1 15 5
3 2 2
3 5 15
3 13 1
3 12 1
3 14 1
3 10 2
3 11 5
5 2 1
5 3 10
5 1 1
5 7 2
5 6 1
5 13 4
5 15 1
11 10 5
12 14 1
6 1 1
6 9 2
6 10 5
6 11 2
6 12 1
6 13 1

Sample Output 1:

3 5
6

Note: In sample 1, although 1 had 9 records, but there were 7 distinct receivers, among which 5 and 15 both had conversations lasted more than 5 minutes in total. Hence 1 had made 5 short phone calls and didn’t exceed the threshold 5, and therefore is not a suspect.

Sample Input 2:

5 7 8
1 2 1
1 3 1
1 4 1
1 5 1
1 6 1
1 7 1
2 1 1
3 1 1

Sample Output 2:

None

题目大意：编写一个程序，从大量的通话记录中检测出电信诈骗嫌疑人。如果一个人每天给不同的人打超过K个短电话，但这些人中回电的比例不超过20%，那他可能是嫌疑人。而且，如果两个嫌疑人互相打电话，我们认为他们可能属于同一个团伙。A给B打短电话是指A到B的通话总时长不超过5分钟。给三个正整数：短电话数量的阈值K，不同电话号码的数量N，通话记录数量M。接下来M行给出一天的通话记录，格式为呼叫者caller、接收者receiver、时长duration。输出格式：在每一行输出一个团伙中所有检测到的嫌疑人，按数字升序排列。这些帮派按第一个成员的升序排列。一行中的数字必须使用1个空格分隔，并且行首或行尾不得有多余空格。
分析：p为并查集的父集，sc中存储短通话的人数，rec中存储短通话收到回电的人数，mark用来标记是否输出过，record记录两个人的通话总时长，su中保存嫌疑人的编号。我们先记录下来两人之间的通话总时间，以此来统计短通话以及回电的次数，进而判断出某个人是不是嫌疑人。如果没有嫌疑人，则输出None。因为要按照帮派输出，所以我们用并查集把互相通过电话的嫌疑人设置到同一个集合内，然后就可以输出答案了~

#include <iostream>
#include <vector>
using namespace std;
int k, n, m, c, r, d, p[1001], sc[1001], rec[1001], mark[1001], record[1001][1001];
vector<int> su;
int Find(int a) {
    if (p[a] != a) return p[a] = Find(p[a]);
    return a;
}
void add(int a, int b) {
    int f1 = Find(a), f2 = Find(b);
    if (f1 < f2) p[f2] = f1;
    else p[f1] = f2;
}
int main() {
    for (int i = 1; i <= 1000; i++) p[i] = i;
    cin >> k >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> c >> r >> d;
        record[c][r] += d;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (record[i][j] && record[i][j] <= 5) {
                sc[i]++;
                if (record[j][i]) rec[i]++;
            }
        }
        if (sc[i] > k && rec[i] * 5 <= sc[i]) su.push_back(i);
    }
    if (su.empty()) {
        cout << "None";
        return 0;
    }
    for (int i = 0; i < su.size(); i++) {
        for (int j = i + 1; j < su.size(); j++) {
            if (record[su[i]][su[j]] && record[su[j]][su[i]]) add(su[i], su[j]);
        }
    }
    for (int i = 0; i < su.size(); i++) {
        if (mark[su[i]]) continue;
        cout << su[i];
        for (int j = i + 1; j < su.size(); j++) {
            if (Find(su[i]) == Find(su[j])) {
                cout << ' ' << su[j];
                mark[su[j]] = 1;
            }
        }
        cout << '\n';
    }
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int k, n, m, c, r, d, p[1001], sc[1001], rec[1001], mark[1001], record[1001][1001];

vector<int> su;

int Find(int a) {

if (p[a] != a) return p[a] = Find(p[a]);

return a;

}

void add(int a, int b) {

int f1 = Find(a), f2 = Find(b);

if (f1 < f2) p[f2] = f1;

else p[f1] = f2;

}

int main() {

for (int i = 1; i <= 1000; i++) p[i] = i;

cin >> k >> n >> m;

for (int i = 0; i < m; i++) {

cin >> c >> r >> d;

record[c][r] += d;

}

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

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

if (record[i][j] && record[i][j] <= 5) {

sc[i]++;

if (record[j][i]) rec[i]++;

}

if (sc[i] > k && rec[i] * 5 <= sc[i]) su.push_back(i);

}

if (su.empty()) {

cout << "None";

return 0;

}

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

for (int j = i + 1; j < su.size(); j++) {

if (record[su[i]][su[j]] && record[su[j]][su[i]]) add(su[i], su[j]);

}

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

if (mark[su[i]]) continue;

cout << su[i];

for (int j = i + 1; j < su.size(); j++) {

if (Find(su[i]) == Find(su[j])) {

cout << ' ' << su[j];

mark[su[j]] = 1;

}

cout << '\n';

}

return 0;

}

1157 Anniversary – PAT甲级真题

Zhejiang University is about to celebrate her 122th anniversary in 2019. To prepare for the celebration, the alumni association （校友会） has gathered the ID’s of all her alumni. Now your job is to write a program to count the number of alumni among all the people who come to the celebration.

Input Specification:

Each input file contains one test case. For each case, the first part is about the information of all the alumni. Given in the first line is a positive integer N (≤105). Then N lines follow, each contains an ID number of an alumnus. An ID number is a string of 18 digits or the letter X. It is guaranteed that all the ID’s are distinct.

The next part gives the information of all the people who come to the celebration. Again given in the first line is a positive integer M (≤105). Then M lines follow, each contains an ID number of a guest. It is guaranteed that all the ID’s are distinct.

Output Specification:

First print in a line the number of alumni among all the people who come to the celebration. Then in the second line, print the ID of the oldest alumnus — notice that the 7th – 14th digits of the ID gives one’s birth date. If no alumnus comes, output the ID of the oldest guest instead. It is guaranteed that such an alumnus or guest is unique.

Sample Input:

5
372928196906118710
610481197806202213
440684198612150417
13072819571002001X
150702193604190912
6
530125197901260019
150702193604190912
220221196701020034
610481197806202213
440684198612150417
370205198709275042

Sample Output:

3
150702193604190912

题目大意：为了准备校庆，校友会收集了所有校友的身份证号。编写程序，根据来参加校庆的所有人士的身份证号，统计来了多少校友。输入在第一行正整数N，随后N行，每行给出一位校友的身份证号（18位由数字和大写字母X组成的字符串）。题目保证身份证号不重复。随后给出前来参加校庆的所有人士的信息：首先是一个不超过正整数M，随后M行，每行给出一位人士的身份证号。题目保证身份证号不重复。首先在第一行输出参加校庆的校友的人数。然后在第二行输出最年长的校友的身份证号——注意身份证第7-14位给出的是yyyymmdd格式的生日。如果没有校友来，则在第二行输出最年长的来宾的身份证号。题目保证这样的校友或来宾必是唯一的。
分析：使用容器set<string> record存储校友的身份证信息，smallx记录校友中最年长的生日，smalla记录所有人中最年长的生日，ansx记录最年长的校友的身份证号，ansa记录所有人中最年长的人的身份证号，cnt记录有多少校友参加。将校友身份证存储在set容器record中，使用record.count来判断参加校庆的人是否是校友，使用substr(6, 8)快速提取身份证号中的生日信息，最后根据cnt的值输出~cnt不等于0，则说明有校友参加，输出最年长的校友的身份证号ansx；如果cnt等于0，说明没有校友参加，输出所有人中最年长的人的身份证号ansa~

#include <iostream>
#include <set>
using namespace std;
int n, m, cnt;
string temp, smallx = "99999999", smalla = "99999999", ansx, ansa;
set<string> record;
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> temp;
        record.insert(temp);
    }
    cin >> m;
    for (int i = 0; i < m; i++) {
        cin >> temp;
        if (record.count(temp)) {
            cnt++;
            if (smallx > temp.substr(6, 8)) {
                smallx = temp.substr(6, 8);
                ansx = temp;
            }
        }
        if (smalla > temp.substr(6, 8)) {
                smalla = temp.substr(6, 8);
                ansa = temp;
        }
    }
    cout << cnt << endl;
    if (cnt) cout << ansx;
    else cout << ansa;
    return 0;
}

#include <iostream>

#include <set>

using namespace std;

int n, m, cnt;

string temp, smallx = "99999999", smalla = "99999999", ansx, ansa;

set<string> record;

int main() {

cin >> n;

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

cin >> temp;

record.insert(temp);

}

cin >> m;

for (int i = 0; i < m; i++) {

cin >> temp;

if (record.count(temp)) {

cnt++;

if (smallx > temp.substr(6, 8)) {

smallx = temp.substr(6, 8);

ansx = temp;

}

if (smalla > temp.substr(6, 8)) {

smalla = temp.substr(6, 8);

ansa = temp;

}

cout << cnt << endl;

if (cnt) cout << ansx;

else cout << ansa;

return 0;

}

1156 Sexy Primes – PAT甲级真题

Sexy primes are pairs of primes of the form (p, p+6), so-named since “sex” is the Latin word for “six”. (Quoted from http://mathworld.wolfram.com/SexyPrimes.html)

Now given an integer, you are supposed to tell if it is a sexy prime.

Input Specification:

Each input file contains one test case. Each case gives a positive integer N (≤108).

Output Specification:

For each case, print in a line Yes if N is a sexy prime, then print in the next line the other sexy prime paired with N (if the answer is not unique, output the smaller number). Or if N is not a sexy prime, print No instead, then print in the next line the smallest sexy prime which is larger than N.

Sample Input 1:

Sample Output 1:

Yes
41

Sample Input 2:

Sample Output 2:

No
23

题目大意：性感素数是指形如 (p, p+6) 这样的一对素数。给定一个整数，判断其是否为一个性感素数。若N是一个性感素数，则在一行中输出Yes，并在第二行输出与N配对的另一个性感素数（若这样的数不唯一，输出较小的那个）。若N不是性感素数，则在一行中输出No，然后在第二行输出大于N的最小性感素数。
分析：is_prime判断是否为素数。判断p和p-6、p和p+6是否同时为素数，如果是，则为性感素数输出Yes。不是的话就从p+1往后找到第一个满足要求的数ans~

#include <iostream>
#include <cmath>
using namespace std;
int p, ans;
int is_prime(int x) {
    if (x < 2) return 0;
    for (int i = 2; i <= sqrt(x); i++)
        if (x % i == 0) return 0; 
    return 1;
}
int main() {
    cin >> p;
    if (is_prime(p) && is_prime(p - 6)) {
        cout << "Yes\n" << p - 6;
    } else if (is_prime(p) && is_prime(p + 6)) {
        cout << "Yes\n" << p + 6;
    } else {
        for (ans = p + 1; ; ans++) {
            if (is_prime(ans) && is_prime(ans - 6)) break;
            if (is_prime(ans) && is_prime(ans + 6)) break;
        }
        cout << "No\n" << ans;
    }
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int p, ans;

int is_prime(int x) {

if (x < 2) return 0;

for (int i = 2; i <= sqrt(x); i++)

if (x % i == 0) return 0;

return 1;

}

int main() {

cin >> p;

if (is_prime(p) && is_prime(p - 6)) {

cout << "Yes\n" << p - 6;

} else if (is_prime(p) && is_prime(p + 6)) {

cout << "Yes\n" << p + 6;

} else {

for (ans = p + 1; ; ans++) {

if (is_prime(ans) && is_prime(ans - 6)) break;

if (is_prime(ans) && is_prime(ans + 6)) break;

}

cout << "No\n" << ans;

}

return 0;

}