算法 – 第4页

1038. 统计同成绩学生(20)-PAT乙级真题

本题要求读入N名学生的成绩，将获得某一给定分数的学生人数输出。
输入格式：
输入在第1行给出不超过 10^5 的正整数N，即学生总人数。随后1行给出N名学生的百分制整数成绩，中间以空格分隔。最后1行给出要查询的分数个数K（不超过N的正整数），随后是K个分数，中间以空格分隔。
输出格式：
在一行中按查询顺序给出得分等于指定分数的学生人数，中间以空格分隔，但行末不得有多余空格。
输入样例：
10
60 75 90 55 75 99 82 90 75 50
3 75 90 88
输出样例：
3 2 0

分析：用b数组保存每个分数对应的学生人数，在输入的时候，对于每一个成绩temp，b[temp]++表示将数组b中对应分数的人数+1～对于m个查询，每一次都输出需要查询的temp所对应的人数b[temp]，注意i不等于0的时候要在输出人数之前输出一个空格～

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n, m, temp;
    scanf("%d", &n);
    vector<int> b(101);
    for (int i = 0; i < n; i++) {
        scanf("%d", &temp);
        b[temp]++;
    }
    scanf("%d", &m);
    for (int i = 0; i < m; i++) {
        scanf("%d", &temp);
        if (i != 0) printf(" ");
        printf("%d", b[temp]);
    }
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

int n, m, temp;

scanf("%d", &n);

vector<int> b(101);

for (int i = 0; i < n; i++) {

scanf("%d", &temp);

b[temp]++;

}

scanf("%d", &m);

for (int i = 0; i < m; i++) {

scanf("%d", &temp);

if (i != 0) printf(" ");

printf("%d", b[temp]);

}

return 0;

}

1037. 在霍格沃茨找零钱（20）-PAT乙级真题

如果你是哈利·波特迷，你会知道魔法世界有它自己的货币系统 —— 就如海格告诉哈利的：“十七个银西可(Sickle)兑一个加隆(Galleon)，二十九个纳特(Knut)兑一个西可，很容易。”现在，给定哈利应付的价钱P和他实付的钱A，你的任务是写一个程序来计算他应该被找的零钱。
输入格式：
输入在1行中分别给出P和A，格式为“Galleon.Sickle.Knut”，其间用1个空格分隔。这里Galleon是[0, 10^7]区间内的整数，Sickle是[0, 17)区间内的整数，Knut是[0, 29)区间内的整数。
输出格式：
在一行中用与输入同样的格式输出哈利应该被找的零钱。如果他没带够钱，那么输出的应该是负数。
输入样例1：
10.16.27 14.1.28
输出样例1：
3.2.1
输入样例2：
14.1.28 10.16.27
输出样例2：
-3.2.1

分析：abc代表应付的钱，mnt代表实付的钱，首先判断应付的钱是否大于实付的钱，如果大于，说明钱不够，为了简化计算，将a和m、b和n、c和t调换，使得计算(mnt-abc)时是大的减去小的～调换之后别忘记输出负号～xyz分别代表找的钱，从低位向高位计算，如果t < c，说明要向前借位，借一位后自己加上29，否则z = t – c即可～别忘记如果有借位，n要减去1～然后计算中间位，如果n < b，说明要借位，则y = n – b + 17，否则不用借位，y = n – b即可～最后计算最高位x，如果n < b引起了借位，则x = m – a – 1，否则x = m – a即可～最后输出x.y.z～

#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;
}

#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;

}

1036. 跟奥巴马一起编程(15)-PAT乙级真题

美国总统奥巴马不仅呼吁所有人都学习编程，甚至以身作则编写代码，成为美国历史上首位编写计算机代码的总统。2014年底，为庆祝“计算机科学教育周”正式启动，奥巴马编写了很简单的计算机代码：在屏幕上画一个正方形。现在你也跟他一起画吧！
输入格式：
输入在一行中给出正方形边长N（3<=N<=20）和组成正方形边的某种字符C，间隔一个空格。
输出格式：
输出由给定字符C画出的正方形。但是注意到行间距比列间距大，所以为了让结果看上去更像正方形，我们输出的行数实际上是列数的50%（四舍五入取整）。
输入样例：
10 a
输出样例：
aaaaaaaaaa
a a
a a
a a
aaaaaaaaaa

分析：为了让结果看上去更像正方形，输出的行数实际上是列数的50%（四舍五入取整），列数是N，则行数t = N / 2 + N % 2，表示偶数等于除以2，奇数要除以2加1的意思，这样才能满足四舍五入～首先输出第一行，N个c，然后输出中间t-2行，最左边和最右边为一个c，中间为N-2个空格，最后输出最后一行，N个c～

#include <iostream>
using namespace std;
int main() {
    int N;
    char c;
    cin >> N >> c;
    int t = N / 2 + N % 2;
    for (int i = 0; i < N; i++)
        cout << c;
    cout << endl;
    for (int i = 0; i < t - 2; i++) {
        cout << c;
        for (int k = 0; k < N - 2; k++)
            cout << " ";
        cout << c << endl;
    }
    for (int i = 0; i < N; i++)
        cout << c;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int N;

char c;

cin >> N >> c;

int t = N / 2 + N % 2;

for (int i = 0; i < N; i++)

cout << c;

cout << endl;

for (int i = 0; i < t - 2; i++) {

cout << c;

for (int k = 0; k < N - 2; k++)

cout << " ";

cout << c << endl;

}

for (int i = 0; i < N; i++)

cout << c;

return 0;

}

1032. 挖掘机技术哪家强(20)-PAT乙级真题

为了用事实说明挖掘机技术到底哪家强，PAT组织了一场挖掘机技能大赛。现请你根据比赛结果统计出技术最强的那个学校。
输入格式：
输入在第1行给出不超过10^5的正整数N，即参赛人数。随后N行，每行给出一位参赛者的信息和成绩，包括其所代表的学校的编号（从1开始连续编号）、及其比赛成绩（百分制），中间以空格分隔。
输出格式：
在一行中给出总得分最高的学校的编号、及其总分，中间以空格分隔。题目保证答案唯一，没有并列。
输入样例：
6
3 65
2 80
1 100
2 70
3 40
3 0
输出样例：
2 150

分析：用数组a保存每个学校的编号对应的总分，在输入时将每一个分数score累加到学校编号num对应的a[num]中，然后遍历整个数组，将总分最高的学校编号保存在变量 t 中，将最高总分保存在max中，最后输出t和max的值～

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

#include <iostream>

#include <vector>

using namespace std;

int main() {

int N;

cin >> N;

vector<int> a(N + 1);

int num, score;

for (int i = 0; i < N; i++) {

cin >> num >> score;

a[num] += score;

}

int max = a[1], t = 1;

for (int i = 2; i <= N; i++) {

if (max < a[i]) {

max = a[i];

t = i;

}

cout << t << " " << max;

return 0;

}

1031. 查验身份证(15)-PAT乙级真题

一个合法的身份证号码由17位地区、日期编号和顺序编号加1位校验码组成。校验码的计算规则如下：
首先对前17位数字加权求和，权重分配为：{7，9，10，5，8，4，2，1，6，3，7，9，10，5，8，4，2}；
然后将计算的和对11取模得到值Z；最后按照以下关系对应Z值与校验码M的值：
Z：0 1 2 3 4 5 6 7 8 9 10
M：1 0 X 9 8 7 6 5 4 3 2
现在给定一些身份证号码，请你验证校验码的有效性，并输出有问题的号码。
输入格式：
输入第一行给出正整数N（<= 100）是输入的身份证号码的个数。随后N行，
每行给出1个18位身份证号码。
输出格式：
按照输入的顺序每行输出1个有问题的身份证号码。这里并不检验前17位是否合理，只检查前17位是否全为数字且最后1位校验码计算准确。如果所有号码都正常，则输出“All passed”。
输入样例1：
4
320124198808240056
12010X198901011234
110108196711301866
37070419881216001X
输出样例1：
12010X198901011234
110108196711301866
37070419881216001X
输入样例2：
2
320124198808240056
110108196711301862
输出样例2：
All passed

分析：isTrue函数判断身份证号是否正常，如果不正常返回false，判断每一个给出的身份证号，如果不正常，就输出这个身份证号，并且置flag=1表示有不正常的号码，如果所有的号码都是正常，即flag依旧等于0，则输出All passed～在isTrue函数中，先判断前17位是否是数字，如果不是，直接return false，如果是，就将当前字符转化为数字并与a[i]相乘，累加在sum中，对于第18位，如果是X要转化为10～比较b[sum%11]和第18位是否相等，如果相等就返回true，不相等就返回false～

#include <iostream>
using namespace std;
int a[17] = {7, 9, 10, 5, 8, 4, 2, 1, 6, 3, 7, 9, 10, 5, 8, 4, 2};
int b[11] = {1, 0, 10, 9, 8, 7, 6, 5, 4, 3, 2};
string s;
bool isTrue() {
    int sum = 0;
    for (int i = 0; i < 17; i++) {
        if (s[i] < '0' || s[i] > '9') return false;
        sum += (s[i] - '0') * a[i];
    }
    int temp = (s[17] == 'X') ? 10 : (s[17] - '0');
    return b[sum%11] == temp;
}
int main() {
    int n, flag = 0;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> s;
        if (!isTrue()) {
            cout << s << endl;
            flag = 1;
        }
    }
    if (flag == 0) cout << "All passed";
    return 0;
}

#include <iostream>

using namespace std;

int a[17] = {7, 9, 10, 5, 8, 4, 2, 1, 6, 3, 7, 9, 10, 5, 8, 4, 2};

int b[11] = {1, 0, 10, 9, 8, 7, 6, 5, 4, 3, 2};

string s;

bool isTrue() {

int sum = 0;

for (int i = 0; i < 17; i++) {

if (s[i] < '0' || s[i] > '9') return false;

sum += (s[i] - '0') * a[i];

}

int temp = (s[17] == 'X') ? 10 : (s[17] - '0');

return b[sum%11] == temp;

}

int main() {

int n, flag = 0;

cin >> n;

for (int i = 0; i < n; i++) {

cin >> s;

if (!isTrue()) {

cout << s << endl;

flag = 1;

}

if (flag == 0) cout << "All passed";

return 0;

}

1029. 旧键盘(20)-PAT乙级真题

旧键盘上坏了几个键，于是在敲一段文字的时候，对应的字符就不会出现。现在给出应该输入的一段文字、以及实际被输入的文字，请你列出肯定坏掉的那些键。
输入格式：
输入在2行中分别给出应该输入的文字、以及实际被输入的文字。每段文字是不超过80个字符的串，由字母A-Z（包括大、小写）、数字0-9、以及下划线“_”（代表空格）组成。题目保证2个字符串均非空。
输出格式：
按照发现顺序，在一行中输出坏掉的键。其中英文字母只输出大写，每个坏键只输出一次。题目保证至少有1个坏键。
输入样例：
7_This_is_a_test
_hs_s_a_es
输出样例：
7TI

分析：用string的find函数～遍历字符串s1，当当前字符s1[i]不在s2中，它的大写也不在ans中时，将当前字符的大写放入ans中，最后输出ans字符串即可～
ps：感谢github上的@xiaorong61给我发的pull request中strchr()函数带来的灵感～让我想到了曾经用过的string的find函数～

#include <iostream>
#include <cctype>
using namespace std;
int main() {
    string s1, s2, ans;
    cin >> s1 >> s2;
    for (int i = 0; i < s1.length(); i++)
        if (s2.find(s1[i]) == string::npos && ans.find(toupper(s1[i])) == string::npos)
            ans += toupper(s1[i]);
    cout << ans;
    return 0;
}

#include <iostream>

#include <cctype>

using namespace std;

int main() {

string s1, s2, ans;

cin >> s1 >> s2;

for (int i = 0; i < s1.length(); i++)

if (s2.find(s1[i]) == string::npos && ans.find(toupper(s1[i])) == string::npos)

ans += toupper(s1[i]);

cout << ans;

return 0;

}