PAT – 第45页

L1-016. 查验身份证-PAT团体程序设计天梯赛GPLT

一个合法的身份证号码由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
分析：输入每个身份证号码的时候逐个判断是否满足条件，如果有满足条件的就flag = 1 最后如果flag依然是0就输出All passed~注意X和10的转换~

#include <iostream>
#include <string>
using namespace std;
bool func(string a);
int main() {
    int n;
    int count = 0;
    cin >> n;
    for (int i = 0; i < n; i++) {
        string a;
        cin >> a;
        if (func(a))
            count++;
    }
    if (count == 0)
        cout << "All passed";
    return 0;
}

bool func(string s) {
    int sum = 0;
    int a[18];
    for (int i = 0; i < 17; i++) {
        if(!isdigit(s[i])) {
            cout << s << endl;
            return false;
        }
        a[i] = s[i] - '0';
    }
    if (s[17] == 'X')
        a[17] = 10;
    else
        a[17] = s[17] - '0';
    int b[17] = {7, 9, 10, 5, 8, 4, 2, 1, 6, 3, 7, 9, 10, 5, 8, 4, 2};
    for (int i = 0; i < 17; i++) {
        sum = sum + a[i] * b[i];
    }
    sum = sum % 11;
    int c[11] = {1, 0, 10, 9, 8, 7, 6, 5, 4, 3, 2};
    if (c[sum] != a[17]) {
        for (int i = 0; i < 17; i++) {
            cout << s[i];
        }
        if (a[17] != 10)
            cout << a[17] << endl;
        else {
            cout << "X" << endl;
        }
        return true;
    }
    else {
        return false;
    }
}

#include <iostream>

#include <string>

using namespace std;

bool func(string a);

int main() {

int n;

int count = 0;

cin >> n;

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

string a;

cin >> a;

if (func(a))

count++;

}

if (count == 0)

cout << "All passed";

return 0;

}

bool func(string s) {

int sum = 0;

int a[18];

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

if(!isdigit(s[i])) {

cout << s << endl;

return false;

}

a[i] = s[i] - '0';

}

if (s[17] == 'X')

a[17] = 10;

else

a[17] = s[17] - '0';

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

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

sum = sum + a[i] * b[i];

}

sum = sum % 11;

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

if (c[sum] != a[17]) {

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

cout << s[i];

}

if (a[17] != 10)

cout << a[17] << endl;

else {

cout << "X" << endl;

}

return true;

}

else {

return false;

}

L1-011. A-B-PAT团体程序设计天梯赛(GPLT)

本题要求你计算A-B。不过麻烦的是，A和B都是字符串 —— 即从字符串A中把字符串B所包含的字符全删掉，剩下的字符组成的就是字符串A-B。
输入格式：
输入在2行中先后给出字符串A和B。两字符串的长度都不超过104，并且保证每个字符串都是由可见的ASCII码和空白字符组成，最后以换行符结束。
输出格式：
在一行中打印出A-B的结果字符串。
输入样例：
I love GPLT! It’s a fun game!
aeiou
输出样例：
I lv GPLT! It’s fn gm!
分析：辣么多ASCII码也在0~255之间，所以用book数组标记所有的ASCII码～如果第二个字符出现了这个ACSII码那就标记为1~然后输出的时候当book数组对应的那个ASCII为1的时候就跳过不输出～

#include <iostream>
using namespace std;
int book[256];
int main() {
    string s, a;
    getline(cin, s);
    getline(cin, a);
    for(int i = 0; i < a.length(); i++) book[a[i]] = 1;
    for(int i = 0; i < s.length(); i++) {
        if(book[s[i]] == 1) continue;
        cout << s[i];
    }
    return 0;
}

#include <iostream>

using namespace std;

int book[256];

int main() {

string s, a;

getline(cin, s);

getline(cin, a);

for(int i = 0; i < a.length(); i++) book[a[i]] = 1;

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

if(book[s[i]] == 1) continue;

cout << s[i];

}

return 0;

}

L1-010. 比较大小-PAT团体程序设计天梯赛

输入格式：
输入在一行中给出3个整数，其间以空格分隔。
输出格式：
在一行中将3个整数从小到大输出，其间以“->”相连。
输入样例：
4 2 8
输出样例：
2->4->8
分析：冒泡呀冒个泡~

#include <iostream>
using namespace std;
int main() {
    int a, b, c;
    cin >> a >> b >> c;
    if(b > c) swap(b, c);
    if(a > b) swap(a, b);
    if(b > c) swap(b, c);
    cout << a << "->" << b << "->" << c;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int a, b, c;

cin >> a >> b >> c;

if(b > c) swap(b, c);

if(a > b) swap(a, b);

if(b > c) swap(b, c);

cout << a << "->" << b << "->" << c;

return 0;

}

L1-006. 连续因子-PAT团体程序设计天梯赛

一个正整数N的因子中可能存在若干连续的数字。例如630可以分解为3*5*6*7，其中5、6、7就是3个连续的数字。给定任一正整数N，要求编写程序求出最长连续因子的个数，并输出最小的连续因子序列。
输入格式：
输入在一行中给出一个正整数N（1<N<231）。
输出格式：
首先在第1行输出最长连续因子的个数；然后在第2行中按“因子1*因子2*……*因子k”的格式输出最小的连续因子序列，其中因子按递增顺序输出，1不算在内。
输入样例：
630
输出样例：
3
5*6*7

[Update v2.0] 由github用户littlesevenmo提供的更高效的解法：
不用算连续因子最多不会超过12个，也不需要三重循环，两重循环即可，直接去计算当前部分乘积能不能整除N
分析：1、如果只有一个因子，那么这个数只能为1或者质数。因此我们主要去计算两个及以上因数的情况。
2、在有两个及以上的数连乘中，因数的最大上限为sqrt(N) + 1
3、因此思路就是，不断构造连乘，看连乘的积是否是N的因数，如果是，则看这部分连乘的数的个数是否比已记录的多。
4、用变量first记录连乘的第一个数字，这里我把它赋初值为0，如果在寻找N的因数过程中，first没有改变，那么就表明N是1或者是一个质数～

#include <iostream>
#include <cmath>
using namespace std;
long int num, temp;
int main(){
    cin >> num;
    int first = 0, len = 0, maxn = sqrt(num) + 1;
    for (int i = 2; i <= maxn; i++) {
        int j; 
        temp = 1;
        for (j = i; j <= maxn; j++) {
            temp *= j;
            if (num % temp != 0) break;
        }
        if (j - i > len) {
            len = j - i;
            first = i;
        }
    }
    if (first == 0) {
        cout << 1 << endl << num;
    } else {
        cout << len << endl;
        for (int i = 0; i < len; i++) {
            cout << first + i;
            if (i != len - 1) cout << '*';
        }
    }
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

long int num, temp;

int main(){

cin >> num;

int first = 0, len = 0, maxn = sqrt(num) + 1;

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

int j;

temp = 1;

for (j = i; j <= maxn; j++) {

temp *= j;

if (num % temp != 0) break;

}

if (j - i > len) {

len = j - i;

first = i;

}

if (first == 0) {

cout << 1 << endl << num;

} else {

cout << len << endl;

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

cout << first + i;

if (i != len - 1) cout << '*';

}

return 0;

}

1011. A+B和C (15)-PAT乙级真题

题目描述：

给定区间[-2^31, 2^31]内的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

分析：使用long long int存储a、b和c，当a + b > c的时候输出true，否则输出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;
}

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

}

1055. 集体照 (25)-PAT乙级真题

拍集体照时队形很重要，这里对给定的N个人K排的队形设计排队规则如下：
每排人数为N/K（向下取整），多出来的人全部站在最后一排；
后排所有人的个子都不比前排任何人矮；
每排中最高者站中间（中间位置为m/2+1，其中m为该排人数，除法向下取整）；
每排其他人以中间人为轴，按身高非增序，先右后左交替入队站在中间人的两侧（例如5人身高为190、188、186、175、170，则队形为175、188、190、186、170。这里假设你面对拍照者，所以你的左边是中间人的右边）；
若多人身高相同，则按名字的字典序升序排列。这里保证无重名。
现给定一组拍照人，请编写程序输出他们的队形。
输入格式：
每个输入包含1个测试用例。每个测试用例第1行给出两个正整数N（<=10000，总人数）和K（<=10，总排数）。随后N行，每行给出一个人的名字（不包含空格、长度不超过8个英文字母）和身高（[30, 300]区间内的整数）。
输出格式：
输出拍照的队形。即K排人名，其间以空格分隔，行末不得有多余空格。注意：假设你面对拍照者，后排的人输出在上方，前排输出在下方。
输入样例：
10 3
Tom 188
Mike 170
Eva 168
Tim 160
Joe 190
Ann 168
Bob 175
Nick 186
Amy 160
John 159
输出样例：
Bob Tom Joe Nick
Ann Mike Eva
Tim Amy John

分析：建立结构体node，里面包含string类型的姓名name和int类型的身高height～将学生的信息输入到node类型的vector数组stu中～然后对stu数组进行排序（cmp函数表示排序规则，如果身高不等，就按照身高从大到小排列；如果身高相等，就按照名字从小到大的字典序排列～）然后用while循环排列每一行，将每一行应该排列的结果的姓名保存在ans数组中～

因为是面对拍照者，后排的人输出在上方，前排输出在下方，每排人数为N/K（向下取整），多出来的人全部站在最后一排，所以第一排输出的应该是包含多出来的人，所以while循环体中，当row == k时，表示当前是在排列第一行，那么这一行的人数m应该等于总人数n减去后面的k列*(k-1)行，即m = n – n / k * (k-1)；如果不是第一行，那么m直接等于n / k；最中间一个学生应该排在m/2的下标位置，即ans[m / 2] = stu[t].name；然后排左边一列，ans数组的下标 j 从m/2-1开始，一直往左j–，而对于stu的下标 i，是从t+1开始，每次隔一个人选取（即i = i+2，因为另一些人的名字是给右边的），每次把stu[i]的name赋值给ans[j–]；排右边的队伍同理，ans数组的下标 j 从m/2 + 1开始，一直往右j++，stu的下标 i，从t+2开始，每次隔一个人选取（i = i+2），每次把stu[i]的name赋值给ans[j++]，然后输出当前已经排好的ans数组～每一次排完一列row-1，直到row等于0时退出循环表示已经排列并输出所有的行～

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct node {
    string name;
    int height;
};
int cmp(struct node a, struct node b) {
    return a.height != b.height ? a.height > b.height : a.name < b.name;
}
int main() {
    int n, k, m;
    cin >> n >> k;
    vector<node> stu(n);
    for(int i = 0; i < n; i++) {
        cin >> stu[i].name >> stu[i].height;
    }
    sort(stu.begin(), stu.end(), cmp);
    int t = 0, row = k;
    while(row) {
        if(row == k)
            m = n - n / k * (k - 1);
        else
            m = n / k;
        vector<string> ans(m);
        ans[m / 2] = stu[t].name;
        // 左边一列
        int j = m / 2 - 1;
        for(int i = t + 1; i < t + m; i = i + 2)
            ans[j--] = stu[i].name;
        // 右边一列
        j = m / 2 + 1;
        for(int i = t + 2; i < t + m; i = i + 2)
            ans[j++] = stu[i].name;
        // 输出当前排
        cout << ans[0];
        for(int i = 1; i < m; i++)
            cout << " " << ans[i];
        cout << endl;
        t = t + m;
        row--;
    }
    return 0;
}

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

struct node {

string name;

int height;

};

int cmp(struct node a, struct node b) {

return a.height != b.height ? a.height > b.height : a.name < b.name;

}

int main() {

int n, k, m;

cin >> n >> k;

vector<node> stu(n);

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

cin >> stu[i].name >> stu[i].height;

}

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

int t = 0, row = k;

while(row) {

if(row == k)

m = n - n / k * (k - 1);

else

m = n / k;

vector<string> ans(m);

ans[m / 2] = stu[t].name;

// 左边一列

int j = m / 2 - 1;

for(int i = t + 1; i < t + m; i = i + 2)

ans[j--] = stu[i].name;

// 右边一列

j = m / 2 + 1;

for(int i = t + 2; i < t + m; i = i + 2)

ans[j++] = stu[i].name;

// 输出当前排

cout << ans[0];

for(int i = 1; i < m; i++)

cout << " " << ans[i];

cout << endl;

t = t + m;

row--;

}

return 0;

}