liuchuo – 第13页 – 柳婼の blog

1101 B是A的多少倍 – PAT乙级真题

设一个数 A 的最低 D 位形成的数是 ad。如果把 ad 截下来移到 A 的最高位前面，就形成了一个新的数 B。B 是 A 的多少倍？例如将 12345 的最低 2 位 45 截下来放到 123 的前面，就得到 45123，它约是 12345 的 3.66 倍。

输入格式：

输入在一行中给出一个正整数 A（≤10⁹）和要截取的位数 D。题目保证 D 不超过 A 的总位数。

输出格式：

计算 B 是 A 的多少倍，输出小数点后 2 位。

输入样例 1：

12345 2

输出样例 1：

3.66

输入样例 2：

12345 5

输出样例 2：

1.00

分析：数字A和B分别存储在字符串string a和b中，a的最低d位形成的数所构成的字符串是a.substr(a.size()-d)，a的前半部分是a.substr(0, a.size()-d)，将这两部分拼接形成新的字符串b，用stod将字符串b和a转换为double类型的数字，输出stod(b)/stod(a)的结果，保留小数点后两位~

#include <iostream>
#include <string>
using namespace std;
string a, b;
int d;
int main() {
    cin >> a >> d;
    b = a.substr(a.size() - d) + a.substr(0, a.size() - d);
    double ans = stod(b) / stod(a);
    printf("%.2f", ans);
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

string a, b;

int d;

int main() {

cin >> a >> d;

b = a.substr(a.size() - d) + a.substr(0, a.size() - d);

double ans = stod(b) / stod(a);

printf("%.2f", ans);

return 0;

}

1100 校庆 – PAT乙级真题

2019 年浙江大学将要庆祝成立 122 周年。为了准备校庆，校友会收集了所有校友的身份证号。现在需要请你编写程序，根据来参加校庆的所有人士的身份证号，统计来了多少校友。

输入格式：

输入在第一行给出不超过 105 的正整数 N，随后 N 行，每行给出一位校友的身份证号（18 位由数字和大写字母X组成的字符串）。题目保证身份证号不重复。

随后给出前来参加校庆的所有人士的信息：首先是一个不超过 105 的正整数 M，随后 M 行，每行给出一位人士的身份证号。题目保证身份证号不重复。

输出格式：

首先在第一行输出参加校庆的校友的人数。然后在第二行输出最年长的校友的身份证号 —— 注意身份证第 7-14 位给出的是 yyyymmdd 格式的生日。如果没有校友来，则在第二行输出最年长的来宾的身份证号。题目保证这样的校友或来宾必是唯一的。

输入样例：

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

输出样例：

3
150702193604190912

分析：使用容器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;

}

1099 性感素数 – PAT乙级真题

“性感素数”是指形如 (p, p+6) 这样的一对素数。之所以叫这个名字，是因为拉丁语管“六”叫“sex”（即英语的“性感”）。（原文摘自 http://mathworld.wolfram.com/SexyPrimes.html）

现给定一个整数，请你判断其是否为一个性感素数。

输入格式：

输入在一行中给出一个正整数 N (≤10⁸)。

输出格式：

若 N 是一个性感素数，则在一行中输出 Yes，并在第二行输出与 N 配对的另一个性感素数（若这样的数不唯一，输出较小的那个）。若 N 不是性感素数，则在一行中输出 No，然后在第二行输出大于 N 的最小性感素数。

输入样例 1：

输出样例 1：

Yes
41

输入样例 2：

输出样例 2：

No
23

分析：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;

}

1098 岩洞施工 – PAT乙级真题

要将一条直径至少为 1 个单位的长管道水平送入地形复杂的岩洞中，究竟是否可能？下面的两幅图分别给出了岩洞的剖面图，深蓝色的折线勾勒出岩洞顶部和底部的轮廓。图 1 是有可能的，绿色部分显示直径为 1 的管道可以送入。图 2 就不可能，除非把顶部或底部的突出部分削掉 1 个单位的高度。

本题就请你编写程序，判断给定的岩洞中是否可以施工。

输入格式：

输入在第一行给出一个不超过 100 的正整数 N，即横向采样的点数。随后两行数据，从左到右顺次给出采样点的纵坐标：第 1 行是岩洞顶部的采样点，第 2 行是岩洞底部的采样点。这里假设坐标原点在左下角，每个纵坐标为不超过 1000 的非负整数。同行数字间以空格分隔。

题目保证输入数据是合理的，即岩洞底部的轮廓线不会与顶部轮廓线交叉。

输出格式：

如果可以直接施工，则在一行中输出 Yes 和可以送入的管道的最大直径；如果不行，则输出 No 和至少需要削掉的高度。答案和数字间以 1 个空格分隔。

输入样例 1：

11
7 6 5 5 6 5 4 5 5 4 4
3 2 2 2 2 3 3 2 1 2 3

输出样例 1：

Yes 1

输入样例 2：

11
7 6 5 5 6 5 4 5 5 4 4
3 2 2 2 3 4 3 2 1 2 3

输出样例 2：

No 1

分析：找到上壁的最低点minA、下壁的最高点maxB，如果minA<=minB，则输出No，需要削掉的高度为maxB-minA+1；否则输出Yes，管道的最大直径为minA-maxB~

#include <bits/stdc++.h>
using namespace std;
int n, a, b, minA = 2000, maxB;
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a;
        minA = min(a, minA);
    }
    for (int i = 0; i < n; i++) {
        cin >> b;
        maxB = max(b, maxB);
    }
    if (minA <= maxB) 
        cout << "No " << maxB - minA + 1;
    else 
        cout << "Yes " << minA - maxB;
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

int n, a, b, minA = 2000, maxB;

int main() {

cin >> n;

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

cin >> a;

minA = min(a, minA);

}

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

cin >> b;

maxB = max(b, maxB);

}

if (minA <= maxB)

cout << "No " << maxB - minA + 1;

else

cout << "Yes " << minA - maxB;

return 0;

}

1097 矩阵行平移 – PAT乙级真题

给定一个 n×n 的整数矩阵。对任一给定的正整数 k<n，我们将矩阵的奇数行的元素整体向右依次平移 1、……、k、1、……、k、…… 个位置，平移空出的位置用整数 x 补。你需要计算出结果矩阵的每一列元素的和。

输入格式：

输入第一行给出 3 个正整数：n（<100）、k（<n）、x（<100），分别如题面所述。

接下来 n 行，每行给出 n 个不超过 100 的正整数，为矩阵元素的值。数字间以空格分隔。

输出格式：

在一行中输出平移后第 1 到 n 列元素的和。数字间以 1 个空格分隔，行首尾不得有多余空格。

输入样例：

7 2 99
11 87 23 67 20 75 89
37 94 27 91 63 50 11
44 38 50 26 40 26 24
73 85 63 28 62 18 68
15 83 27 97 88 25 43
23 78 98 20 30 81 99
77 36 48 59 25 34 22

输出样例：

529 481 479 263 417 342 343

分析：二维数组A存储矩阵，数组Sum存储每列元素的和，cnt表示当前行需要右移多少次。首先将输入元素存储到数组A中，因为偶数行元素始终不变，我们可以将偶数行的每列元素之和先累加后保存在Sum数组中（i&1的解释：是判断i为奇偶数的一种更快方法，因为奇数的二进制最低位为1，偶数为0，那么和1按位与，奇数结果为1，偶数结果为0）。
接下来for循环处理每一个奇数行，i从0开始每步+2。cnt为当前行向右平移的步数，初始值为1。从0到cnt-1列，已经平移后变成了x的值，所以Sum累加x的值；从cnt列到n-1列，Sum[j]累加数组A第i行第j-cnt列的数字A[i][j-cnt]（相当于平移）。每次cnt值为cnt%k+1，这样可实现cnt从1、2、…、k、1、2、…、k的循环。最后输出Sum数组的每一个值，就是每一列元素的和~

#include <iostream>
using namespace std;
int n, k, x, cnt = 1, Sum[100], A[100][100];
int main() {
    cin >> n >> k >> x;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> A[i][j];
            if (i & 1) Sum[j] += A[i][j];
        }
    }
    for (int i = 0; i < n; i += 2) {
        for (int j = 0; j < cnt; j++) Sum[j] += x;
        for (int j = cnt; j < n; j++) Sum[j] += A[i][j-cnt];
        cnt = cnt % k + 1;
    }
    for (int i = 0; i < n; i++) {
        if (i) cout << ' ';
        cout << Sum[i];
    }
    return 0;
}

#include <iostream>

using namespace std;

int n, k, x, cnt = 1, Sum[100], A[100][100];

int main() {

cin >> n >> k >> x;

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

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

cin >> A[i][j];

if (i & 1) Sum[j] += A[i][j];

}

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

for (int j = 0; j < cnt; j++) Sum[j] += x;

for (int j = cnt; j < n; j++) Sum[j] += A[i][j-cnt];

cnt = cnt % k + 1;

}

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

if (i) cout << ' ';

cout << Sum[i];

}

return 0;

}

1096 大美数 – PAT乙级真题

若正整数 N 可以整除它的 4 个不同正因数之和，则称这样的正整数为“大美数”。本题就要求你判断任一给定的正整数是否是“大美数”。

输入格式：

输入在第一行中给出正整数 K（≤10），随后一行给出 K 个待检测的、不超过 10⁴ 的正整数。

输出格式：

对每个需要检测的数字，如果它是大美数就在一行中输出 Yes，否则输出 No。

输入样例：

3
18 29 40

输出样例：

Yes
No
Yes

分析：检验每一个输入的数字num，for循环遍历，寻找四个不同的正因数a、b、c、d（假设abcd由小到大），判断四个正因数之和a+b+c+d是否能被num整除（用flag的值表示），flag==1时就直接break退出寻找因数的循环，最后根据flag的值输出Yes或No~

#include <iostream>
using namespace std;
int k, num, flag;
int main() {
    cin >> k;
    for (int i = 0; i < k; i++) {
        cin >> num;
        flag = 0;
        for (int a = 1; a < num; a++) {
            if (flag == 1) break;
            if (num % a != 0) continue;
            for (int b = a + 1; b < num; b++) {
                if (flag == 1) break;
                if (num % b != 0) continue;
                for (int c = b + 1; c < num; c++) {
                    if (flag == 1) break;
                    if (num % c != 0) continue;
                    for (int d = c + 1; d <= num; d++) {
                        if (num % d != 0) continue;
                        if ((a + b + c + d) % num == 0) {
                            flag = 1;
                            break;
                        }
                    }
                }
            }
        }
        cout << (flag ? "Yes\n" : "No\n");
    }
    return 0;
}

#include <iostream>

using namespace std;

int k, num, flag;

int main() {

cin >> k;

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

cin >> num;

flag = 0;

for (int a = 1; a < num; a++) {

if (flag == 1) break;

if (num % a != 0) continue;

for (int b = a + 1; b < num; b++) {

if (flag == 1) break;

if (num % b != 0) continue;

for (int c = b + 1; c < num; c++) {

if (flag == 1) break;

if (num % c != 0) continue;

for (int d = c + 1; d <= num; d++) {

if (num % d != 0) continue;

if ((a + b + c + d) % num == 0) {

flag = 1;

break;

}

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

}

return 0;

}