liuchuo – 第4页 – 柳婼の blog

1119 胖达与盆盆奶 – PAT乙级真题

大熊猫，俗称“胖达”，会排队吃盆盆奶。它们能和谐吃奶的前提，是它们认为盆盆奶的分配是“公平”的，即：更胖的胖达能吃到更多的奶，等胖的胖达得吃到一样多的奶。另一方面，因为它们是排好队的，所以每只胖达只能看到身边胖达的奶有多少，如果觉得不公平就会抢旁边小伙伴的奶吃。

已知一只胖达每次最少要吃 200 毫升的奶，当另一份盆盆奶多出至少 100 毫升的时候，它们才能感觉到是“更多”了，否则没感觉。

现在给定一排胖达的体重，请你帮饲养员计算一下，在保持给定队形的前提下，至少应该准备多少毫升的盆盆奶？

输入格式：

输入首先在第一行给出正整数 n（≤10^4），为胖达的个数。随后一行给出 n 个正整数，表示 n 只胖达的体重（公斤）。每个数值是不超过 200 的正整数，数字间以空格分隔。

输出格式：

在一行中输出至少应该准备多少毫升的盆盆奶。

输入样例：

10
180 160 100 150 145 142 138 138 138 140

输出样例：

3000

样例解释：

盆盆奶的分配量顺序为：

400 300 200 500 400 300 200 200 200 300

分析：使用数组A记录每个熊猫的体重，L[i]表示第i个数的右边有几个连续下降的数（过程中可以有相等的数字，但是只记录不重复的数字的数量），R[i]则表示第i个数左边有几个连续下降的数（也是可以相等但是不记录）。从左到右遍历每一个i，然后看一下它右边有多少个连续下降的数。从右到左同理，看一下i的左边有多少个连续下降的数。对于每一只熊猫，取L[i]和R[i]中较大的那个数*100+200，就是这只熊猫应该喝的牛奶的毫升数。最后计算他们的总和就可以啦。

#include <iostream>
using namespace std;
int n, ans, A[10005], L[10005], R[10005];
int main(){
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> A[i];
    for (int i = 1; i < n; i++) {
        int j = i;
        while(j + 1 <= n && A[j] >= A[j + 1]) {
            if (A[j] > A[j + 1]) ++L[i];
            ++j;
        }
    }
    for (int i = n; i > 1; i--) {
        int j = i;
        while(j - 1 >= 1 && A[j] >= A[j - 1]) {
            if (A[j] > A[j - 1]) ++R[i];
            --j;
        }
    }
    for (int i = 1; i <= n; i++) ans += max(L[i], R[i]) * 100 + 200;
    cout << ans;
    return 0;
}

#include <iostream>

using namespace std;

int n, ans, A[10005], L[10005], R[10005];

int main(){

cin >> n;

for (int i = 1; i <= n; i++) cin >> A[i];

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

int j = i;

while(j + 1 <= n && A[j] >= A[j + 1]) {

if (A[j] > A[j + 1]) ++L[i];

++j;

}

for (int i = n; i > 1; i--) {

int j = i;

while(j - 1 >= 1 && A[j] >= A[j - 1]) {

if (A[j] > A[j - 1]) ++R[i];

--j;

}

for (int i = 1; i <= n; i++) ans += max(L[i], R[i]) * 100 + 200;

cout << ans;

return 0;

}

1118 如需挪车请致电 – PAT乙级真题

上图转自新浪微博。车主用一系列简单计算给出了自己的电话号码，即：

2/2=1、3+2=5、√9=3、√9=3、0%=0、叁=3、5−2=3、9/3=3、1×3=3、2^3=8、8/2=4，最后得到的电话号码就是 153 3033 3384。

本题就请你写个程序自动完成电话号码的转换，以帮助那些不会计算的人。

输入格式：

输入用 11 行依次给出 11 位数字的计算公式，每个公式占一行。这里仅考虑以下几种运算：加（+）、减（-）、乘（*）、除（/）、取余（%，注意这不是上图中的百分比）、开平方根号（sqrt）、指数（^）和文字（即 0 到 9 的全小写汉语拼音，如 ling 表示 0）。运算符与运算数之间无空格，运算数保证是不超过 1000 的非负整数。题目保证每个计算至多只有 1 个运算符，结果都是 1 位整数。

输出格式：

在一行中给出电话号码，数字间不要空格。

输入样例：

2/2
3+2
sqrt9
sqrt9
6%2
san
5-2
9/3
15330333384

输出样例：

15330333384

分析：s存储初始字符串，c存储操作符（如果有的话）。A存储数字拼音转换成int型数字的映射。题目说”题目保证每个计算至多只有1个运算符”，那么可能没有运算符，可能只有纯数字运算数，如果s的长度为1，则直接输出。否则看一下是不是求根运算，即前几位是”sqrt”。都不是的话，就要把数字分成三个部分，数字部分a和b、运算符c。然后根据具体是什么运算符，进行相对应的计算。

#include <iostream>
#include <map>
#include <cmath>
#include <string>
using namespace std;
string s, c;
map<string,int> A = {{"ling", 0}, {"yi", 1}, {"er", 2}, {"san", 3}, {"si", 4}, {"wu", 5}, {"liu", 6}, {"qi", 7}, {"ba", 8}, {"jiu", 9}};
int main() {
    for (int I = 0; I < 11; I++) {
        cin >> s;
        if (s.size() == 1) cout << s;
        else if (s[0] == 's' && s[1] == 'q') cout << sqrt(stoi(s.substr(4)));
        else if (A.count(s)) cout << A[s];
        else {
            int a = 0, b = 0, i = 0;
            while(i < s.size() && isdigit(s[i])) a = a * 10 + s[i++] - '0';
            c = s[i++];
            while(i < s.size()) b = b * 10 + s[i++] - '0';
            if (c == "+") cout << a + b;
            else if (c == "-") cout << a - b;
            else if (c == "*") cout << a * b;
            else if (c == "/") cout << a / b;
            else if (c == "%") cout << a % b;
            else cout << pow(a, b);
        }
    }
    return 0;
}

#include <iostream>

#include <map>

#include <cmath>

#include <string>

using namespace std;

string s, c;

map<string,int> A = {{"ling", 0}, {"yi", 1}, {"er", 2}, {"san", 3}, {"si", 4}, {"wu", 5}, {"liu", 6}, {"qi", 7}, {"ba", 8}, {"jiu", 9}};

int main() {

for (int I = 0; I < 11; I++) {

cin >> s;

if (s.size() == 1) cout << s;

else if (s[0] == 's' && s[1] == 'q') cout << sqrt(stoi(s.substr(4)));

else if (A.count(s)) cout << A[s];

else {

int a = 0, b = 0, i = 0;

while(i < s.size() && isdigit(s[i])) a = a * 10 + s[i++] - '0';

c = s[i++];

while(i < s.size()) b = b * 10 + s[i++] - '0';

if (c == "+") cout << a + b;

else if (c == "-") cout << a - b;

else if (c == "*") cout << a * b;

else if (c == "/") cout << a / b;

else if (c == "%") cout << a % b;

else cout << pow(a, b);

}

return 0;

}

1117 数字之王 – PAT乙级真题

给定两个正整数 N1<N2。把从 N1 到 N2 的每个数的各位数的立方相乘，再将结果的各位数求和，得到一批新的数字，再对这批新的数字重复上述操作，直到所有数字都是 1 位数为止。这时哪个数字最多，哪个就是“数字之王”。

例如 N1=1 和 N2=10 时，第一轮操作后得到 { 1, 8, 9, 10, 8, 9, 10, 8, 18, 0 }；第二轮操作后得到 { 1, 8, 18, 0, 8, 18, 0, 8, 8, 0 }；第三轮操作后得到 { 1, 8, 8, 0, 8, 8, 0, 8, 8, 0 }。所以数字之王就是 8。

本题就请你对任意给定的 N1<N2 求出对应的数字之王。

输入格式：

输入在第一行中给出两个正整数 0<N1<N2≤10^3，其间以空格分隔。

输出格式：

首先在一行中输出数字之王的出现次数，随后第二行输出数字之王。例如对输入 1 10 就应该在两行中先后输出 6 和 8。如果有并列的数字之王，则按递增序输出。数字间以 1 个空格分隔，行首尾不得有多余空格。

输入样例：

10 14

输出样例：

2
0 8

分析：使用f变量控制是否继续重复执行题目中的操作，1表示继续执行，0表示停止。B中存储数字0-9出现的次数，maxn存储数字之王出现的次数。首先将N1到N2的值存储在数组A中，如果N2超过9，表示有数字不是个位数。循环过程中按照题意模拟。然后把所有的个位数输出现了几次，记录在数组B中。把出现次数最多的所有的数存储在数组ans中，最后按顺序输出它们。

#include <iostream>
#include <vector>
using namespace std;
int N1, N2, f, A[1005], B[10], maxn;
vector<int> ans;
signed main(){
    cin >> N1 >> N2;
    for (int i = N1; i <= N2; i++) A[i] = i;
    if (N2 > 9) f = 1;
    while (f) {
        f = 0;
        for (int i = N1; i <= N2; i++) {
            if (!A[i]) continue;
            int t1 = 1, t2 = A[i];
            while(t2) {
                t1 *= (t2 % 10) * (t2 % 10) * (t2 % 10);
                t2 /= 10;
            }
            while(t1) {
                t2 += t1 % 10;
                t1 /= 10;
            }
            if (t2 > 9) f = 1;
            A[i] = t2;
        }
    }
    for (int i = N1; i <= N2; i++) {
         B[A[i]]++;
         maxn = max(maxn, B[A[i]]);
    }
    for (int i = 0 ; i < 10; i++) 
        if (B[i] == maxn) ans.push_back(i);
    cout << maxn << '\n';
    for (int i = 0; i < ans.size(); i++) {
        if (i) cout << ' ';
        cout << ans[i];
    }
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int N1, N2, f, A[1005], B[10], maxn;

vector<int> ans;

signed main(){

cin >> N1 >> N2;

for (int i = N1; i <= N2; i++) A[i] = i;

if (N2 > 9) f = 1;

while (f) {

f = 0;

for (int i = N1; i <= N2; i++) {

if (!A[i]) continue;

int t1 = 1, t2 = A[i];

while(t2) {

t1 *= (t2 % 10) * (t2 % 10) * (t2 % 10);

t2 /= 10;

}

while(t1) {

t2 += t1 % 10;

t1 /= 10;

}

if (t2 > 9) f = 1;

A[i] = t2;

}

for (int i = N1; i <= N2; i++) {

B[A[i]]++;

maxn = max(maxn, B[A[i]]);

}

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

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

cout << maxn << '\n';

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

if (i) cout << ' ';

cout << ans[i];

}

return 0;

}

1116 多二了一点 – PAT乙级真题

若一个正整数有 2n 个数位，后 n 个数位组成的数恰好比前 n 个数位组成的数多 2，则称这个数字“多二了一点”。如 24、6668、233235 等都是多二了一点的数字。
给定任一正整数，请你判断它有没有多二了那么一点。

输入格式：

输入在第一行中给出一个正整数 N（≤101000）。

输出格式：

在一行中根据情况输出下列之一：

如果输入的整数没有偶数个数位，输出 Error: X digit(s)，其中 X 是 N 的位数；
如果是偶数位的数字，并且是多二了一点，输出 Yes: X - Y = 2，其中 X 是后一半数位组成的数，Y 是前一半数位组成的数。注意：为了让题目简单，输入保证此时 Y 的个位数不大于 7。
如果是偶数位的数字，但并不是多二了一点，输出 No: X - Y != 2，其中 X 是后一半数位组成的数，Y 是前一半数位组成的数。

输入样例 1：

233235

输出样例 1：

Yes: 235 – 233 = 2

输入样例 2：

5678912345

输出样例 2：

No: 12345 – 56789 != 2

输入样例 3：

2331235

输出样例 3：

Error: 7 digit(s)

分析：使用string类型存储数字，使用Left和Right分别存储这个数的前n个数的和、后n个数的和。由于是计算差值，所以不需要让字符数字减去’0’。如果数的长度为奇数，就直接输出相对应的Error语句。否则按对应条件输出即可。s.substr(a)表示从s的第a位开始截取到最后，s.substr(a,b)表示从s的第a位开始截取长度位b的字符串。

#include <iostream>
using namespace std;
string s;
int Left, Right;
int main(){
    cin >> s;
    if (s.size() & 1) cout << "Error: " << s.size() << " digit(s)";
    else {
        for (int i = 0; i < s.size(); i++) {
            if (i < s.size() / 2) Left += s[i];
            else Right += s[i];
        }
        if (Left + 2 == Right) cout << "Yes: " << s.substr(s.size() / 2 ) << " - " << s.substr(0, s.size() / 2) << " = 2";
        else cout << "No: " << s.substr(s.size() / 2) << " - " << s.substr(0, s.size() / 2) << " != 2";
    }
    return 0;
}

#include <iostream>

using namespace std;

string s;

int Left, Right;

int main(){

cin >> s;

if (s.size() & 1) cout << "Error: " << s.size() << " digit(s)";

else {

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

if (i < s.size() / 2) Left += s[i];

else Right += s[i];

}

if (Left + 2 == Right) cout << "Yes: " << s.substr(s.size() / 2 ) << " - " << s.substr(0, s.size() / 2) << " = 2";

else cout << "No: " << s.substr(s.size() / 2) << " - " << s.substr(0, s.size() / 2) << " != 2";

}

return 0;

}

1115 裁判机 – PAT乙级真题

有一种数字游戏的规则如下：首先由裁判给定两个不同的正整数，然后参加游戏的几个人轮流给出正整数。要求给出的数字必须是前面已经出现的某两个正整数之差，且不能等于之前的任何一个数。游戏一直持续若干轮，中间有写重复或写错的人就出局。

本题要求你实现这个游戏的裁判机，自动判断每位游戏者给出的数字是否合法，以及最后的赢家。

输入格式：

输入在第一行中给出 2 个初始的正整数，保证都在 [1,10^5] 范围内且不相同。

第二行依次给出参加比赛的人数 N（2≤N≤10）和每个人都要经历的轮次数 M（2≤M≤10^3）。

以下 N 行，每行给出 M 个正整数。第 i 行对应第 i 个人给出的数字（i=1,⋯,N）。游戏顺序是从第 1 个人给出第 1 个数字开始，每人顺次在第 1 轮给出自己的第 1 个数字；然后每人顺次在第 2 轮给出自己的第 2 个数字，以此类推。

输出格式：

如果在第 k 轮，第 i 个人出局，就在一行中输出 Round #k: i is out.。出局人后面给出的数字不算；同一轮出局的人按编号增序输出。直到最后一轮结束，在一行中输出 Winner(s): W1 W2 ... Wn，其中 W1 ... Wn 是最后的赢家编号，按增序输出。数字间以 1 个空格分隔，行末不得有多余空格。如果没有赢家，则输出 No winner.。

输入样例 1：

101 42
4 5
59 34 67 9 7
17 9 8 50 7
25 92 43 26 37
76 51 1 41 40

输出样例 1：

Round #4: 1 is out.
Round #5: 3 is out.
Winner(s): 2 4

输入样例 2：

42 101
4 5
59 34 67 9 7
17 9 18 50 49
25 92 58 1 39
102 32 2 6 41

输出样例 2：

Round #1: 4 is out.
Round #3: 2 is out.
Round #4: 1 is out.
Round #5: 3 is out.
No winner.

分析：使用二维数组A存储每一轮每一个玩家出的数，使用flag2标记是否有人获胜，mark数组中标记某个数是否出现过，out[i]表示第i个人已经出局，used数组中存储已经出现过的数。题目要求是给出的数字必须是前面已经出现的某两个正整数之差，可以转换为现在这个人出的数字，加上已经出过的某个数，看是不是等于另一个已经出过的数字。对于每一轮我们遍历所有人，如果这个人已经出局，则跳过。如果这个数加所有出现过数字，不等于另外一个已经出现过的数字，或者这个数已经出现过了，那么这个人淘汰，否则mark记录一下这个数字已经被使用过，并且添加到已经使用过的数组used中。最后遍历输出赢家，如果没有赢家就输出”No winner.”。

#include <iostream>
#include <vector>
using namespace std;
int N, M, flag2, A[11][1001], mark[200005], out[11];
vector<int> used(2);
int main(){
    cin >> used[0] >> used[1];
    mark[used[0]] = mark[used[1]] = 1;
    cin >> N >> M;
    for (int i = 1; i <= N; i++)
    for (int j = 1; j <= M; j++) cin >> A[i][j];
    for (int i = 1; i <= M; i++) 
        for (int j = 1; j <= N; j++) {
            if (out[j]) continue;
            int flag = 0;
            if (mark[A[j][i]]) flag = -1;
            for (auto it : used) {
                if (mark[it + A[j][i]] == 1) {
                    mark[A[j][i]] = 1;
                    flag++;
                    used.push_back(A[j][i]);
                    break;
                }
            }
            if (flag <= 0) {
                out[j] = 1;
                cout << "Round #" << i << ": " << j << " is out.\n";
            }
        }
    for (int i = 1; i <= N; i++) {
        if (!out[i]) {
            if(!flag2) {
                cout << "Winner(s):";
                flag2 = 1;
            }
            cout << " " << i;
        }
    }
    if (!flag2) cout << "No winner.";
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int N, M, flag2, A[11][1001], mark[200005], out[11];

vector<int> used(2);

int main(){

cin >> used[0] >> used[1];

mark[used[0]] = mark[used[1]] = 1;

cin >> N >> M;

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

for (int j = 1; j <= M; j++) cin >> A[i][j];

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

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

if (out[j]) continue;

int flag = 0;

if (mark[A[j][i]]) flag = -1;

for (auto it : used) {

if (mark[it + A[j][i]] == 1) {

mark[A[j][i]] = 1;

flag++;

used.push_back(A[j][i]);

break;

}

if (flag <= 0) {

out[j] = 1;

cout << "Round #" << i << ": " << j << " is out.\n";

}

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

if (!out[i]) {

if(!flag2) {

cout << "Winner(s):";

flag2 = 1;

}

cout << " " << i;

}

if (!flag2) cout << "No winner.";

return 0;

}

1114 全素日 – PAT乙级真题

以上图片来自新浪微博，展示了一个非常酷的“全素日”：2019年5月23日。即不仅20190523本身是个素数，它的任何以末尾数字3结尾的子串都是素数。

本题就请你写个程序判断一个给定日期是否是“全素日”。

输入格式：

输入按照 yyyymmdd 的格式给出一个日期。题目保证日期在0001年1月1日到9999年12月31日之间。

输出格式：

从原始日期开始，按照子串长度递减的顺序，每行首先输出一个子串和一个空格，然后输出 Yes，如果该子串对应的数字是一个素数，否则输出 No。如果这个日期是一个全素日，则在最后一行输出 All Prime!。

输入样例 1：

20190523

输出样例 1：

20190523 Yes
0190523 Yes
190523 Yes
90523 Yes
0523 Yes
523 Yes
23 Yes
3 Yes
All Prime!

输入样例 2：

20191231

输出样例 2：

20191231 Yes
0191231 Yes
191231 Yes
91231 No
1231 Yes
231 No
31 Yes
1 No

分析：使用num储存合数的个数，如果最后num为0，则表示要输出”All Prime!”。使用string s存储输入的数字。可以使用while循环，每次查询当前数值是不是素数，然后使用erase()函数删除第一个数字，如此循环到s长度为0。可以直接使用函数stoi()，将string转化成int类型。每次我们判断当前的数是不是素数，并直接输出。

#include <iostream>
#include <cmath>
using namespace std;
int num;
string s;
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 >> s;
    num = s.size();
    while (s.size()) {
        cout << s << ' ' << (is_prime(stoi(s)) ? "Yes" : "No") << '\n';
        if (is_prime(stoi(s))) --num;
        s.erase(s.begin());
    }
    if (num == 0) cout << "All Prime!";
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int num;

string s;

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

num = s.size();

while (s.size()) {

cout << s << ' ' << (is_prime(stoi(s)) ? "Yes" : "No") << '\n';

if (is_prime(stoi(s))) --num;

s.erase(s.begin());

}

if (num == 0) cout << "All Prime!";

return 0;

}