liuchuo – 第12页 – 柳婼の blog

1107 老鼠爱大米 – PAT乙级真题

翁恺老师曾经设计过一款 Java 挑战游戏，叫“老鼠爱大米”（或许因为他的外号叫“胖胖鼠”）。每个玩家用 Java 代码控制一只鼠，目标是抢吃尽可能多的大米让自己变成胖胖鼠，最胖的那只就是冠军。

因为游戏时间不能太长，我们把玩家分成 N 组，每组 M 只老鼠同场竞技，然后从 N 个分组冠军中直接选出最胖的冠军胖胖鼠。现在就请你写个程序来得到冠军的体重。

输入格式：

输入在第一行中给出 2 个正整数：N（≤100）为组数，M（≤10）为每组玩家个数。随后 N 行，每行给出一组玩家控制的 M 只老鼠最后的体重，均为不超过 10⁴ 的非负整数。数字间以空格分隔。

输出格式：

首先在第一行顺次输出各组冠军的体重，数字间以 1 个空格分隔，行首尾不得有多余空格。随后在第二行输出冠军胖胖鼠的体重。

输入样例：

3 5
62 53 88 72 81
12 31 9 0 2
91 42 39 6 48

输出样例：

88 31 91
91

分析：d记录小组最胖老鼠，D记录总胖冠军鼠。直接取最大值就可以了~

#include <iostream>
using namespace std;
int n, m, t, d, D;
int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        d = 0;
        for (int j = 0; j < m; j++) {
            cin >> t;
            d = max(d, t);
        }
        cout << d << ((i == n - 1) ? '\n' : ' ');
        D = max(D, d);
    }
    cout << D;
    return 0;
}

#include <iostream>

using namespace std;

int n, m, t, d, D;

int main() {

cin >> n >> m;

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

d = 0;

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

cin >> t;

d = max(d, t);

}

cout << d << ((i == n - 1) ? '\n' : ' ');

D = max(D, d);

}

cout << D;

return 0;

}

1106 2019数列 – PAT乙级真题

把 2019 各个数位上的数字 2、0、1、9 作为一个数列的前 4 项，用它们去构造一个无穷数列，其中第 n（>4）项是它前 4 项之和的个位数字。例如第 5 项为 2，因为 2+0+1+9=12，个位数是 2。

本题就请你编写程序，列出这个序列的前 n 项。

输入格式：

输入给出正整数 n（≤1000）。

输出格式：

在一行中输出数列的前 n 项，数字间不要有空格。

输入样例：

输出样例：

2019224758

分析：数组a[4]中始终保留前4项数字，如果n小于4，就输出前n项；如果n大于等于4，就先输出前四项，然后不断累加a[4]所有元素的值，并对10取余得到个位数字，输出后将a[4]替换为新的前4项方便下一次累加取余~

#include <iostream>
using namespace std;
int n, sum, a[4] = {2, 0, 1, 9};
int main() {
    cin >> n;
    for (int i = 0; i < min(4, n); i++) cout << a[i];
    for (int i = 4; i < n; i++) {
        sum = (a[0] + a[1] + a[2] + a[3]) % 10;
        cout << sum;
        a[0] = a[1], a[1] = a[2], a[2] = a[3], a[3] = sum;
    }
    return 0;
}

#include <iostream>

using namespace std;

int n, sum, a[4] = {2, 0, 1, 9};

int main() {

cin >> n;

for (int i = 0; i < min(4, n); i++) cout << a[i];

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

sum = (a[0] + a[1] + a[2] + a[3]) % 10;

cout << sum;

a[0] = a[1], a[1] = a[2], a[2] = a[3], a[3] = sum;

}

return 0;

}

1105 链表合并 – PAT乙级真题

给定两个单链表 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 (≤105)，即给定的结点总数。一个结点的地址是一个 5 位数的非负整数，空地址 NULL 用 -1 表示。

随后 N 行，每行按以下格式给出一个结点的信息：

Address Data Next

其中 Address 是结点的地址，Data 是不超过 105 的正整数，Next 是下一个结点的地址。题目保证没有空链表，并且较长的链表至少是较短链表的两倍长。

输出格式：

按顺序输出结果链表，每个结点占一行，格式与输入相同。

输入样例：

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

输出样例：

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

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

}

1104 天长地久 – PAT乙级真题

“天长地久数”是指一个 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。

输入样例：

2
6 45
7 80

输出样例：

Case 1
10 189999
10 279999
10 369999
10 459999
10 549999
10 639999
10 729999
10 819999
10 909999
Case 2
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;

}

1103 缘分数 – PAT乙级真题

所谓缘分数是指这样一对正整数 a 和 b，其中 a 和它的小弟 a−1 的立方差正好是另一个整数 c 的平方，而 c 正好是 b 和它的小弟 b−1 的平方和。例如 83−73=169=132，而 13=32+22，于是 8 和 3 就是一对缘分数。

给定 a 所在的区间 [m,n]，是否存在缘分数？

输入格式：

输入给出区间的两个端点 0<m<n≤25000，其间以空格分隔。

输出格式：

按照 a 从小到大的顺序，每行输出一对缘分数，数字间以空格分隔。如果无解，则输出 No Solution。

输入样例 1：

8 200

输出样例 1：

8 3
105 10

输入样例 2：

9 100

输出样例 2：

No Solution

分析：遍历m到n区间中的每一个数a，先判断a和它的小弟a-1的立方差d是不是一个平方数，sqrt(d) * sqrt(d) == d则说明其是一个平方数，然后从1开始枚举这个数是不是另外两个数b和b-1的平方和，如果b和b-1的平方和等于a和a-1的立方差的平方根，则输出a和b，并将flag置为1，如果最后flag都为0，则输出No Solution~
这里用映射map<long long, long long> record记录了每一个数b和b-1的平方和的结果，后续如果有碰到之前计算过的平方和，就直接调用map中的结果，不用再次计算~

#include <iostream>
#include <map>
#include <cmath>
using namespace std;
long long m, n, a, b, d, c, flag, temp;
map<long long, long long> record;
int main() {
    cin >> m >> n;
    for (a = m; a <= n; a++) {
        d = a * a * a - (a-1) * (a-1) * (a-1), c = sqrt(d);
        if (c * c != d) continue;
        for (long long b = 1; b < c; b++) {
            if (record.count(b)) temp = record[b];
            else {
                temp = b * b + (b - 1) * (b - 1);
                record[b] = temp;
            }
            if (temp == c) {
                cout << a << ' ' << b << '\n';
                flag = 1;
                break;
            }
        }
    }
    if (!flag) cout << "No Solution";
    return 0;
}

#include <iostream>

#include <map>

#include <cmath>

using namespace std;

long long m, n, a, b, d, c, flag, temp;

map<long long, long long> record;

int main() {

cin >> m >> n;

for (a = m; a <= n; a++) {

d = a * a * a - (a-1) * (a-1) * (a-1), c = sqrt(d);

if (c * c != d) continue;

for (long long b = 1; b < c; b++) {

if (record.count(b)) temp = record[b];

else {

temp = b * b + (b - 1) * (b - 1);

record[b] = temp;

}

if (temp == c) {

cout << a << ' ' << b << '\n';

flag = 1;

break;

}

if (!flag) cout << "No Solution";

return 0;

}

1102 教超冠军卷 – PAT乙级真题

“教育超市”是拼题 A 系统的一个衍生产品，发布了各种试卷和练习供用户选购。在试卷列表中，系统不仅列出了每份试卷的单价，还显示了当前的购买人次。本题就请你根据这些信息找出教育超市所有试卷中的销量（即购买人次）冠军和销售额冠军。

输入格式：

输入首先在第一行中给出一个正整数 N（≤10⁴），随后 N 行，每行给出一份卷子的独特 ID （由小写字母和数字组成的、长度不超过8位的字符串）、单价（为不超过 100 的正整数）和购买人次（为不超过 10⁶ 的非负整数）。

输出格式：

在第一行中输出销量冠军的 ID 及其销量，第二行中输出销售额冠军的 ID 及其销售额。同行输出间以一个空格分隔。题目保证冠军是唯一的，不存在并列。

输入样例：

4
zju007 39 10
pku2019 9 332
pat2018 95 79
qdu106 19 38

输出样例：

pku2019 332
pat2018 7505

分析：maxN记录最多销量，ansN记录销量冠军的ID；销售额等于单价*购买人次，maxS记录最大销售额，ansS记录销售额冠军的ID

#include <iostream>
using namespace std;
int n, a, b, maxN = -1, maxS = -1;
string name, ansN, ansS; 
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> name >> a >> b;
        if (b > maxN) {
            maxN = b;
            ansN = name;
        }
        if (a * b > maxS) {
            maxS = a * b;
            ansS = name;
        }
    }
    cout << ansN << ' ' << maxN << '\n' << ansS << ' ' << maxS;
    return 0;
}

#include <iostream>

using namespace std;

int n, a, b, maxN = -1, maxS = -1;

string name, ansN, ansS;

int main() {

cin >> n;

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

cin >> name >> a >> b;

if (b > maxN) {

maxN = b;

ansN = name;

}

if (a * b > maxS) {

maxS = a * b;

ansS = name;

}

cout << ansN << ' ' << maxN << '\n' << ansS << ' ' << maxS;

return 0;

}