PTA乙级(计划寒假刷完)
写在前面，刷完PTA上的（PAT (Basic Level) Practice (中文)题目，共110题
如果我的时候有磕磕绊绊，会写题解或者tips
tip**:不要漂亮，要快(大不了最后格式化)；仔细阅读问题，验证每一个例子！
有一个遗憾1055 ：23/25我觉得理解问题有很多问题，因为按照我的理解例子是错误的，蛤蜊
其实我打算先刷乙级，再刷甲级(因为乙级是中文)
结果花了太长时间
1001 杀人不偿命(3)n 1)猜想(15)
卡拉兹(Callatz)猜想：
对任何正整数 n，若为偶数，则将其砍掉一半；若为奇数，则将其砍掉 (3n 1) 砍掉一半。这样一次又一次地被砍掉，最后必须在某一步得到 n=1。卡拉兹在 1950 在2000年的世界数学家大会上宣布了这一猜想。据说耶鲁大学的师生们一起动员，试图证明这个看似愚蠢和天真的命题。结果，学生们无意中学习，只有一颗心 (3n 1)以至于有人说这是阴谋，卡拉兹故意延缓美国数学教学和科研的进展……
我们今天的话题不是证明卡拉兹猜想，而是不超过给定的任何一个 1000 的正整数 n，简单数一下需要多少步(砍几次)才能得到。 n=1？
输入格式： 包括每个测试输入 1 一个测试用例，即给出正整数 n 的值。
输出格式： 输出从 n 计算到 1 所需步数。
输入样例： 3 输出样例： 5
#include <bits/stdc .h> using namespace std; int main() {
int n; cin >> n; int ans = 0; while (n != 1) {
if (n % 2 == 0) n = n / 2; else n = (3 * n 1) / 2; ans ; } cout << ans << endl; } 1002 写这个数字(20)
读正整数 n，计算每个数字之和，用汉语拼音写出每个数字。
输入格式： 包括每个测试输入 1 测试用例，即给出自然数 n 值。这里保证 n 小于 10 100 。
输出格式： 输出一行 n 每个人的数字之和，拼音数字之间都有 1 但是一行中最后一个拼音数字没有空格。
输入样例： 1234567890987654321123456789 输出样例： yi san wu
#include <bits/stdc .h> using namespace std; string a[11] = {
"ling", "yi", "er", "san", "si", "wu", "liu", "qi", "ba", "jiu"};
int main() {
string str;
cin >> str;
int ans = 0;
for (int i = 0; i < str.size(); i++) {
ans += (str[i] - '0');
}
str = to_string(ans);
for (int i = 0; i < str.size(); i++) {
if (i != 0) cout << " ";
cout << a[str[i] - '0'];
}
}
1003 我要通过！(20)
“答案正确”是自动判题系统给出的最令人欢喜的回复。本题属于 PAT 的“答案正确”大派送 —— 只要读入的字符串满足下列条件，系统就输出“答案正确”，否则输出“答案错误”。
得到“答案正确”的条件是：
字符串中必须仅有 P、 A、 T这三种字符，不可以包含其它字符； 任意形如 xPATx 的字符串都可以获得“答案正确”，其中 x 或者是空字符串，或者是仅由字母 A 组成的字符串； 如果 aPbTc 是正确的，那么 aPbATca 也是正确的，其中 a、 b、 c 均或者是空字符串，或者是仅由字母 A 组成的字符串。 现在就请你为 PAT 写一个自动裁判程序，判定哪些字符串是可以获得“答案正确”的。
输入格式： 每个测试输入包含 1 个测试用例。第 1 行给出一个正整数 n (≤10)，是需要检测的字符串个数。接下来每个字符串占一行，字符串长度不超过 100，且不包含空格。
输出格式： 每个字符串的检测结果占一行，如果该字符串可以获得“答案正确”，则输出 YES，否则输出 NO。
输入样例： 10 PAT PAAT AAPATAA AAPAATAAAA xPATx PT Whatever APAAATAA APT APATTAA 输出样例： YES YES YES YES NO NO NO NO NO NO
题解&tips:
三个条件，第一个条件好懂，第二个条件中“xPATx”的意思为当‘P’和’T‘中有一个’A‘时，’P‘前面的’A‘的个数和’T‘后的相等。（并不是前后有任意个，要仔细看）
第三个条件的意思中”如果
aPbTc是正确的，那么aPbATca也是正确的“，可以规范为：已知前两个条件可以判断正确的字符串则按照上面的拓展规则，拓展的字符串也是正确的。设’P‘之前的’A’的个数为x，‘P’和‘T’之前的为b，‘T’之后为x，若 x 个‘A’ + ‘P’ + b个‘A‘ + T’ + x 个‘A’ （暂写为 xPbTx）为正确，那么xP(b + 1)T(x + x)也为正确的。推广为：xP(1 + s)T(x + s*x)
其中有点模糊意思的（我语感的问题）：“其中
a、b、c均或者是空字符串，或者是仅由字母A组成的字符串”意思为三个部分单独为 要不 空，要不多个’A‘
#include <bits/stdc++.h>
using namespace std;
bool is(string str) {
for (int i = 0; i < str.size(); i++) {
if (str[i] != 'A' && str[i] != 'P' && str[i] != 'T') {
return 0;
}
}
int pos1 = 0, pos2 = 0, cnt1 = 0, cnt2 = 0;
for (int i = 0; i < str.size(); i++) {
if (str[i] == 'P') pos1 = i, cnt1++;
if (str[i] == 'T') pos2 = i, cnt2++;
}
if (cnt1 > 1 || cnt2 > 1) return 0;
if (pos2 <= pos1 + 1) return 0;
int x = pos1;
int b = pos2 - pos1 - 1;
int y = str.length() - pos2 - 1;
if (y == b * x) return 1;
else return 0;
}
int main() {
int n;
cin >> n;
while (n--) {
string str;
cin >> str;
if (is(str)) cout << "YES\n";
else cout << "NO\n";
}
}
1004 成绩排名(20)
读入 n（>0）名学生的姓名、学号、成绩，分别输出成绩最高和成绩最低学生的姓名和学号。
输入格式： 每个测试输入包含 1 个测试用例，格式为
第 1 行：正整数 n 第 2 行：第 1 个学生的姓名 学号 成绩 第 3 行：第 2 个学生的姓名 学号 成绩 … … … 第 n+1 行：第 n 个学生的姓名 学号 成绩 其中姓名和学号均为不超过 10 个字符的字符串，成绩为 0 到 100 之间的一个整数，这里保证在一组测试用例中没有两个学生的成绩是相同的。
输出格式： 对每个测试用例输出 2 行，第 1 行是成绩最高学生的姓名和学号，第 2 行是成绩最低学生的姓名和学号，字符串间有 1 空格。
输入样例： 3 Joe Math990112 89 Mike CS991301 100 Mary EE990830 95 输出样例： Mike CS991301 Joe Math990112
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e5 + 10;
struct stu {
string name;
string xue;
int num;
} a[MAX];
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i].name >> a[i].xue >> a[i].num;
}
sort(a, a + n, [](stu a, stu b) {
return a.num > b.num;
});
cout << a[0].name << " " << a[0].xue << endl;
cout << a[n - 1].name << " " << a[n - 1].xue << endl;
}
1005 继续(3n+1)猜想(25)
卡拉兹(Callatz)猜想已经在1001中给出了描述。在这个题目里，情况稍微有些复杂。
当我们验证卡拉兹猜想的时候，为了避免重复计算，可以记录下递推过程中遇到的每一个数。例如对 n=3 进行验证的时候，我们需要计算 3、5、8、4、2、1，则当我们对 n=5、8、4、2 进行验证的时候，就可以直接判定卡拉兹猜想的真伪，而不需要重复计算，因为这 4 个数已经在验证3的时候遇到过了，我们称 5、8、4、2 是被 3“覆盖”的数。我们称一个数列中的某个数 n 为“关键数”，如果 n 不能被数列中的其他数字所覆盖。
现在给定一系列待验证的数字，我们只需要验证其中的几个关键数，就可以不必再重复验证余下的数字。你的任务就是找出这些关键数字，并按从大到小的顺序输出它们。
输入格式： 每个测试输入包含 1 个测试用例，第 1 行给出一个正整数 K (<100)，第 2 行给出 K 个互不相同的待验证的正整数 n (1<n≤100)的值，数字间用空格隔开。
输出格式： 每个测试用例的输出占一行，按从大到小的顺序输出关键数字。数字间用 1 个空格隔开，但一行中最后一个数字后没有空格。
输入样例： 6 3 5 6 7 8 11 输出样例： 7 6
tips:仔细看题意
#include <bits/stdc++.h>
using namespace std;
const int MAX = 110;
int a[MAX];
bool flag[MAX];
void ishave(int n, int x) {
set<int> have;
while (x != 1) {
if (x % 2 == 1) {
x = (3 * x + 1) / 2;
} else {
x = x / 2;
}
have.insert(x);
}
for (int i = 0; i < n; i++) {
if (a[i] == x) continue;
if (have.find(a[i]) != have.end()) {
flag[i] = 1;
}
}
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int i = 0; i < n; i++) {
ishave(n, a[i]);
}
vector<int> ans;
for (int i = 0; i < n; i++) {
if (flag[i] == 0) ans.push_back(a[i]);
}
sort(ans.begin(), ans.end(), [](int a, int b) {
return a > b;
});
for (int i = 0; i < ans.size(); i++) {
if (i != 0) cout << " ";
cout << ans[i];
}
}
1006 换个格式输出整数(15)
让我们用字母 B 来表示“百”、字母 S 表示“十”，用 12…n 来表示不为零的个位数字 n（<10），换个格式来输出任一个不超过 3 位的正整数。例如 234 应该被输出为 BBSSS1234，因为它有 2 个“百”、3 个“十”、以及个位的 4。
输入格式： 每个测试输入包含 1 个测试用例，给出正整数 n（<1000）。
输出格式：在这里插入代码片 每个测试用例的输出占一行，用规定的格式输出 n。
输入样例 1： 234 输出样例 1： BBSSS1234 输入样例 2： 23 输出样例 2： SS123
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
int b = n / 100;
int s = n / 10 % 10;
int g = n % 10;
string ans = "";
ans += string(b, 'B');
ans += string(s, 'S');
for(int i = 1; i <= g; i++) {
ans += to_string(i);
}
cout << ans << endl;
}
1007 素数对猜想(20)
1007 素数对猜想 (20 分) 让我们定义d_n 为：d_n=p_(n+1) −p_n ，其中p_i是第i个素数。显然有d_1 =1，且对于n>1有d_n是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。
现给定任意正整数N(<10^5 )，请计算不超过N的满足猜想的素数对的个数。
输入格式: 输入在一行给出正整数N。
输出格式: 在一行中输出不超过N的满足猜想的素数对的个数。
输入样例: 20 输出样例: 4
#include <bits/stdc++.h>
using namespace std;
bool isp(int x) {
for (int i = 2; i <= x / i; i++) {
if (x % i == 0) return 0;
}
return 1;
}
const int MAX = 1e5 + 10;
int ans[MAX];
void init() {
int tmp = 0;
for (int i = 2; i + 2 < MAX; i++) {
if (isp(i) == 1 && isp(i + 2) == 1) tmp++;
ans[i + 2] = tmp;
}
}
int main() {
init();
int x;
cin >> x;
cout << ans[x] << endl;
}
1008 数组元素循环右移问题(20)
一个数组A中存有N（>0）个整数，在不允许使用另外数组的前提下，将每个整数循环向右移M（≥0）个位置，即将A中的数据由（A0 A1 ⋯A N−1）变换为（A N−M ⋯A N−1 A0 A 1 ⋯A N−M−1 ）（最后M个数循环移至最前面的M个位置）。如果需要考虑程序移动数据的次数尽量少，要如何设计移动的方法？
输入格式: 每个输入包含一个测试用例，第1行输入N（1≤N≤100）和M（≥0）；第2行输入N个整数，之间用空格分隔。
输出格式: 在一行中输出循环右移M位以后的整数序列，之间用空格分隔，序列结尾不能有多余空格。
输入样例: 6 2 1 2 3 4 5 6 输出样例: 5 6 1 2 3 4
#include <bits/stdc++.h>
using namespace std;
const int MAX = 110;
int a[MAX];
int main() {
int n, k;
cin >> n >> k;
k %= n;
for (int i = 1; i <= n; i++) cin >> a[i];
vector<int> ans;
for (int i = n - k + 1; i <= n; i++) ans.push_back(a[i]);
for (int i = 1; i <= n - k; i++) ans.push_back(a[i]);
for (int i = 0; i < ans.size(); i++) {
if (i != 0) cout << " ";
cout << ans[i];
}
}
1009 说反话(20)
给定一句英语，要求你编写程序，将句中所有单词的顺序颠倒输出。
输入格式： 测试输入包含一个测试用例，在一行内给出总长度不超过 80 的字符串。字符串由若干单词和若干空格组成，其中单词是由英文字母（大小写有区分）组成的字符串，单词之间用 1 个空格分开，输入保证句子末尾没有多余的空格。
输出格式： 每个测试用例的输出占一行，输出倒序后的句子。
输入样例： Hello World Here I Come 输出样例： Come I Here World Hello
#include <bits/stdc++.h>
using namespace std;
vector<string> ans;
int main() {
string str;
while (cin >> str) {
ans.push_back(str);
}
for (int i = ans.size() - 1; i >= 0; i--) {
if (i != ans.size() - 1) cout << " ";
cout << ans[i];
}
}
1010 一元多项式求导(25)
设计函数求一元多项式的导数。（注：x^n （n为整数）的一阶导数为nx^(n−1)。）
输入格式: 以指数递降方式输入多项式非零项系数和指数（绝对值均为不超过 1000 的整数）。数字间以空格分隔。
输出格式: 以与输入相同的格式输出导数多项式非零项的系数和指数。数字间以空格分隔，但结尾不能有多余空格。注意“零多项式”的指数和系数都是 0，但是表示为 0 0。
输入样例: 3 4 -5 2 6 1 -2 0 输出样例: 12 3 -10 1 6 0
#include <bits/stdc++.h>
using namespace std;
vector< pair<int, int> >ans;
int main() {
int x, y;
while(cin >> x >> y) {
if(y >= 1) {
ans.push_back({
x * y, y - 1});
}
}
if(ans.size() == 0) cout << "0 0";
for(int i = 0; i < ans.size(); i++) {
if(i != 0) cout << " ";
cout << ans[i].first << " " << ans[i].second;
}
}
1011 A+B 和 C(15)
给定区间 [−2 ^31 ,2 ^31] 内的 3 个整数 A、B 和 C，请判断 A+B 是否大于 C。
输入格式： 输入第 1 行给出正整数 T (≤10)，是测试用例的个数。随后给出 T 组测试用例，每组占一行，顺序给出 A、B 和 C。整数间以空格分隔。
输出格式： 对每组测试用例，在一行中输出 Case #X: true 如果 A+B>C，否则输出 Case #X: false，其中 X 是测试用例的编号（从 1 开始）。
输入样例： 4 1 2 3 2 3 4 2147483647 0 2147483646 0 -2147483648 -2147483647 输出样例： Case #1: false Case #2: true Case #3: true Case #4: false
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
int n;
cin >> n;
for(int i = 0; i < n; i++) {
ll a, b, c;
cin >> a >> b >> c;
cout << "Case #" << i + 1 << ": ";
if(a + b > c) cout << "true" << endl;
else cout << "false" << endl;
}
}