PAT – 第5页 – 柳婼の blog

PAT 1144. The Missing Number (20) – 甲级

Given N integers, you are supposed to find the smallest positive integer that is NOT in the given list.
Input Specification:
Each input file contains one test case. For each case, the first line gives a positive integer N (<= 105). Then N integers are given in the next line, separated by spaces. All the numbers are in the range of int.
Output Specification:
Print in a line the smallest positive integer that is missing from the input list.
Sample Input:
10
5 -25 9 6 1 3 4 2 5 17
Sample Output:
7

题目大意：给n个数字，找到不在这个数字列表里面的最小的正整数
分析：将每个数字出现的次数存储在map里面，num从1开始，如果m[num] == 0说明不存在，则输出这个num～

#include <iostream>
#include <map>
using namespace std;
int main() {
    int n, a, num = 0;
    cin >> n;
    map<int, int> m;
    for (int i = 0; i < n; i++) {
        cin >> a;
        m[a]++;
    }
    while(++num)
        if (m[num] == 0) break;
    cout << num;
    return 0;
}

#include <iostream>

#include <map>

using namespace std;

int main() {

int n, a, num = 0;

cin >> n;

map<int, int> m;

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

cin >> a;

m[a]++;

}

while(++num)

if (m[num] == 0) break;

cout << num;

return 0;

}

1085. PAT单位排行 (25) -PAT乙级真题

每次 PAT 考试结束后，考试中心都会发布一个考生单位排行榜。本题就请你实现这个功能。
输入格式：
输入第一行给出一个正整数N（<=105），即考生人数。随后N行，每行按下列格式给出一个考生的信息：
准考证号得分学校
其中“准考证号”是由6个字符组成的字符串，其首字母表示考试的级别：“B”代表乙级，“A”代表甲级，“T”代表顶级；“得分”是 [0,100] 区间内的整数；“学校”是由不超过6个英文字母组成的单位码（大小写无关）。注意：题目保证每个考生的准考证号是不同的。
输出格式：
首先在一行中输出单位个数。随后按以下格式非降序输出单位的排行榜：
排名学校加权总分考生人数
其中“排名”是该单位的排名（从1开始）；“学校”是全部按小写字母输出的单位码；“加权总分”定义为“乙级总分/1.5 + 甲级总分 + 顶级总分*1.5”的整数部分；“考生人数”是该属于单位的考生的总人数。
学校首先按加权总分排行。如有并列，则应对应相同的排名，并按考生人数升序输出。如果仍然并列，则按单位码的字典序输出。
输入样例：
10
A57908 85 Au
B57908 54 LanX
A37487 60 au
T28374 67 CMU
T32486 24 hypu
A66734 92 cmu
B76378 71 AU
A47780 45 lanx
A72809 100 pku
A03274 45 hypu
输出样例：
5
1 cmu 192 2
1 au 192 3
3 pku 100 1
4 hypu 81 2
4 lanx 81 2

分析：两个map，一个cnt用来存储某学校名称对应的参赛人数，另一个sum计算某学校名称对应的总加权成绩。每次学校名称string school都要转化为全小写，将map中所有学校都保存在vector ans中，类型为node，node中包括学校姓名、加权总分、参赛人数。对ans数组排序，根据题目要求写好cmp函数，最后按要求输出。对于排名的处理：设立pres表示前一个学校的加权总分，如果pres和当前学校的加权总分不同，说明rank等于数组下标+1，否则rank不变～
注意：总加权分数取整数部分是要对最后的总和取整数部分，不能每次都直接用int存储，不然会有一个3分测试点不通过～
PS: 更新后的pat系统会导致之前使用map的代码最后一个测试点超时，更改为unordered_map即可AC～

#include <iostream>
#include <algorithm>
#include <cctype>
#include <vector>
#include <unordered_map>
using namespace std;
struct node {
    string school;
    int tws, ns;
};
bool cmp(node a, node b) {
    if (a.tws != b.tws)
        return a.tws > b.tws;
    else if (a.ns != b.ns)
        return a.ns < b.ns;
    else
        return a.school < b.school;
}
int main() {
    int n;
    scanf("%d", &n);
    unordered_map<string, int> cnt;
    unordered_map<string, double> sum;
    for (int i = 0; i < n; i++) {
        string id, school;
        cin >> id;
        double score;
        scanf("%lf", &score);
        cin >> school;
        for (int j = 0; j < school.length(); j++)
            school[j] = tolower(school[j]);
        if (id[0] == 'B')
            score = score / 1.5;
        else if (id[0] == 'T')
            score = score * 1.5;
        sum[school] += score;
        cnt[school]++;
    }
    vector<node> ans;
    for (auto it = cnt.begin(); it != cnt.end(); it++)
        ans.push_back(node{it->first, (int)sum[it->first], cnt[it->first]});
    sort(ans.begin(), ans.end(), cmp);
    int rank = 0, pres = -1;
    printf("%d\n", (int)ans.size());
    for (int i = 0; i < ans.size(); i++) {
        if (pres != ans[i].tws) rank = i + 1;
        pres = ans[i].tws;
        printf("%d ", rank);
        cout << ans[i].school;
        printf(" %d %d\n", ans[i].tws, ans[i].ns);
    }
    return 0;
}

#include <iostream>

#include <algorithm>

#include <cctype>

#include <vector>

#include <unordered_map>

using namespace std;

struct node {

string school;

int tws, ns;

};

bool cmp(node a, node b) {

if (a.tws != b.tws)

return a.tws > b.tws;

else if (a.ns != b.ns)

return a.ns < b.ns;

else

return a.school < b.school;

}

int main() {

int n;

scanf("%d", &n);

unordered_map<string, int> cnt;

unordered_map<string, double> sum;

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

string id, school;

cin >> id;

double score;

scanf("%lf", &score);

cin >> school;

for (int j = 0; j < school.length(); j++)

school[j] = tolower(school[j]);

if (id[0] == 'B')

score = score / 1.5;

else if (id[0] == 'T')

score = score * 1.5;

sum[school] += score;

cnt[school]++;

}

vector<node> ans;

for (auto it = cnt.begin(); it != cnt.end(); it++)

ans.push_back(node{it->first, (int)sum[it->first], cnt[it->first]});

sort(ans.begin(), ans.end(), cmp);

int rank = 0, pres = -1;

printf("%d\n", (int)ans.size());

for (int i = 0; i < ans.size(); i++) {

if (pres != ans[i].tws) rank = i + 1;

pres = ans[i].tws;

printf("%d ", rank);

cout << ans[i].school;

printf(" %d %d\n", ans[i].tws, ans[i].ns);

}

return 0;

}

1084. 外观数列 (20) -PAT乙级真题

外观数列是指具有以下特点的整数序列：
d, d1, d111, d113, d11231, d112213111, …
它从不等于 1 的数字 d 开始，序列的第 n+1 项是对第 n 项的描述。比如第 2 项表示第 1 项有 1 个 d，所以就是 d1；第 2 项是 1 个 d（对应 d1）和 1 个 1（对应 11），所以第 3 项就是 d111。又比如第 4 项是 d113，其描述就是 1 个 d，2 个 1，1 个 3，所以下一项就是 d11231。当然这个定义对 d = 1 也成立。本题要求你推算任意给定数字 d 的外观数列的第 N 项。
输入格式：
输入第一行给出[0,9]范围内的一个整数 d、以及一个正整数 N（<=40），用空格分隔。
输出格式：
在一行中给出数字 d 的外观数列的第 N 项。
输入样例：
1 8
输出样例：
1123123111

分析：用string s接收所需变幻的数字，每次遍历s，从当前位置i开始，看后面有多少个与s[i]相同，设j处开始不相同，那么临时字符串 t += s[i] + to_string(j – i);然后再将t赋值给s，cnt只要没达到n次就继续加油循环下一次，最后输出s的值～

#include <iostream>
using namespace std;
int main() {
    string s;
    int n, j;
    cin >> s >> n;
    for (int cnt = 1; cnt < n; cnt++) {
        string t;
        for (int i = 0; i < s.length(); i = j) {
            for (j = i; j < s.length() && s[j] == s[i]; j++);
            t += s[i] + to_string(j - i);
        }
        s = t;
    }
    cout << s;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

string s;

int n, j;

cin >> s >> n;

for (int cnt = 1; cnt < n; cnt++) {

string t;

for (int i = 0; i < s.length(); i = j) {

for (j = i; j < s.length() && s[j] == s[i]; j++);

t += s[i] + to_string(j - i);

}

s = t;

}

cout << s;

return 0;

}

1083. 是否存在相等的差 (20) -PAT乙级真题

给定 N 张卡片，正面分别写上 1、2、……、N，然后全部翻面，洗牌，在背面分别写上 1、2、……、N。将每张牌的正反两面数字相减（大减小），得到 N 个非负差值，其中是否存在相等的差？
输入格式：
输入第一行给出一个正整数 N（2 <= N <= 10000），随后一行给出 1 到 N 的一个洗牌后的排列，第 i 个数表示正面写了 i 的那张卡片背面的数字。
输出格式：
按照“差值重复次数”的格式从大到小输出重复的差值及其重复的次数，每行输出一个结果。
输入样例：
8
3 5 8 6 2 1 4 7
输出样例：
5 2
3 3
2 2

分析：所有差值出现的次数保存在a数组中，从后往前输出所有出现的次数>=2的值～

#include <iostream>
using namespace std;
int main() {
    int n, t, a[10000] = {0};
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> t;
        a[abs(t-i)]++;
    }
    for (int i = 9999; i >= 0; i--)
        if (a[i] >= 2) cout << i << " " << a[i] << endl;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, t, a[10000] = {0};

cin >> n;

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

cin >> t;

a[abs(t-i)]++;

}

for (int i = 9999; i >= 0; i--)

if (a[i] >= 2) cout << i << " " << a[i] << endl;

return 0;

}

1082. 射击比赛 (20) -PAT乙级真题

本题目给出的射击比赛的规则非常简单，谁打的弹洞距离靶心最近，谁就是冠军；谁差得最远，谁就是菜鸟。本题给出一系列弹洞的平面坐标(x,y)，请你编写程序找出冠军和菜鸟。我们假设靶心在原点(0,0)。
输入格式：
输入在第一行中给出一个正整数 N（<= 10 000）。随后 N 行，每行按下列格式给出：
ID x y
其中 ID 是运动员的编号（由4位数字组成）；x 和 y 是其打出的弹洞的平面坐标(x,y)，均为整数，且 0 <= |x|, |y| <= 100。题目保证每个运动员的编号不重复，且每人只打 1 枪。
输出格式：
输出冠军和菜鸟的编号，中间空 1 格。题目保证他们是唯一的。
输入样例：
3
0001 5 7
1020 -1 3
0233 0 -1
输出样例：
0233 0001

分析：
1、注意n=1的情况，即冠军和菜鸟都是同一个人的情况（第二个测试点）
2.、注意距离越大的越菜～

#include <iostream>
using namespace std;
int main() {
    int n, id, x, y, maxid, maxdis = -1, minid, mindis = 99999;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> id >> x >> y;
        int dis = x * x + y * y;
        if (dis > maxdis) maxid = id;
        if (dis < mindis) minid = id;
        maxdis = max(maxdis, dis);
        mindis = min(mindis, dis);
    }
    printf("%04d %04d", minid, maxid);
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, id, x, y, maxid, maxdis = -1, minid, mindis = 99999;

cin >> n;

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

cin >> id >> x >> y;

int dis = x * x + y * y;

if (dis > maxdis) maxid = id;

if (dis < mindis) minid = id;

maxdis = max(maxdis, dis);

mindis = min(mindis, dis);

}

printf("%04d %04d", minid, maxid);

return 0;

}

1081. 检查密码 (15) -PAT乙级真题

本题要求你帮助某网站的用户注册模块写一个密码合法性检查的小功能。该网站要求用户设置的密码必须由不少于6个字符组成，并且只能有英文字母、数字和小数点”.”，还必须既有字母也有数字。
输入格式：
输入第一行给出一个正整数 N（<=100），随后 N 行，每行给出一个用户设置的密码，为不超过80个字符的非空字符串，以回车结束。
输出格式：
对每个用户的密码，在一行中输出系统反馈信息，分以下5种：
如果密码合法，输出“Your password is wan mei.”；
如果密码太短，不论合法与否，都输出“Your password is tai duan le.”；
如果密码长度合法，但存在不合法字符，则输出“Your password is tai luan le.”；
如果密码长度合法，但只有字母没有数字，则输出“Your password needs shu zi.”；
如果密码长度合法，但只有数字没有字母，则输出“Your password needs zi mu.”。
输入样例：
5
123s
zheshi.wodepw
1234.5678
WanMei23333
pass*word.6
输出样例：
Your password is tai duan le.
Your password needs shu zi.
Your password needs zi mu.
Your password is wan mei.
Your password is tai luan le.

分析：非空字符串，每个字符串以回车结束，但是字符串里面可能会有空格，所以不能直接用cin，要用getline接收一行字符。在接收完n后要getchar()读取一下换行符才能用getline，否则换行符会被读进getline中～

#include <iostream>
#include <cctype>
using namespace std;
int main() {
    int n;
    cin >> n; getchar();
    for (int i = 0; i < n; i++) {
        string s;
        getline(cin, s);
        if (s.length() >= 6) {
            int invalid = 0, hasAlpha = 0, hasNum = 0;
            for (int j = 0; j < s.length(); j++) {
                if (s[j] != '.' && !isalnum(s[j])) invalid = 1;
                else if (isalpha(s[j])) hasAlpha = 1;
                else if (isdigit(s[j])) hasNum = 1;
            }
            if (invalid == 1) cout << "Your password is tai luan le.\n";
            else if (hasNum == 0) cout << "Your password needs shu zi.\n";
            else if (hasAlpha == 0) cout << "Your password needs zi mu.\n";
            else cout << "Your password is wan mei.\n";
        } else
            cout << "Your password is tai duan le.\n";
    }
    return 0;
}

#include <iostream>

#include <cctype>

using namespace std;

int main() {

int n;

cin >> n; getchar();

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

string s;

getline(cin, s);

if (s.length() >= 6) {

int invalid = 0, hasAlpha = 0, hasNum = 0;

for (int j = 0; j < s.length(); j++) {

if (s[j] != '.' && !isalnum(s[j])) invalid = 1;

else if (isalpha(s[j])) hasAlpha = 1;

else if (isdigit(s[j])) hasNum = 1;

}

if (invalid == 1) cout << "Your password is tai luan le.\n";

else if (hasNum == 0) cout << "Your password needs shu zi.\n";

else if (hasAlpha == 0) cout << "Your password needs zi mu.\n";

else cout << "Your password is wan mei.\n";

} else

cout << "Your password is tai duan le.\n";

}

return 0;

}