PAT乙级学习笔记（三）

发表于 2020-02-19 更新于 2020-02-27 分类于 PAT

##续接PAT乙级学习笔记（二）
##以下PAT乙级其它题目
1.B1015德才论。对于这样的有多数据的比较，先建立结构体，然后写好cmp函数，注意函数一定要写return！！！看题目的时候一定要注意哪些是大于，不大于，哪些是小于，不小于！！

#include<iostream>
#include<set>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
struct node{
string name;
int de, cai, sum;
};
int cmp(node a, node b){
if(a.sum != b.sum) 
    return a.sum > b.sum;
else if(a.de != b.de) 
    return a.de > b.de;
else 
    return a.name < b.name;
}
vector<node> v[4];
int main(){
int n, l, h;
cin >> n >> l >> h;
int d, c, cnt = n;
for(int i = 0; i < n; i++){
    string s;
    cin >> s >> d >> c;
    if(d < l || c < l) cnt--;
    else if(d >= h && c >= h){
        v[0].push_back(node{s, d, c, d + c});
    }
    else if(d >= h && c < h ){
        v[1].push_back(node{s, d, c, d + c});
    }
    else if(d < h && c < h && d >= c){
        v[2].push_back(node{s, d, c, d + c});
    }
    else 
        v[3].push_back(node{s, d, c, d + c});
}

cout << cnt << endl;
for( int i = 0; i < 4; i++){
    sort(v[i].begin(),v[i].end(),cmp);
    for(int j = 0; j < v[i].size(); j++)
        printf("%s %d %d\n",v[i][j].name.c_str(), v[i][j].de, v[i][j].cai);
}
return 0;
}

2.B1017A除以 B。跌跌撞撞的把题做出来了，但是代码冗长不精简，下面是我的代码：

#include<iostream>
#include<set>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
string a;
int b; 
cin >> a >> b;
int len = a.length();
int q[len],r = 0;
for(int i = 0; i < len; i++){
    r = r * 10 + a[i]-'0'; 
    if(r < b) q[i] = 0;
    else{
        q[i] = r / b;
        r = r % b;
    }
}
if(len == 1 && a[0] - '0' < b){
    cout << 0 << " " << r;
    return 0;
}
int pos = 0;
for(int i = 0; i < len; i++){
    if(q[i] == 0) pos++;
    else break;
}
for(int i = pos; i < len; i++){
     cout << q[i];
}
cout << " " << r;
return 0;
}

下面是柳神的代码，真的十分精简并且一气呵成！！！

#include<iostream>
#include<set>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
string s;
int a, t = 0, temp = 0;
cin >> s >> a;
int len = s.length();
t = (s[0] -  '0') / a;
//下面表示先特殊处理一下第一位 
if((t != 0 && len > 1) || len == 1)
    cout << t;
//下面表示处理其它位
temp = (s[0] - '0') % a;
for(int i = 1; i < len; i++){
    t = (temp * 10 + s[i] - '0') / a;
    cout << t;
    temp = (temp * 10 + s[i] - '0') % a;
} 
cout << " " << temp;
return 0;
}

3.BD进制的A+B。这道题注意柳神代码中如何反向输出数组中的元素，将i设为全局变量，循环的时候使用whil循环，代码更加精简。
#include
#include
#include
#include
#include
using namespace std;
int main(){
int a, b, d;
cin >> a >> b >> d;
int t = a + b;
if(t == 0) {
cout << 0;
return 0;
}
int s[100];
int i = 0;
while(t != 0){
s[i++] = t % d;
t = t / d;
}
for(int j = i - 1; j >= 0; j–){
cout << s[j];
}
return 0;
}
4.B1023组个最小的数。这道题相对简单，感觉我的做法要比柳神的更好理解一些，代码长度差不多：

#include<iostream>
#include<set>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
int a[10];
for(int i = 0; i < 10; i++){
    scanf("%d",&a[i]);    
}
if(a[0] != 0){
    for(int j = 1; j < 10; j++){
        if(a[j] > 0){
            cout << j;
            a[j]--;
            break;
        }
    }
}
for(int i = 0; i < 10; i++){
    while(a[i]-- > 0) cout << i;
}
return 0;
}

5.B1027打印沙漏。这道题参考的柳神的代码：

#include <iostream>
using namespace std;
int main() {
int N, row = 0;
char c;
cin >> N >> c;
for (int i = 0; i < N; i++) {
    if ((2 * i * (i + 2) + 1) > N) {
        row = i - 1;
        break;
    }
}
for (int i = row; i >= 1; i--) {
    for (int k = row - i; k >= 1; k--) cout << " ";
    for (int j = i * 2 + 1; j >= 1; j--) cout << c;
    cout << endl;
}
for (int i = 0; i < row; i++) cout << " ";
cout << c << endl;
for (int i = 1; i <= row; i++) {
    for (int k = row - i; k >= 1; k--) cout << " ";
    for (int j = i * 2 + 1; j >= 1; j--) cout << c;
    cout << endl;
}
cout << (N - (2 * row * (row + 2) + 1));
return 0;
}

6.B1028人口普查。这道题注意，先设置最大和最小的极限情况，然后一一遍历，得出情况。判断是否合法可以使用一个函数来实现，注意当没有合法生日的时候，不应该输出名字！！！我的代码如下：

#include<iostream>
#include<set>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
bool isright(int y, int m, int d){
if(y > 2014 || y == 2014 && m > 9 || y == 2014 && m == 9 && d > 6){
    return false;
}
else if(y < 1814 || y == 1814 && m < 9 || y == 1814 && m == 9 && d < 6){
    return false;
} 
else return true;
}
int main(){
int n,cnt = 0;
string s, maxs, mins;
int y, m, d, maxy = 2014 , maxm = 9, maxd = 6, miny = 1814, minm = 9, mind = 6;
cin >> n;
for(int i = 0; i < n; i++){
    cin >> s;
    scanf("%d/%d/%d", &y, &m, &d);
    if(isright(y, m, d)){
        cnt++;
        if(y > miny || y == miny  && m > minm || y == miny && m == minm && d > mind){
            mins = s;
            miny = y;
            minm = m;
            mind = d;
        }
        if(y < maxy || y == maxy  && m < maxm || y == maxy && m == maxm && d < maxd){
            maxs = s;
            maxy = y;
            maxm = m;
            maxd = d;
        }
    }    
} 
if(cnt == 0) cout << 0;
else cout << cnt << " " << maxs << " " << mins;
return 0;
}

看完柳神的代码，真的自叹不如。判断生日大小直接采用字符串比较，我还多写了一个函数，还要分情况讨论，代码写的真的冗长，附上柳神的代码：

#include <iostream>
using namespace std;
int main() {
int n, cnt = 0;
cin >> n;
string name, birth, maxname, minname, maxbirth = "1814/09/06", minbirth = "2014/09/06";
for (int i = 0; i < n; i++) {
    cin >> name >> birth;
    if (birth >= "1814/09/06" && birth <= "2014/09/06") {
        cnt++;
        if (birth >= maxbirth) {
            maxbirth = birth;
            maxname = name;
        }
        if (birth <= minbirth) {
            minbirth = birth;
            minname = name;
        }
    }
}
cout << cnt;
if (cnt != 0) cout << " " << minname << " " << maxname;
return 0;
}

7.B1030完美数列。这道题注意溢出的情况int最多2*10^9，所以p要设置为lonlong类型，要是超时的时候可以考虑两个for循环的代码优化，外层for循环不优化也可以，因为如果条件不满足没有语句执行，思考问题的时候最好是正向思维，避免出错，如果j从最后一项开始遍历，就比较乱

#include<iostream>
#include<algorithm>
using namespace std;
int main(){
int n;
long p;
cin >> n >> p;
int a[n];
for(int k = 0; k < n; k++){
    scanf("%d",&a[k]);
} 
sort(a,a + n);
int maxcnt = 0,temp = 0;
for(int i = 0; i <= n; i++){
    for(int j = i + maxcnt; j < n; j++){
        if(a[j] <= p * a[i]){
            temp = j - i + 1;
            if(temp > maxcnt) maxcnt = temp;
        }
        else break;    
    }    
}
cout << maxcnt;
return 0;
}

8.B1032挖掘机技术哪家强。这道题比较简单，注意审题，题目中说没有重复并列，学校序号从0开始连续编号，所以简单不少，注意柳神当中把最大值当做第一个，遍历从第二项开始遍历的写法，下面是我的代码：

#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    int n;
    cin >> n;
    int a[n + 1] = {0};
    for(int i = 0; i < n; i++ ){
        int sch, score;
        cin >> sch >> score;
        a[sch] += score;
    } 
    int max = 0,t = 0;
    for(int i = 1; i <= n; i++){
        if(a[i] >= max){
            max = a[i];
            t = i;    
        }
    }
cout << t << " "<< max;
return 0;
}

9.B1036跟奥巴马一起学编程。这道题相对简单，注意每一列之间没有空格，就直接是换行，下面是代码：

#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    int n;
    char c;
    cin >> n >> c;
    int row = n % 2 == 0 ? n / 2 : n / 2 + 1;
    for(int i = 0; i < n; i++) cout << c;
    cout << endl;
    for(int i = 0; i < row - 2; i++){
        cout << c;
        for(int j = 0; j < n - 2; j++) cout << " ";
        cout << c << endl;
    }
    for(int i = 0; i < n; i++) cout << c;
return 0;
}

注意体会柳神代码中如何分类奇数和偶数的写法,真的是比我的简单多了
int t = N / 2 + N % 2;

10.B1037在霍格沃茨找零钱。这道题比较简单，看成是计算时间的那道题即可，下面是代码：

#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    int g1, s1, k1, g2, s2, k2;
    scanf("%d.%d.%d %d.%d.%d",&g1, &s1, &k1, &g2, &s2, &k2);
    int a, b;
    a = g1 * 17 * 29 + s1 *29 + k1;
    b = g2 * 17 * 29 + s2 *29 + k2;
    int ans;
    if(a > b){
        cout << "-";
        ans = a - b;
    }
    else ans = b - a;
    int g, s, k;
    g = ans / (17 * 29);
    s = (ans - g * 17 *29) / 29;
    k = ans - g * 17 * 29 - s *29;
    cout << g << "." << s << "." << k;
    return 0;
}

看了柳神的代码，采用模拟减法运算的方法，简直是太妙了!,附上柳神的代码

#include <iostream>
using namespace std;
int main() {
    int a, b ,c, m, n, t, x, y, z;
    scanf("%d.%d.%d %d.%d.%d",&a, &b, &c, &m, &n, &t);
    if (a > m || (a == m && b > n) || (a == m && b == n && c > t)) {
        swap(a, m); swap(b, n); swap(c, t);
        printf("-");        
    }
    z = t < c ? t - c + 29 : t - c;
    n = t < c ? n - 1 : n;
    y = n < b ? n - b + 17 : n - b;
    x = n < b ? m - a - 1 : m - a;
    printf("%d.%d.%d", x, y, z);
    return 0;
}

11.B1041考试座位号。注意如果没有使用循环中的i作为循环体内的数据的时候，尽量让i从0开始，下面是我的代码，这道题和mooc考试成绩，危险品装箱题型类似，注意体会：

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct node{
    string id;
    int a, b;
};
int main(){
    int n;
    cin >> n;
    vector<node> v;
    for(int i = 0; i < n; i++){
        string s;
        int a, b;
        cin >> s >> a >> b;
        v.push_back(node{s, a, b});
    }
    int m;
    cin >> m;
    for(int j = 0; j < m; j++){
        int temp;
        cin >> temp;
        for(int i = 0; i < n; i++){
            if(v[i].a == temp) cout << v[i].id << " " << v[i].b << endl;
        }
    } 
return 0;
}

柳神采用的是string类型的二维数组，更加简单！！

#include <iostream>
using namespace std;
int main() {
    string stu[1005][2], s1, s2;;
    int n, m, t;
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> s1 >> t >> s2;
        stu[t][0] = s1;
        stu[t][1] = s2; 
    } 
    cin >> m;
    for(int i = 0; i < m; i++) {
        cin >> t;
        cout << stu[t][0] << " " << stu[t][1] << endl;
    } 
    return 0;
}

12.B1055集体照。结构体定义struct要放在cmp之前。输入结构体可以直接cin>>v[i].name，不需要临时变量，然后push_back(node{s,a})。注意体会柳神代码中的空格的输出方式。就是先输出第一项，然后输出空格加第i项。将整个题目转换为不同人数的行的计算，不用分类讨论更简单。先左后右不递增就是排序中每隔一个一输出。

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
struct node{
    string name;
    int high;
}; 
bool cmp1(struct node a,struct node b){
    if(a.high != b.high) return a.high > b.high;
    else return a.name < b.name; 
}
int main(){
    int n, k, m;
    cin >> n >> k;
    vector <node> v(n);
    for(int i = 0; i < n; i++){
        cin >> v[i].name;
        cin >> v[i].high;
    } 
    sort(v.begin(),v.end(),cmp1);
    int t = 0, row = k;//t是v的下标，是每一排起始的数 
    while(row){
        if(row == k)
            m = n - n / k * (k - 1);
        else 
            m = n / k;
        
        vector<string> ans(m);
        ans[m / 2] = v[t].name;
        
        int j = m / 2 - 1;
        for(int i = t + 1; i < t + m; i = i + 2) 
            ans[j--] = v[i].name;
        
        j = m / 2 + 1;
        for(int i = t + 2; i < t + m; i = i + 2)
            ans[j++] = v[i].name;
            
        cout << ans[0];
        for(int i = 1; i < m; i++)
            cout << " " << ans[i];
        cout << endl;
        t = t + m;
        row--; 
    }    
    return 0;
}

13.B1057数零壹。这道题比较简单，注意十进制如何转换为二进制，方法要注意，当和为零的时候，应该输出0 0，下面是代码：

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cctype>
using namespace std;
int main(){
    string s;
    getline(cin,s);
    int sum = 0;
    for(int i = 0; i < s.length(); i++){
        if(isalpha(s[i])){
            s[i] = tolower(s[i]);
            sum += s[i] - 'a' + 1;
        }
    } 
    int a = 0, b = 0;
        while(sum != 0){
            if(sum % 2 == 0) a++;
            else b++;
            sum /= 2; 
        }
        cout << a << " " << b;
    return 0;
}

14.B1061判断题。水题，比较简单，注意写的时候认真点：

#include <iostream>
using namespace std;
int main(){
    int n, m;
    cin >> n >> m;
    int score[m], right[m];
    for(int i = 0; i < m; i++) cin >> score[i];
    for(int i = 0; i < m; i++) cin >> right[i];
    int sum[n] = {0};
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            int a;
            cin >> a;
            if(a == right[j]) sum[i] += score[j];
        }
        cout << sum[i] << endl;
    }
    return 0;
}