两学一做登录网站,企业网站维护怎么做,360 街景地图,wordpress认证机制PTA Basic Level Practice 解题思路和代码#xff0c;主要用的是 C。每22题一篇博客#xff0c;可以按目录来进行寻找。 文章目录 1045 快速排序1046 划拳1047 编程团体赛1048 数字加密1049 数列的片段和1050 螺旋矩阵1051 复数乘法1052 卖个萌1053 住房空置率1054 求平均值1… PTA Basic Level Practice 解题思路和代码主要用的是 C。每22题一篇博客可以按目录来进行寻找。 文章目录 1045 快速排序1046 划拳1047 编程团体赛1048 数字加密1049 数列的片段和1050 螺旋矩阵1051 复数乘法1052 卖个萌1053 住房空置率1054 求平均值1055 集体照1056 组合数的和1057 数零壹1058 选择题1059 C语言竞赛1060 爱丁顿数1061 判断题1062 最简分数 1045 快速排序
思路 对于每一个元素如果其比左侧的最大值要大比右侧的最小值要小那么它就符合主元的定义所以具体的做法就是
先遍历一遍数组找出每个元素左侧的最大值再遍历一遍数组找出每个元素右侧的最小值最后遍历一遍数组找出符合主元要求的所有数最后打印输出。时间复杂度为 O ( n ) O(n) O(n)。
用 leftMax 数组来保存 A 中对应元素左侧的最大值。假设当前下标是 i比较其前一个元素 A[i - 1] 和前一个元素左侧的最大值 leftMax[i - 1]谁更大谁就是 A[i] 左侧的最大值寻找右侧最小值同理。然后就是升序输出的问题因为符合要求的主元都是比左侧的元素要大因此放入到 ans 数组中的元素也一定是升序排列的。最后要注意一下输出的格式第三个测试点中结果没有主元所以输出第一行中主元的个数为0第二行是一个空行所以最后要加一句 cout endl;
#include iostream
#include vector
using namespace std;int main()
{int n;cin n;vectorint A(n), leftMax(n), rightMin(n), ans;for (int i 0; i n; i)cin A[i];leftMax[0] 0, rightMin[n - 1] 0x3fffffff; // 最小值和最大值for (int i 1; i n; i)leftMax[i] max(A[i - 1], leftMax[i - 1]); // 寻找每个整数左侧的最小值for (int j n - 2; j 0; --j)rightMin[j] min(A[j 1], rightMin[j 1]); // 寻找每个整数右侧的最大值for (int i 0; i n; i)if (leftMax[i] A[i] A[i] rightMin[i]) // 将符合要求的数放入数组ans.push_back(A[i]);cout ans.size() endl;if (ans.size() 0) cout ans[0]; // 第一个数前不打印空格for (int i 1; i ans.size(); i) cout ans[i]; // 除第一个数外每个数之前都打印一个空格cout endl; // 打印空行return 0;
}另一种做法在快速排序中每一趟排序后主元一定到达了最终的位置。因此先对初始数组进行拷贝然后对它进行排序。排序后对两个数组进行逐个元素的比较元素位置不发生变化且比左侧的最大值都要大的元素一定可以做主元。
另外提一点在对数据进行频繁的访问操作时数组的效率要比 vector 高很多。但这不能说明数组一定比 vector 好vector 拥有很多强大的功能也可以存储很多种类型相比之下数组还是太单一了点。如果只是对一组数据进行简单的频繁访问可以选择数组否则用 vector 更加方便。
#include iostream
#include algorithm
#include vector
using namespace std;
vectorint ans;
int main()
{int n, max 0;cin n;vectorint a(n);for (int i 0; i n; i)cin a[i];vectorint b a; // 拷贝初始数组sort(a.begin(), a.end()); // 对数组进行排序for (int i 0; i n; i){if (a[i] b[i] b[i] max) // 符合要求的主元放入数组 ansans.push_back(b[i]); max b[i] max ? b[i] : max; // 更新最大值}cout ans.size() endl;if (ans.size() 0) cout ans[0];for (int i 1; i ans.size(); i)cout ans[i];cout endl;return 0;
}1046 划拳
#include iostream
using namespace std;int main()
{int ashout, bshout, cshout, ahua, bhua, acnt, bcnt, n;cin n;acnt bcnt 0;while (n--){cin ashout ahua bshout bhua;cshout ashout bshout;if (cshout ahua cshout bhua)continue;else if (cshout ahua) bcnt;else if (cshout bhua) acnt;}cout acnt bcnt;return 0;
}1047 编程团体赛
#include iostream
#include cstring
using namespace std;int main()
{int n, team, num, score, hashTable[1000] {0};cin n;int chpteam -1, chpscore -1;char c;while (n--){cin team c num score; // 用 c 过滤队员和队伍编号之间的 -hashTable[team] score;if (hashTable[team] chpscore){chpteam team;chpscore hashTable[team];}}cout chpteam chpscore;return 0;
}1048 数字加密
思路 将整数 A 和 B 分别倒置此时就将整数的个位放到了字符串的第一位。然后获取两者的长度对于较短的在字符串的末尾补上 ‘0’相当于在整数的高位补了0。然后从字符串的最后一位整数的最高位开始遍历一直到字符串的第一位整数的个位逐个加密逐个输出即可得到加密后的结果这样就就省去了再定义一个 string 对象保存加密结果了。
注意
位数不够需要补0参与加密而不是将多余的字符直接输出。奇数位偶数位指的是数位的奇偶性而不是位上的数字的奇偶性。i 从 max(lena, lenb) 开始不断减小而不是 lena 或 lenb否则会漏解的。用的是下标遍历下标是偶数时对应的是奇数位规则是反过来的。
经验
用 string C; 来代替 char C[13]; 数组更加简便。三元运算符的效率比 if-else 更高。判断下标奇偶性可以用与运算效率更高。x 1结果为1是奇数结果为0是偶数和奇偶判断是一样的。注意不能写成 i 1 0因为 ‘’ 的运算优先级比 ‘’ 更高写成这样会先运算 1 0 倒置全是 false 了。取而代之可以写成 (i 1) 0 或者 !(i 1)。reverse() 函数用于将数组或字符串倒置在头文件 algorithm 中。append() 函数是在字符串的末尾添加指定个数的字符头文件 iostream 就已经包含了
#include iostream
#include algorithm
using namespace std;int main()
{string A, B, C 0123456789JQK;cin A B;reverse(A.begin(), A.end()); // 字符串倒置reverse(B.begin(), B.end());int lena A.size(), lenb B.size();lena lenb ? B.append(lena - lenb, 0) : A.append(lenb - lena, 0); // 补0for (int i max(lena, lenb) - 1; i 0; --i) // 从最高位开始{if (!(i 1))cout C[(B[i] - 0 A[i] - 0) % 13];elsecout ((B[i] - A[i]) 10) % 10;}return 0;
}1049 数列的片段和
#include iostream
#include iomanip
using namespace std;int main()
{int n;long double v, ans 0; // ans 必须要用 long double 型来定义否则会导致测试点3超时cin n;for (int i 1; i n; i){cin v;ans v * i * (n 1 - i); // 第 i 位的总出现次数为 v * i * (n 1 - i)}cout setiosflags(ios::fixed) setprecision(2) ans endl;return 0;
}1050 螺旋矩阵
思路 寻找 m - n 最小差值的过程类似于判断是否为素数其实也就是寻找 N 的最接近因子对的过程从 n 1 枚举到 n * n N如果 N 能被 n 整除就令 m N / n。在退出循环后得到的就是满足 m - n 差值最小的 m也是大于等于 N \sqrt N N 中最小的一个因子。然后再令 n N / m 即可得到满足 m - n 差值最小的 n。用 sort() 函数对输入的数组 A 进行排序用 memset() 函数将二维螺旋数组 B 的所有元素初始化为0。
然后在 while 循环中将 A 数组的元素依次填充到数组 B 中因为 sort() 函数是从小到大的排序所以我用 k 来标记数组的尾部下标填充一个 k 的值就减1当 k 的值小于0时表明填充完了从而退出 while 循环。填充过程的基本思路是用 d 的值来标记填充的方向继续当前方向填充的标志是 B[i][j] 0 且 i 或 j 并未到达数组边界。因为题目表明了输入的都是正整数所以可以用元素值为0表明还没有被填充过 注意
i 和 j 要初始化为 -1因为第一次进入 for 循环时 i 和 j 分别加了1。退出一个 for 循环后i 和 j 的值会与一开始填充的路线偏离所以在下一个 for 循环时加1或减1来让路线回正。
经验
对于任意一个正整数 N其因子对中一定有一个 ≤ N \le \sqrt N ≤N 而另一个 ≥ N \ge \sqrt N ≥N 因此 N 只需要从 1 枚举到 N \sqrt N N 。二维数组的初始化用 memset() 函数就很方便。对于这种模拟类的题目详细的写出其过程更有助于理清解题思路。
#include iostream
#include cstring
#include algorithm
using namespace std;int main()
{int N, m, n, d 0, i -1, j -1, k 0;cin N;for (n 1; n * n N; n) // 寻找满足大于根号 N 却又最小的因子 mm N % n 0 ? N / n : m;n N / m, k N - 1;int A[N], B[m][n];for (int l; l N; l) cin A[l];sort(A, A N); // 排序memset(B, 0, sizeof(B)); // 初始化螺旋数组while (k 0){if (d 0) // i, j 的过程就是路线回正的过程for (i, j; B[i][j] 0 j n; j) B[i][j] A[k--];else if (d 1) // i, --j 也是使路线回正的做法for (i, --j; B[i][j] 0 i m; i) B[i][j] A[k--];else if (d 2)for (--i, --j; B[i][j] 0 j 0; --j) B[i][j] A[k--];elsefor (--i, j; B[i][j] 0 i 0; --i) B[i][j] A[k--];d (d 1) % 4;}for (i 0; i m; i){cout B[i][0];for (j 1; j n; j)cout B[i][j];cout endl;}return 0;
}1051 复数乘法
#include iostream
#include iomanip
#include cmath
using namespace std;int main(){double r1, r2, p1, p2;double a, b;cin r1 p1 r2 p2;a (r1 * r2) * cos(p1 p2);b (r1 * r2) * sin(p1 p2);if(fabs(a) 0.01) a 0;if(fabs(b) 0.01) b 0;if(b 0)cout setiosflags(ios::fixed) setprecision(2) a - fabs(b) i;elsecout setiosflags(ios::fixed) setprecision(2) a fabs(b) i;return 0;
}1052 卖个萌
题目有一个隐含条件没有说明左手和左眼之间要加左括号右眼和右手之间要加右括号。这一题我不知道为什么控制端就是不能输出特殊字符所以索性就不做了贴上柳神代码的链接1052. 卖个萌 (20)-PAT乙级真题。 1053 住房空置率
#include iostream
#include iomanip
using namespace std;int main()
{int N, D, K, cnt 0; // m 可能空置n 空置 float e, ei, m 0, n 0;cin N e D;for (int i 0; i N; i, cnt 0){cin K;for (int j 0; j K; j){cin ei;if (ei e) cnt; // 用电量小于给定阈值 e计数1}if (cnt K / 2) K D ? m : n; // 符合条件1的前提下不符合条件2可能空置否则空置 }cout setiosflags(ios::fixed) setprecision(1) m / N * 100 % n / N * 100 %;return 0;
}1054 求平均值
思路 读者可以阅读一下PAT OJ 刷题必备知识总结 12 sscanf 与 sprintf 中的内容。sscanf 会将 a 中符合 %lf 格式的内容写入 tempsprintf 会将 temp 中的内容以 %.2lf 的格式写入 b。执行完这两步后比较 a 中的每一位与 b 中的对应位是否相等只有符合题目要求的数才会相等。如果不相等令 flag 等于1。然后进行判断只有同时满足 falg 为0temp 的值在 [-1000, 1000] 之内才是题目所求的合法数。然后更新和与计数最后按照题目规定的格式输出即可。输出的时候要注意只有一个合法数时应当输出 “number” 而不是 “numbers”。
#include iostream
#include cstdio
#include cstring
#include iomanip
using namespace std;
int main()
{int n, cnt 0, flag 0;double temp 0.0, sum 0.0;char a[50], b[50];cin n;for (int i 0; i n; i, flag 0){cin a;sscanf(a, %lf, temp); // 将 a 中的内容以浮点数的格式写入 tempsprintf(b, %.2f, temp); // 将 temp 中的内容以 %.2f 的格式写入 bfor (int j 0; j strlen(a); j) // 存在不对应的字符flag 1表明不匹配if (a[j] ! b[j]) flag 1;if (flag || temp -1000 || temp 1000)cout ERROR: a is not a legal number endl;else{sum temp; // 更新和cnt; // 更新计数}}if (cnt 1)cout The average of 1 number is setiosflags(ios::fixed) setprecision(2) sum;else if (cnt 1)cout The average of cnt numbers is setiosflags(ios::fixed) setprecision(2) sum / cnt;else cout The average of 0 numbers is Undefined;return 0;
}1055 集体照
思路 这一题首先要结合测试用例仔细理解一下题目的意思按照排队规则还原一下队伍的情况如下所示可以知道它的排列是整体先从高到低然后身高相等时再按照字典序排序。因此在得到输入后应首先按要求对整个队伍进行一次排列。要使名字和身高同时更换顺序最好就是用结构体。定义一个结构体数组 person 来保存所有的排队人员。
解决了排序问题就需要将所有人依次按照规则放入每一行中。由于说了后排的人输出在上方所以很自然地我们就能从数组的头部一个个往每一行排入。用 n 来标记目前该排哪个人用 r 来表明排到了哪一行两者初始值都为0。用 m 来表示每一行需要排多少人最上方一行需要 N % K N / K想一想为什么个人下方的每一行都是 N / K 个人。因为当 r 0 时 m N % K N / K。假设现在在第一行需要排四个人也就是 JoeTomNick 和 Bob。按照题目要求就是先把最高的 Joe 排好后面就一个放 Joe 的右边一个放 Joe 的左边以此往复而在我们的视角内就是先排好 Joe然后 Tom 放左边Nick 放右边Bob 又放到左边。如果用一个数组 line 来表示当前行那么就应该是如下的形式
所以我的思路就是在排每一行的人时将 person 数组中下标 n ~ n m 的人依次拿出来放入 line 数组先放左边的再放中间最高的最后放右边的。中间的位置是 m / 2比如一行4个人时中间位置的下标就是 4 / 2 2一行3个人时中间位置的下标就是 3 / 2 1用 j 来标记应该放在 line 数组中的哪个位置。
用 i 来标记 person 数组而 person[n] 固定是放在中间位置的。排左边时i 从 n 1 开始因为是先放一个左边再放一个右边所以 i 每次循环是自增2而 j 是从 m / 2 - 1 开始往 0 的方向走然后将 person[i].name 给到 line[j]即可。右边 j 则是从 m / 2 1 开始往 m 的方向走i 依然是每次循环自增2。排完一行后进入下次循环前要令 n m因为有 m 个人已经排完了。
注意 我一开始用的是双端队列来表示每一行然后用 push_front 和 push_back 来实现左插入和右插入这样就不用考虑数组下标的问题。但是会超时所以才改用直接通过下标访问数组的方式毕竟插入元素需要移动比直接访问更耗时。
经验
两个条件的 cmp 函数用一个三目运算符就能实现新技能 get。不需要用二维数组来保存排完一行就输出一行空间利用更少代码也更简洁。
#include iostream
#include algorithm
#include vector
using namespace std;struct Person
{string name;int height;
} person[10005];bool cmp(const Person a, const Person b)
{return a.height b.height ? a.name b.name : a.height b.height;
}int main()
{int N, K, n 0;cin N K;for (int i 0; i N; i)cin person[i].name person[i].height;sort(person, person N, cmp); // 先按身高排序后按名字字典序排序for (int r 0; r K; r){int m r 0 ? N % K N / K : N / K;vectorstring line(m, ); // 数组大小为 m初始化为空串for (int i n 1, j m / 2 - 1; i n m j 0; i 2, --j)line[j] person[i].name; // 排左边的同学line[m / 2] person[n].name; // 排中间最高的同学for (int i n 2, j m / 2 1; i n m j m; i 2, j)line[j] person[i].name; // 排右边的同学n m;cout line[0]; // 第一个名字前不输出空格for (int i 1; i line.size(); i)cout line[i];cout endl;}return 0;
}1056 组合数的和
思路 输入 N 个数每个数字既可能做个位数也有可能做十位数分别会出现 N - 1 次。所以每个数 n 所产生和是 (n * 10 n) * (N - 1) n * 11 * (N - 1)。
#include iostream
using namespace std;int main()
{int N, n, sum 0;cin N;while (cin n)sum 11 * n * (N - 1);cout sum;return 0;
}1057 数零壹
思路 由于输入可能有空格所以用 getline 来获取字符串。枚举字符串中的字符若是字母将其转换为小写字母后计算序号加到 sum 上。利用二进制除法来统计0和1的个数即可。
#include iostream
using namespace std;int main()
{int sum 0, cnt_0 0, cnt_1 0;string s;getline(cin, s);for (int i 0; i s.size(); i)if (isalpha(s[i])) sum tolower(s[i]) - a 1;while (sum){sum % 2 1 ? cnt_1 : cnt_0;sum / 2;} ;cout cnt_0 cnt_1;return 0;
}1058 选择题
思路 定义 score 数组保存每一题的满分opts 为选项数cor 为正确选项个数ans 数组保存每一题的正确选项也即正确答案。然后照常获取所有的输入用一个 c getchar() 来过滤掉输入流中的回车。
定义 stuScore 数组保存每个学生的得分wrongCnt 数组保存每一题的错误次数maxWrong 保存最大的错误次数。第一层 for 循环用 i 枚举每一个学生。因为每个学生的答题情况包含所有的选择题且没有题号标记只是用左右括号隔开然后顺序输入所以用 cur 来记录题号因此在每一层循环中都需要将题号 cur 置0。
因为学生的答题情况用一行字符串表示而我思考后决定只对三种字符情况做判断所以在这里用 c getchar() 来处理比直接用 string 来接受一整行的输入更加方便。
当 c 为 ‘(’ 时表明到了下一题cur 加1且清空学生的选择 temp当 c 为字母时是学生的选择将其加入 temp当 c 为 ‘)’ 时就需要判断对错了将 temp 与 ans[cur] 作比较正确的话则增加得分 stuScore[i] score[cur]错误的话该题错误次数 wrongCnt[cur] 加1。然后检查是否需要更新 wrongCnt。
输入完后按题目要求输出即可。
注意 仔细思考和试错过后发现选项个数 opts、正确选项个数 cor 在后面用不上所以就没有用数组来保存。因为即便加上“如果学生的选择数不等于正确选项个数判错”由于数据量和选项数比较少并不会带来更多的时长优化而为此还需要多加一层判断得不偿失。
#include iostream
using namespace std;int main()
{int N, M, a, score[105], opts, cor, cur;string ans[105], temp;cin N M;for (int i 1; i M; i){cin score[i] opts cor;while (cor--){cin temp; // cin 可以过滤掉正确选项之间的空格ans[i] temp; // 将所有正确选项保存在 ans 中}}char c getchar(); // 过滤掉输入流里的回车int stuScore[N 1] {0}, wrongCnt[M 1] {0}, maxWrong 0;for (int i 1, cur 0; i N; i, cur 0)// i 枚举每一个学生{while ((c getchar()) ! \n){if (c () // 遇到左括号表明到了下一题{cur; // 题号加1temp ; // 清空 temp}else if (isalpha(c)) temp c; // 将学生的选择加入 temp 中else if (c )) // 遇到右括号就判断是对错{if (temp ans[cur]) stuScore[i] score[cur];else wrongCnt[cur]; // 题号为 cur 的错误数加1maxWrong wrongCnt[cur] maxWrong ? wrongCnt[cur] : maxWrong; // 更新最大错误数}}}for (int i 1; i N; i) cout stuScore[i] endl;if (!maxWrong) cout Too simple;else{cout maxWrong;for (int i 1; i M; i)if (wrongCnt[i] maxWrong) cout i;}return 0;
}1059 C语言竞赛
思路 基本思路就是定义一个 map 字典 id_pz_ck其中键是参赛者的 ID值是一个 pairpair 的 first 成员是奖品second 成员是布尔值表明其是否被查询过。
通过 insert 函数来将新的键值对插入到 map 中构造键值对的方式是用花括号括起来。通过 find() 函数来查找键是否在字典中返回的是指向该键的迭代器如果没有这个键返回的就是字典的尾后迭代器。
#include iostream
#include map
using namespace std;bool isPrime(int n) // 判断是否是素数
{for (int i 2; i * i n; i)if (n % i 0) return false;return true;
}int main()
{int N, K, ifChecked[N];string id, prize, query;cin N;mapstring, pairstring, bool id_pz_ck;for (int i 1; i N; i) // i 为排名{cin id;if (i 1) id_pz_ck.insert({id, {Mystery Award, false}});else if (isPrime(i)) id_pz_ck.insert({id, {Minion, false}});else id_pz_ck.insert({id, {Chocolate, false}});}cin K;while (K--){cin query;if (id_pz_ck.find(query) id_pz_ck.end()) // 查询 id 不在字典中cout query : Are you kidding? endl;else if (!id_pz_ck[query].second) // 查询 id 在字典中且布尔值为 false{cout query : id_pz_ck[query].first endl;id_pz_ck[query].second true; // 查询过该 id布尔值变为 true}else cout query : Checked endl;}return 0;
}1060 爱丁顿数
思路 将数组从大到小排序排好序就是如下图所示
然后从下标 i 1 开始枚举数组中的元素。从题目的要求可以这么理解当 i 6 时a[i] 7因为数组是递减的说明从 1 ~ 6 这六天的英里数都是大于6的就满足了 E 6 满足有 6 天骑车超过 6 英里。当 i 7 时a[i] 6说明从 1 ~ 7 这七天的英里数不全都大于 7不满足 E 7。再往后就肯定都不满足了所以输出前一个满足条件的 i即 i - 1。
注意
是超过因此要用大于号。测试用例会出现如 3 3 3 3 5 这种此时 E 2再如1 1 1 1 这种此时 E 0再入 0 0 0 2 0此时 E 1
#include iostream
#include algorithm
using namespace std;bool cmp(int a, int b) { return a b; }int main()
{int N;cin N;int a[N 1], i;for (int j 1; j N; j)cin a[j];sort(a 1, a N 1, cmp);for (i 1; i N; i)if (i a[i]) break;cout i - 1;return 0;
}1061 判断题
#include iostream
using namespace std;int main()
{int N, M, n, score[105], ans[105]; // score 数组保存每道题的分数ans 数组保存每道题的答案cin N M;for (int i 0; i M; i) cin score[i];for (int i 0; i M; i) cin ans[i];while (N--){int total 0; // 学生得分for (int i 0; i M; i) // i 为题目序号{cin n; // 学生的解答if (n ans[i]) total score[i];}cout total endl;}return 0;
}1062 最简分数
