引言:
起初,報PAT是伙伴推薦。但在報名路途中,有朋友說,花時間到這上面不值得,還有學長說沒聽過,野雞杯。
我一笑而過,我可能就是偏執,我就是想報。隨著刷真題,我的基礎得以鞏固,我在想,他們為此而錯過了什么...
大綱:
1、A+B和C (15) - 簡單題(解析)
2、數字分類 (20) - 邊界測試,要細心(解析)
3、數素數 (20) - 歐拉篩(解析)
4、福爾摩斯的約會 (20) - 我還是喜歡柳姐的代碼,太簡便了(解析)
5、德才論 (25) - 第一次運用結構體,太爽了(解析)
6、1016. 部分A+B (15) - 簡單題(解析)
7、A除以B (20) - 模擬-除法,非常好的題目(解析)
8、錘子剪刀布 (20) - 第一次用pair<int,int>...(解析)
9、1019. 數字黑洞 (20) - 加深了我對pair的運用(解析)
10、月餅 (25) - 不在介意結構體,甚至喜歡與sort結合(解析)
題目:
1、A+B和C (15)
題目描述
給定區間[-231, 231]內的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 <iostream>
using namespace std;
int main() {int n;scanf("%d", &n);for (int i = 0; i < n; i++) {long long int a, b, c;scanf("%lld%lld%lld", &a, &b, &c);printf("Case #%d: %s\n", i + 1, a + b > c ? "true" : "false");}return 0;
}
2、數字分類 (20)
題目描述
給定一系列正整數,請按要求對數字進行分類,并輸出以下5個數字:A1 = 能被5整除的數字中所有偶數的和;A2 = 將被5除后余1的數字按給出順序進行交錯求和,即計算n1-n2+n3-n4...;A3 = 被5除后余2的數字的個數;A4 = 被5除后余3的數字的平均數,精確到小數點后1位;A5 = 被5除后余4的數字中最大數字。輸入描述:
每個輸入包含1個測試用例。 每個測試用例先輸入一個不超過1000的正整數N。 然后給出N個不超過1000的待分類的正整數。數字間以空格分隔。輸出描述:
對給定的N個正整數,按題目要求計算A1~A5并在一行中順序輸出。數字間以空格分隔,但行末不得有多余空格。 若其中某一類數字不存在,則在相應位置輸出“N”。輸入例子:
13 1 2 3 4 5 6 7 8 9 10 20 16 18輸出例子:
30 11 2 9.7 9
#include <iostream>
using namespace std;
// 這道題目,真抽象,怪不得通過率這么低,壓根是因為邊界測試緣故,粗心緣故
int main() {int A1=0,A2=0,A3=0,A4=0,A5=INT32_MIN;int i2=1,i4=0;int n;cin>>n;int num;while(n--){cin>>num;if(num%5==0&&num%2==0){A1 += num;}else if (num%5==1){A2 += num*i2;i2*=(-1);}else if (num%5==2) {A3++;}else if (num%5==3){A4+=num;i4++;}else if (num%5==4) {A5 = max(num,A5);}}if(A1!=0) cout<<A1<<" ";else cout<<"N ";if(A2!=0) cout<<A2<<" ";else cout<<"N ";if(A3!=0) cout<<A3<<" ";else cout<<"N ";if(i4!=0) printf("%.1f ",(double)A4/i4);else cout<<"N ";if(A5!=INT32_MIN) cout<<A5<<" ";else cout<<"N ";
}
// 64 位輸出請用 printf(\"%lld\")
3、數素數 (20)
題目描述
令Pi表示第i(i從1開始計數)個素數。現任給兩個正整數M <= N <= 10000,請輸出PM到PN的所有素數。輸入描述:
輸入在一行中給出M和N,其間以空格分隔。輸出描述:
輸出從PM到PN的所有素數,每10個數字占1行,其間以空格分隔,但行末不得有多余空格。輸入例子:
5 27輸出例子:
11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103
#include "bits/stdc++.h"
using namespace std;
int sieve[110005];
void get_sieve(vector<bool>& bool_sieve){ // 歐拉篩,大范圍篩數int num = 0;bool_sieve[2] = true; // 表示二是素數for(int i=2; i<110005; ++i){if(bool_sieve[i]) sieve[num++]=i;for (int j = 0; j < num; ++j) {if(i*sieve[j]>110005) break;bool_sieve[i*sieve[j]] = false;if(i% sieve[j]==0) break;}}}
int main(){int n,m;cin>>n>>m;vector<bool> bool_sieve(110005, true); // 表示都是質數bool_sieve[0] = bool_sieve[1] = false;get_sieve(bool_sieve);int flag = 0;for(int i = n-1; i < m; ++i){flag++;cout<<sieve[i];if(flag%10==0) cout<<endl;else cout<<" ";}return 0;
}
4、福爾摩斯的約會 (20)
題目描述
大偵探福爾摩斯接到一張奇怪的字條:“我們約會吧! 3485djDkxh4hhGE 2984akDfkkkkggEdsb s&hgsfdk d&Hyscvnm”。大偵探很快就明白了,字條上奇怪的亂碼實際上就是約會的時間“星期四 14:04”,因為前面兩字符串中第1對相同的大寫英文字母(大小寫有區分)是第4個字母'D',代表星期四;第2對相同的字符是'E',那是第5個英文字母,代表一天里的第14個鐘頭(于是一天的0點到23點由數字0到9、以及大寫字母A到N表示);后面兩字符串第1對相同的英文字母's'出現在第4個位置(從0開始計數)上,代表第4分鐘。現給定兩對字符串,請幫助福爾摩斯解碼得到約會的時間。
(注:兩字符串的比較過程必須按照兩字符串中對應的下標相同的字符進行比較!)
?輸入描述:
輸入在4行中分別給出4個非空、不包含空格、且長度不超過60的字符串。輸出描述:
在一行中輸出約會的時間,格式為“DAY HH:MM”,其中“DAY”是某星期的3字符縮寫,即MON表示星期一,TUE表示星期二,WED表示星期三,THU表示星期 四,FRI表示星期五,SAT表示星期六,SUN表示星期日。題目輸入保證每個測試存在唯一解。輸入例子:
3485djDkxh4hhGE 2984akDfkkkkggEdsb s&hgsfdk d&Hyscvnm輸出例子:
THU 14:04
#include <iostream>
#include <cctype>
using namespace std;
// 這個是劉姐的代碼,太簡介啦!!!
int main() {string a, b, c, d;cin >> a >> b >> c >> d;char t[2];int pos, i = 0, j = 0;while(i < a.length() && i < b.length()) {if (a[i] == b[i] && (a[i] >= 'A' && a[i] <= 'G')) {t[0] = a[i];break;}i++;}i = i + 1;while (i < a.length() && i < b.length()) {if (a[i] == b[i] && ((a[i] >= 'A' && a[i] <= 'N') || isdigit(a[i]))) {t[1] = a[i];break;}i++;}while (j < c.length() && j < d.length()) {if (c[j] == d[j] && isalpha(c[j])) {pos = j;break;}j++;}string week[7] = {"MON ", "TUE ", "WED ", "THU ", "FRI ", "SAT ", "SUN "};int m = isdigit(t[1]) ? t[1] - '0' : t[1] - 'A' + 10;cout << week[t[0]-'A'];printf("%02d:%02d", m, pos);return 0;
}
5、德才論 (25)
題目描述
宋代史學家司馬光在《資治通鑒》中有一段著名的“德才論”:“是故才德全盡謂之圣人,才德兼亡謂之愚人,德勝才謂之君子,才勝德謂之小人。凡取人之術,茍不得圣人,君子而與之,與其得小人,不若得愚人。”現給出一批考生的德才分數,請根據司馬光的理論給出錄取排名。輸入描述:
輸入第1行給出3個正整數,分別為:N(<=105),即考生總數;L(>=60),為錄取最低分數線,即德分和才分均不低于L的考生才有資格 被考慮錄取;H(<100),為優先錄取線——德分和才分均不低于此線的被定義為“才德全盡”,此類考生按德才總分從高到低排序;才分不到 但德分到線的一類考生屬于“德勝才”,也按總分排序,但排在第一類考生之后;德才分均低于H,但是德分不低于才分的考生屬于“才德兼 亡”但尚有“德勝才”者,按總分排序,但排在第二類考生之后;其他達到最低線L的考生也按總分排序,但排在第三類考生之后。隨后N行,每行給出一位考生的信息,包括:準考證號、德分、才分,其中準考證號為8位整數,德才分為區間[0, 100]內的整數。數字間以空格分隔。輸出描述:
輸出第1行首先給出達到最低分數線的考生人數M,隨后M行,每行按照輸入格式輸出一位考生的信息,考生按輸入中說明的規則從高到低排序。當某類考生中有多人 總分相同時,按其德分降序排列;若德分也并列,則按準考證號的升序輸出。輸入例子:
14 60 80 10000001 64 90 10000002 90 60 10000011 85 80 10000003 85 80 10000004 80 85 10000005 82 77 10000006 83 76 10000007 90 78 10000008 75 79 10000009 59 90 10000010 88 45 10000012 80 100 10000013 90 99 10000014 66 60輸出例子:
12 10000013 90 99 10000012 80 100 10000003 85 80 10000011 85 80 10000004 80 85 10000007 90 78 10000006 83 76 10000005 82 77 10000002 90 60 10000014 66 60 10000008 75 79 10000001 64 90
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
// 這可是,我第一次,在算法中運用結構體,太爽了,當與cmp結合時
struct student {int sum;int moral;int talent;int id;student(int x, int y, int z): moral(x), talent(y), id(z) {sum = x + y;}
};
bool cmp(const student& stu1, const student& stu2) { // 匹配模式if (stu1.sum != stu2.sum) return stu1.sum >stu2.sum; // 第一個大于第二個if (stu1.moral != stu2.moral) return stu1.moral > stu2.moral; // 德高者居之return stu1.id < stu2.id; // 按降序排列
}
int main() {int N, L, H; // N(考生總數) L(最低錄取分數線) H(優先錄取)cin >> N >> L >> H;vector<student> vec1, vec2, vec3, vec4;while (N--) {int id, moral, talent;cin >> id >> moral >> talent;student s(moral, talent, id);if (s.moral >= H && s.talent >= H) vec1.push_back(s);else if (s.moral >= L && s.talent >= L) { // 都及格if (s.moral >= s.talent && s.moral >= H) vec2.push_back(s);else if (s.moral >= s.talent) vec3.push_back(s);else vec4.push_back(s);}}sort(vec1.begin(), vec1.end(), cmp);sort(vec2.begin(), vec2.end(), cmp);sort(vec3.begin(), vec3.end(), cmp);sort(vec4.begin(), vec4.end(), cmp);cout << vec1.size() + vec2.size() + vec3.size() + vec4.size() << endl;for (student s : vec1) cout << s.id << " " << s.moral << " " << s.talent <<endl;for (student s : vec2) cout << s.id << " " << s.moral << " " << s.talent <<endl;for (student s : vec3) cout << s.id << " " << s.moral << " " << s.talent <<endl;for (student s : vec4) cout << s.id << " " << s.moral << " " << s.talent <<endl;return 0;
}
6、1016. 部分A+B (15)
題目描述
正整數A的“DA(為1位整數)部分”定義為由A中所有DA組成的新整數PA。例如:給定A = 3862767,DA = 6,則A的“6部分”PA是66,因為A中有2個6。現給定A、DA、B、DB,請編寫程序計算PA + PB。輸入描述:
輸入在一行中依次給出A、DA、B、DB,中間以空格分隔,其中0 < A, B < 1010。輸出描述:
在一行中輸出PA + PB的值。輸入例子:
3862767 6 13530293 3輸出例子:
399
#include <bits/stdc++.h>
#define ll long long
using namespace std;
// 這道題,倒是挺簡單的
int get_num(char d, int num){int D = d-'0';int all_num = 0;while (num--) {all_num = all_num*10+D;}return all_num;
}
int main(){string a,b;char Da,Db;cin>>a>>Da>>b>>Db; // 輸入int numa=0,numb=0;for(int i=0; i<a.size(); ++i) // 判斷if(a[i]==Da) numa++;for(int i=0; i<b.size(); ++i)if(b[i]==Db) numb++;cout<<get_num(Da, numa)+get_num(Db, numb)<<endl;}
7、A除以B (20)
題目描述
本題要求計算A/B,其中A是不超過1000位的正整數,B是1位正整數。你需要輸出商數Q和余數R,使得A = B * Q + R成立。輸入描述:
輸入在1行中依次給出A和B,中間以1空格分隔。輸出描述:
在1行中依次輸出Q和R,中間以1空格分隔。輸入例子:
123456789050987654321 7輸出例子:
17636684150141093474 3
// !本題值得做!,主要模擬除法內容
// 加深對模擬的了解
#include <bits/stdc++.h>
using namespace std;
int main(){string a;int b;cin>>a>>b;int len,t=0,temp=0; // t(存放除數),temp(存放余數)len = a.size();t = (a[0]-'0')/b; // 模擬除法if(t!=0) cout<<t;temp = (a[0]-'0')%b;int flag = false;for(int i=1; i<a.size(); ++i){t = (temp*10+a[i]-'0')/b; // 求除數if(t!=0) flag = true;if(flag) cout<<t;temp = (temp*10 +a[i]-'0')%b; // 求剩下的余數}cout<<" "<<temp;return 0;
}
8、錘子剪刀布 (20)
題目描述
大家應該都會玩“錘子剪刀布”的游戲: 現給出兩人的交鋒記錄,請統計雙方的勝、平、負次數,并且給出雙方分別出什么手勢的勝算最大。輸入描述:
輸入第1行給出正整數N(<=105),即雙方交鋒的次數。隨后N行,每行給出一次交鋒的信息,即甲、乙雙方同時給出的的手勢。C代表“錘子”、J代表“剪刀”、B代 表“布”,第1個字母代表甲方,第2個代表乙方,中間有1個空格。輸出描述:
輸出第1、2行分別給出甲、乙的勝、平、負次數,數字間以1個空格分隔。第3行給出兩個字母,分別代表甲、乙獲勝次數最多的手勢,中間有1個空格。如果解不唯 一,則輸出按字母序最小的解。輸入例子:
10 C J J B C B B B B C C C C B J B B C J J輸出例子:
5 3 2 2 3 5 B B
// 本題,一般般,沒啥含金量
// 其實挺有含金量的,知識不知道如何將其表示出來
// 這是我第一次,通過pair<int,int>的方式展現出來
#include "iostream"
#include "vector"
#include "algorithm"
using namespace std;
bool cmp(const pair<char,int>& p1,const pair<char,int>& p2){if(p1.second!=p2.second) return p1.second>p2.second;return p1.first<p2.first; // 升序
}
int main(){ // 這是個啥玩意,天啊,簡直嘍// C代表“錘子”、J代表“剪刀”、B代表“布”,分別除下vector<pair<char,int>> vec1{{'C',0},{'J',0},{'B',0}};vector<pair<char,int>> vec2{{'C',0},{'J',0},{'B',0}};int n;cin>>n;int a=0,b=0,c=0;char k1,k2;// 只需要,3個字母就能將勝負表示while(n--){cin>>k1>>k2;if(k1==k2){ // 平局b++;}else if((k1=='C'&&k2=='J')||(k1=='J'&&k2=='B')||(k1=='B'&&k2=='C')){ // 甲勝a++;if(k1=='C') vec1[0].second++;if(k1=='J') vec1[1].second++;if(k1=='B') vec1[2].second++;// 把另一種方法補充上去}else if((k2=='C'&&k1=='J')||(k2=='J'&&k1=='B')||(k2=='B'&&k1=='C')){ // 乙勝c++;if(k2=='C') vec2[0].second++;if(k2=='J') vec2[1].second++;if(k2=='B') vec2[2].second++;}}sort(vec1.begin(),vec1.end(), cmp);sort(vec2.begin(),vec2.end(), cmp);cout<<a<<" "<<b<<" "<<c<<endl;cout<<c<<" "<<b<<" "<<a<<endl;cout<<vec1[0].first<<" "<<vec2[0].first<<endl;return 0;
}
// 當然以上是最麻煩的一種方法之一
// ..... 接下來看這個
/*using namespace std;
int main() {int n;cin >> n;int jiawin = 0, yiwin = 0;int jia[3] = {0}, yi[3] = {0};for (int i = 0; i < n; i++) {char s, t;cin >> s >> t;if (s == 'B' && t == 'C') {jiawin++;jia[0]++;} else if (s == 'B' && t == 'J') {yiwin++;yi[2]++;} else if (s == 'C' && t == 'B') {yiwin++;yi[0]++;} else if (s == 'C' && t == 'J') {jiawin++;jia[1]++;} else if (s == 'J' && t == 'B') {jiawin++;jia[2]++;} else if (s == 'J' && t == 'C') {yiwin++;yi[1]++;}}cout << jiawin << " " << n - jiawin - yiwin << " " << yiwin << endl << yiwin << " " << n - jiawin - yiwin << " " << jiawin << endl;int maxjia = jia[0] >= jia[1] ? 0 : 1;maxjia = jia[maxjia] >= jia[2] ? maxjia : 2;int maxyi = yi[0] >= yi[1] ? 0 : 1;maxyi = yi[maxyi] >= yi[2] ? maxyi : 2;char str[4] = {"BCJ"};cout << str[maxjia] << " " << str[maxyi];return 0;
}*/
9、1019. 數字黑洞 (20)
題目描述
給定任一個各位數字不完全相同的4位正整數,如果我們先把4個數字按非遞增排序,再按非遞減排序,然后用第1個數字減第2個數字,將得到一個新的數字。一直重復這樣做,我們很快會停在有“數字黑洞”之稱的6174,這個神奇的數字也叫Kaprekar常數。例如,我們從6767開始,將得到7766 - 6677 = 10899810 - 0189 = 96219621 - 1269 = 83528532 - 2358 = 61747641 - 1467 = 6174... ...現給定任意4位正整數,請編寫程序演示到達黑洞的過程。輸入描述:
輸入給出一個[1000, 10000)區間內的正整數N。輸出描述:
如果N的4位數字全相等,則在一行內輸出“N - N = 0000”;否則將計算的每一步在一行內輸出,直到6174作為差出現,輸出格式見樣例,每行中間沒有空行。注意每個數字按4位數格式輸出。輸入例子:
6767輸出例子:
7766 - 6677 = 10899810 - 0189 = 96219621 - 1269 = 83528532 - 2358 = 6174
#include <iostream>
#include <algorithm>
using namespace std;
// 夯實了,我對string-字符串的運用
bool cmp(char a, char b){ // 默認是從小到大,現在是從大到小return a>b;
}
int main(){ // string str,str1,str2,str3;cin>>str;int num1,num2,num; // while (1) {sort(str.begin(),str.end(),cmp);str1 = str;num1 = stoi(str1);sort(str.begin(),str.end());str2 = str;num2 = stoi(str2); num = num1-num2;str = to_string(num);str.insert(0,4-str.size(),'0');if(num==0){cout<<str1<<" - "<<str2<<" = "<<"0000"<<endl;break;} else {cout<<str1<<" - "<<str2<<" = "<<str<<endl;if(num==6174) break;}}return 0;
}
10、月餅 (25)
題目描述
月餅是中國人在中秋佳節時吃的一種傳統食品,不同地區有許多不同風味的月餅。現給定所有種類月餅的庫存量、總售價、以及市場的最大需 求量,請你計算可以獲得的最大收益是多少。注意:銷售時允許取出一部分庫存。樣例給出的情形是這樣的:假如我們有3種月餅,其庫存量分別為18、15、10萬噸,總售價分別為75、 72、45億元。如果市場的最大需求量只有20萬噸,那么我們最大收益策略應該是賣出全部15萬噸第2種月餅、以及5萬噸第3種月餅,獲得72 + 45/2 = 94.5(億元)。輸入描述:
每個輸入包含1個測試用例。每個測試用例先給出一個不超過1000的正整數N表示月餅的種類數、以及不超過500(以萬噸為單位)的正整數 D表示市場最大需求量。隨后一行給出N個正數表示每種月餅的庫存量(以萬噸為單位);最后一行給出N個正數表示每種月餅的總售價(以億 元為單位)。數字間以空格分隔。輸出描述:
對每組測試用例,在一行中輸出最大收益,以億元為單位并精確到小數點后2位。輸入例子:
3 20 18 15 10 75 72 45輸出例子:
94.50
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
// 對struct不在排擠,而是使用
// 認為細節扣到他腦子有坑,哭死
struct mooncake{int num;int money;double price;mooncake():num(0),money(0),price(0){} // 構造器
};bool cmp(mooncake m1, mooncake m2){ // 從小到大排序return m1.price>m2.price;
}
int main(){int n,d; // n種類,d市場cin>>n>>d;vector<mooncake> vec(n);for(int i=0; i<n; ++i) cin>>vec[i].num;for(int i=0; i<n; ++i){ // 計算cin>>vec[i].money;vec[i].price = (double)vec[i].money/vec[i].num;}sort(vec.begin(),vec.end(),cmp); // 挺好int remain = d;double money = 0;for(int i=0; i<vec.size(); ++i){if(remain>=vec[i].num){money += vec[i].money;remain -= vec[i].num;}else{money += remain*vec[i].price;remain = 0;}if(remain<=0) break;}printf("%.2lf",money);return 0;
}
?拓展
串的操作?::(拓展知識)::
串的操作,無非就是對 字符串 的 增刪改查
- 增 - 插入(insert)
- 刪 - 刪除某段字符(erase)
- 改 - 交換(swap),反轉(reverse)
- 查 - 截取片段(substr),查字符(find-string::npos)
#include "iostream"
using namespace std;int main(){// 增刪改查string str = "123";cout<<str<<endl;// 增 - 插入str.insert(0,1,'0');str.insert(0,"aaa");cout<<str<<endl;// 刪 - 刪除str.erase(0,1); // 用的好,甚至可以刪除某個特定字符cout<<str<<endl;// 改 - 交換,反轉string str2 = "00";str2.swap(str); - 反轉reverse(s.begin(), s.end());cout<<str<<endl;// 查 - 截取片段,查字符string str3 = str2.substr(0,3); // 截取cout<<str3<<endl;cout<<str3.find('0')<<endl;if(str3.find('1')==string::npos) cout<<"你好"<<endl;return 0;
}
借鑒網站:
1、牛客
2、PAT