柳婼の blog – 第92页 – 我不管，反正我最萌～

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;

}

PAT 1142. Maximal Clique (25) – 甲级

A clique is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent. A maximal clique is a clique that cannot be extended by including one more adjacent vertex. (Quoted from https://en.wikipedia.org/wiki/Clique_(graph_theory))
Now it is your job to judge if a given subset of vertices can form a maximal clique.
Input Specification:
Each input file contains one test case. For each case, the first line gives two positive integers Nv (<= 200), the number of vertices in the graph, and Ne, the number of undirected edges. Then Ne lines follow, each gives a pair of vertices of an edge. The vertices are numbered from 1 to Nv.
After the graph, there is another positive integer M (<= 100). Then M lines of query follow, each first gives a positive number K (<= Nv), then followed by a sequence of K distinct vertices. All the numbers in a line are separated by a space.
Output Specification:
For each of the M queries, print in a line “Yes” if the given subset of vertices can form a maximal clique; or if it is a clique but not a maximal clique, print “Not Maximal”; or if it is not a clique at all, print “Not a Clique”.
Sample Input:
8 10
5 6
7 8
6 4
3 6
4 5
2 3
8 2
2 7
5 3
3 4
6
4 5 4 3 6
3 2 8 7
2 2 3
1 1
3 4 3 6
3 3 2 1
Sample Output:
Yes
Yes
Yes
Yes
Not Maximal
Not a Clique

题目大意：clique是一个点集，在一个无向图中，这个点集中任意两个不同的点之间都是相连的。maximal clique是一个clique，这个clique不可以再加入任何一个新的结点构成新的clique。点编号从1～nv，给出ne条边，以一对结点编号的方式给出。然后给出m条询问，每个询问是一个点集合，问这个点集合是否是maximal clique、是否是clique～
分析：先判断是否是clique，即判断是否任意两边都相连；之后判断是否是maximal，即遍历所有不在集合中的剩余的点，看是否存在一个点满足和集合中所有的结点相连，最后如果都满足，那就输出Yes表示是Maximal clique～

#include <iostream>
#include <vector>
using namespace std;
int e[210][210];
int main() {
    int nv, ne, m, ta, tb, k;
    scanf("%d %d", &nv, &ne);
    for (int i = 0; i < ne; i++) {
        scanf("%d %d", &ta, &tb);
        e[ta][tb] = e[tb][ta] = 1;
    }
    scanf("%d", &m);
    for (int i = 0; i < m; i++) {
        scanf("%d", &k);
        vector<int> v(k);
        int hash[210] = {0}, isclique = 1, isMaximal = 1;
        for (int j = 0; j < k; j++) {
            scanf("%d", &v[j]);
            hash[v[j]] = 1;
        }
        for (int j = 0; j < k; j++) {
            if (isclique == 0) break;
            for (int l = j + 1; l < k; l++) {
                if (e[v[j]][v[l]] == 0) {
                    isclique = 0;
                    printf("Not a Clique\n");
                    break;
                }
            }
        }
        if (isclique == 0) continue;
        for (int j = 1; j <= nv; j++) {
            if (hash[j] == 0) {
                for (int l = 0; l < k; l++) {
                    if (e[v[l]][j] == 0) break;
                    if (l == k - 1) isMaximal = 0;
                }
            }
            if (isMaximal == 0) {
                printf("Not Maximal\n");
                break;
            }
        }
        if (isMaximal == 1) printf("Yes\n");
    }
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int e[210][210];

int main() {

int nv, ne, m, ta, tb, k;

scanf("%d %d", &nv, &ne);

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

scanf("%d %d", &ta, &tb);

e[ta][tb] = e[tb][ta] = 1;

}

scanf("%d", &m);

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

scanf("%d", &k);

vector<int> v(k);

int hash[210] = {0}, isclique = 1, isMaximal = 1;

for (int j = 0; j < k; j++) {

scanf("%d", &v[j]);

hash[v[j]] = 1;

}

for (int j = 0; j < k; j++) {

if (isclique == 0) break;

for (int l = j + 1; l < k; l++) {

if (e[v[j]][v[l]] == 0) {

isclique = 0;

printf("Not a Clique\n");

break;

}

if (isclique == 0) continue;

for (int j = 1; j <= nv; j++) {

if (hash[j] == 0) {

for (int l = 0; l < k; l++) {

if (e[v[l]][j] == 0) break;

if (l == k - 1) isMaximal = 0;

}

if (isMaximal == 0) {

printf("Not Maximal\n");

break;

}

if (isMaximal == 1) printf("Yes\n");

}

return 0;

}

PAT 1141. PAT Ranking of Institutions (25) – 甲级

After each PAT, the PAT Center will announce the ranking of institutions based on their students’ performances. Now you are asked to generate the ranklist.
Input Specification:
Each input file contains one test case. For each case, the first line gives a positive integer N (<=105), which is the number of testees. Then N lines follow, each gives the information of a testee in the following format:
ID Score School
where “ID” is a string of 6 characters with the first one representing the test level: “B” stands for the basic level, “A” the advanced level and “T” the top level; “Score” is an integer in [0, 100]; and “School” is the institution code which is a string of no more than 6 English letters (case insensitive). Note: it is guaranteed that “ID” is unique for each testee.
Output Specification:
For each case, first print in a line the total number of institutions. Then output the ranklist of institutions in nondecreasing order of their ranks in the following format:
Rank School TWS Ns
where “Rank” is the rank (start from 1) of the institution; “School” is the institution code (all in lower case); “TWS” is the total weighted score which is defined to be the integer part of “ScoreB/1.5 + ScoreA + ScoreT*1.5”, where “ScoreX” is the total score of the testees belong to this institution on level X; and “Ns” is the total number of testees who belong to this institution.
The institutions are ranked according to their TWS. If there is a tie, the institutions are supposed to have the same rank, and they shall be printed in ascending order of Ns. If there is still a tie, they shall be printed in alphabetical order of their codes.
Sample Input:
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
Sample Output:
5
1 cmu 192 2
1 au 192 3
3 pku 100 1
4 hypu 81 2
4 lanx 81 2

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

}