PAT(乙级)2020年秋季考试
7-1 多二了一点 (15分)
7-1 多二了一点 (15分)
若一个正整数有 2n 个数位,后 n 个数位组成的数恰好比前 n 个数位组成的数多 2,则称这个数字“多二了一点”。如 24、6668、233235 等都是多二了一点的数字。
给定任一正整数,请你判断它有没有多二了那么一点。
输入格式:
输入在第一行中给出一个正整数 N(≤101000)。
输出格式:
在一行中根据情况输出下列之一:
1.如果输入的整数没有偶数个数位,输出 Error: X digit(s),其中 X 是 N 的位数;
2.如果是偶数位的数字,并且是多二了一点,输出 Yes: X - Y = 2,其中 X 是后一半数位组成的数,Y 是前一半数位组成的数;
3.如果是偶数位的数字,但并不是多二了一点,输出 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)
分析:就是一个简单的高精度加法,因为字符串有最多一千位,因此按照题目意思判断一下字符串的长度;假如是奇数就返回error;假如是偶数的话就进行高精度加法运算
代码 :
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
bool isplus (string a , string b) {
int la = a.length(); //因为是用后面减前面
string sum; //所以干脆直接转换成前面加2就好了
int plus = 0; // plus 的意思是进位,假如有进位的话就加上plus
int num = 2;
for (int i = la - 1; i >= 0 ; i --) {
int tmp = a[i] = a[i] - '0' + num + plus; //从右向左进行赋值
plus = tmp / 10;
sum += '0' + (tmp % 10);
num = 0;
}
reverse (sum.begin() , sum.end()); //因为是从最后一位向前进行加法 因此要倒置一下字符串
return sum == b; //比较一下相不相等就行了
}
int main () {
string a; cin >> a;
int len = a.length();
if (len % 2 != 0) {
printf("Error: %d digit" , len);
if (len > 1) cout << "(s)" << endl; //注意当字符串长度大于一的时候要负数
return 0;
}
string b = a.substr(0, len / 2);
string c = a.substr(len / 2);
if (ispuls(b , c)) {
cout << "Yes: " << c << " - " << b << " = 2" << endl;
return 0;
} else {
cout << "No: " << c << " - " << b << " != 2" << endl;
return 0;
}
return 0;
}
总结:简单的高精度模拟题 但是有一个测试点没有过去 请评论大神知道的话告诉我一下 谢谢
7-2 数字之王
这道题光是理解题意就理解了我几十分钟。。。没办法语文不好QAQ
给定两个正整数 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≤103,其间以空格分隔。
输出格式:
首先在一行中输出数字之王的出现次数,随后第二行输出数字之王。例如对输入 1 10 就应该在两行中先后输出 6 和 8。如果有并列的数字之王,则按递增序输出。数字间以 1 个空格分隔,行首尾不得有多余空格。
输入样例:
- 10 14
输出样例:
- 2
- 0 8
题目简化:简单来说就是将 n1 到 n2 中的每一个数 (包括端点) 先立方 然后再把得到的数的每一位数加起来 eg :8 ; 首先对8进行立方操作 : 8 ^ 3 = 512 ,然后再把 512 每一位数字加起来得到新的数字 5 + 1 + 2 = 8;
思路 :因为结束的时候是要让每一位数都是个位数,换言之就是最大值是 <= 9 的此时就满足条件了
之后就是一个简单的计数问题了;
坑点在于:每个数假如超过了两位数那就要取他的个位数!!!!
一开始就因为这个点超时了
代码 : 由于思路比较混乱 再加上一开始没理解清楚题目意思 最后代码也写得很乱。。。
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
int mxnum (vector <int> v) {
int n = v.size();
int mx = 0; // 遍历一遍数组 找到最大值
for (int i = 0 ; i < n ; i ++) {
if (v[i] > mx) mx = v[i];
}
return mx <= 9 ? 1 : 0; // 假如最大值满足小于等于 9 那么就返回true
}
int main () {
int n1 ,n2;
cin >> n1 >> n2;
int len = n2 - n1 + 1;
vector <int> v(len);
int k = 0;
for (int i = n1 ; i <= n2 ; i ++) v[k ++] = i;
int mx = 0;
do{
for (int i = 0 ; i < len ; i ++) {
int t = pow((v[i] % 10), 3); //求立方
string tmp = to_string (t);
int sum = 0;
for (int j = 0 ; j < tmp.length() ; j ++) sum += tmp[j] - '0'; //求每一位的和
v[i] = sum; //然后重新赋值
}
if (mxnum(v)) break; //每一次循环过后就判断一下满不满足条件
} while (true);
// for (int i = 0 ; i < len ; i ++) cout << v[i] << " ";
int hash[10] = {0};
for (int i = 0 ; i < v.size() ; i ++) ++ hash[v[i]];
vector <int> ans;
for (int i = 0 ; i < 10 ; i ++) if(mx < hash[i]) mx = hash[i]; //找到最大值
for (int i = 0 ; i < 10 ; i ++) if(hash[i] == mx) ans.push_back(i);
sort (ans.begin() , ans.end()); //假如有多个相同的值的时候就一起放进去
cout << ans.size() << endl; // 先把ans的大小打印出来
for (int i = 0 ; i < ans.size() ; i ++) {
if (i != 0) cout << " ";
cout << ans[i];
}
return 0;
}
总结 : 代码写的很乱 思路不够清晰 理解题意太慢 还需要多多练习!!!
7-3如需挪车请致电
上图转自新浪微博。车主用一系列简单计算给出了自己的电话号码,即:
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
- 1*3
- 2^3
- 8/2
输出样例:
15330333384
题目简化 : 简单模拟题 值得注意的是题目提到了至多一次运算 意思就是还有没有运算的时候;也就是单纯给一个数字的情况 此时要考虑进去 !!! (被坑了贼久)
代码子 :
看着很长其实只需要写出来一个就可以辣
剩下的都复制粘贴就好了
#include <iostream>
#include <string>
#include <cmath>
#include <map>
using namespace std;
int main () {
map <string,int> m = {{"ling" , 0} , {"yi" , 1} , {"er" , 2} , {"san", 3} , {"si" , 4},
{"wu" , 5} , {"liu" , 6} , {"qi" , 7} , {"ba" , 8} ,{"jiu" , 9}};
string q[11];
int ans[11];
for (int i = 0 ; i < 11 ; i ++) cin >> q[i];
for (int i = 0 ; i < 11 ; i ++) {
int l = q[i].length();
string a , b;
for (int j = 0 ; j < l ; j ++) {
if (q[i][j] =='/') {
a = q[i].substr(0 , j);
b = q[i].substr(j + 1);
ans[i] = stoi(a) / stoi(b);
break;
}
if (q[i][j] == '+') {
a = q[i].substr(0 , j);
b = q[i].substr(j + 1);
ans[i] = stoi(a) + stoi(b);
break;
}
if (q[i][j] == '-') {
a = q[i].substr(0 , j);
b = q[i].substr(j + 1);
ans[i] = stoi(a) - stoi(b);
break;
}
if (q[i][j] == '%') {
a = q[i].substr(0 , j);
b = q[i].substr(j + 1);
ans[i] = stoi(a) % stoi(b);
break;
}
if (q[i][j] == '*') {
a = q[i].substr(0 , j);
b = q[i].substr(j + 1);
ans[i] = stoi(a) * stoi(b);
break;
}
if (q[i][j] == '^') {
a = q[i].substr(0 , j);
b = q[i].substr(j + 1);
ans[i] = pow(stoi(a) , stoi(b));
break;
}
if (isalpha(q[i][l - 1])) { // 这个地方偷了一下懒
ans[i] = m[q[i]]; //假如最后一位都是字母的话那肯定就是拼音对不对
break;
}
if (q[i][1] == 'q') { //这里也是 假如第二位是 q 的话
a = q[i].substr(4); //那肯定就是 sqrt 开方运算了
ans[i] = sqrt(stoi(a));
break;
}
else ans[i] = stoi(q[i]); //一定要注意最后没有运算的时候就是数字本身
}
}
for (int i = 0; i < 11 ;i ++) cout << ans[i];
return 0;
}
总结 :也是一个题目叫你干啥 你就干啥的题 虽然这些题我老是会错
7-4 胖达与盆盆奶
这道题真的挺有意思的
我没有做出来 想了半天也不知道要用什么方法来做害
大熊猫,俗称“胖达”,会排队吃盆盆奶。它们能和谐吃奶的前提,是它们认为盆盆奶的分配是“公平”的,即:更胖的胖达能吃到更多的奶,等胖的胖达得吃到一样多的奶。另一方面,因为它们是排好队的,所以每只胖达只能看到身边胖达的奶有多少,如果觉得不公平就会抢旁边小伙伴的奶吃。
已知一只胖达每次最少要吃 200 毫升的奶,当另一份盆盆奶多出至少 100 毫升的时候,它们才能感觉到是“更多”了,否则没感觉。
现在给定一排胖达的体重,请你帮饲养员计算一下,在保持给定队形的前提下,至少应该准备多少毫升的盆盆奶?
输入格式:
输入首先在第一行给出正整数 n(≤104),为胖达的个数。随后一行给出 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
题目分析 : 意思就是一个像山峰一样的数组 从最小的逐渐向两边攀爬 可是我不会敲QAQ
别人的代码 :
#include <cstdio>
int n,panda[10010],milk[10010],sum;
int main(){
int i,j,pre;
//freopen("input.txt","r",stdin);
scanf("%d%d",&n,&panda[0]);
milk[0]=200;
for(i=1;i<n;i++){
scanf("%d",&panda[i]);
if(panda[i]==panda[i-1]) milk[i]=milk[i-1];
else if(panda[i]>panda[i-1]){
milk[i]=milk[i-1]+100;
}else{
milk[i]=200;
for(j=i-1;j>=0;j--){
if(panda[j]>=panda[j+1] && milk[j]<=milk[j+1])
milk[j]+=100;
else break;
}
}
}
for(i=0;i<n;i++){
sum+=milk[i];
}
printf("%d",sum);
return 0;
}
有时间的话自己再做一遍 第四题比第五题还要难系列。。。
7-5 买地攻略
数码城市有土地出售。待售的土地被划分成若干块,每一块标有一个价格。这里假设每块土地只有两块相邻的土地,除了开头和结尾的两块是只有一块邻居的。每位客户可以购买多块连续相邻的土地。
现给定这一系列土地的标价,请你编写程序,根据客户手头的现金量,告诉客户有多少种不同的购买方案。
输入格式:
输入首先在第一行给出两个正整数:N(≤104)为土地分割的块数(于是这些块从 1 到 N 顺次编号);M(≤109)为客户手中的现金量。
随后一行给出 N 个正整数,其中第 i 个数字就是第 i 块土地的标价。
题目保证所有土地的总价不超过 109。
输出格式:
在一行中输出客户有多少种不同的购买方案。请注意客户只能购买连续相邻的土地。
输入样例:
5 85
38 42 15 24 9
输出样例:
11
样例解释:
这 11 种不同的方案为:
38
42
15
24
9
38 42
42 15
42 15 24
15 24
15 24 9
24 9
题目意思 有两种思路
1:理解成前缀和 先预处理出来前缀和 然后for循环就好了 十的四次方 不会超时(吧);
2:DFS 因为是连续的 那就从头开始dfs就好了 (出自某位大神的思路)
代码一 :(我的思路)
#include <iostream>
using namespace std;
int q[10005];
int main () {
int n , all; cin >> n >> all;
for (int i = 1 ; i <= n ; i ++) scanf ("%d" , &q[i]);
int sum[10005] = {0};
for (int i = 1 ; i <= n ; i ++) sum[i] = sum[i - 1] + q[i]; //预处理出前缀和
int cnt = 0;
int tmp = 0;
for (int i = 1 ; i <= n ; i ++) {
for (int j = i ; j <= n ; j ++) {
if (sum[j] - sum[i - 1] <= all) cnt ++; //从第一项开始遍历假如当前相减去
else break; //起始相的前一相比资金小的话 就是一种方案
} //要注意及时break 不然肯定超时的
}
cout << cnt << endl;
return 0;
}
我自己的代码在编译器上跑了一下没什么大问题 大数据也跑了一波
代码二(别人那搬来的大神代码)
毕竟我也没学dfs所以就不写注释了
#include <iostream>
using namespace std;
int n, m, cnt=0, place[10010];
void DFS(int sum, int idx){
if(idx >= n) return;
if(sum > m) return;
cnt++;
DFS(sum+place[idx+1], idx+1);
}
int main(){
cin >>n>>m;
for(int i=0; i<n; i++) scanf("%d", &place[i]);
for(int i=0; i<n; i++) DFS(place[i], i);
cout <<cnt;
return 0;
}
真的好简短好优美 !!!
总结:
因为刚学编程三个多月 匆忙准备比赛 而且算法知识也不富足 所以让各位见笑了
这次模拟赛算是正式比赛前的热身,希望正式比赛的时候不要像这次一样笨笨的脑子也转不过来
请各位读者帮我纠错或者哪个地方有问题的欢迎评论区讨论 谢谢子!!