PAT 甲级 - 入门模拟
Aidan Engineer
 2021-08-08 15:44:06      12.7k 字  65 分钟

当时准备 PAT 竞赛时候，买了本《算法笔记》，书中将题型进行分类，是我最系统的一次算法学习，对题型判断、解题思路都有了新的认知，本篇文章主要记录当时刷的入门模拟题，算是比较简单的算法题（有些都不能称之为算法），就当是打基础了

包括分类：简单模拟 、 查找元素 、 图形输出 、 日期处理 、 进制转换 、 字符串处理

简单模拟

思想解释

根据题目的要求去做即可，主要考察代码的编写能力

类型练习

1042

题目：Shuffling Machine

Shuffling is a procedure used to randomize a deck of playing cards. Because standard shuffling techniques are seen as weak, and in order to avoid “inside jobs” where employees collaborate with gamblers by performing inadequate shuffles, many casinos employ automatic shuffling machines. Your task is to simulate a shuffling machine.

The machine shuffles a deck of 54 cards according to a given random order and repeats for a given number of times. It is assumed that the initial status of a card deck is in the following order:

S1, S2, …, S13, H1, H2, …, H13, C1, C2, …, C13, D1, D2, …, D13, J1, J2

where “S” stands for “Spade”, “H” for “Heart”, “C” for “Club”, “D” for “Diamond”, and “J” for “Joker”. A given order is a permutation of distinct integers in [1, 54]. If the number at the i-th position is j, it means to move the card from position i to position j. For example, suppose we only have 5 cards: S3, H5, C1, D13 and J2. Given a shuffling order {4, 2, 5, 3, 1}, the result will be: J2, H5, D13, S3, C1. If we are to repeat the shuffling again, the result will be: C1, H5, S3, J2, D13.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer K (<= 20) which is the number of repeat times. Then the next line contains the given order. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print the shuffling results in one line. All the cards are separated by a space, and there must be no extra space at the end of the line.

Sample Input:

2
36 52 37 38 3 39 40 53 54 41 11 12 13 42 43 44 2 4 23 24 25 26 27 6 7 8 48 49 50 51 9 10 14 15 16 5 17 18 19 1 20 21 22 28 29 30 31 32 33 34 35 45 46 47

Sample Output:

S7 C11 C10 C12 S1 H7 H8 H9 D8 D9 S11 S12 S13 D10 D11 D12 S3 S4 S6 S10 H1 H2 C13 D2 D3 D4 H6 H3 D13 J1 J2 C1 C2 C3 C4 D1 S5 H5 H11 H12 C6 C7 C8 C9 S2 S8 S9 H10 D5 D6 D7 H4 H13 C5

思路： 用字符串不如使用整型数组直接进行循环调换，根据其编号输出对应的花色

  • 建立三个整型数组，分别用来存储初始顺序、洗牌后的顺序、洗牌规则

  • 每次洗牌就是将规则数组中的当前数字作为下标用来控制洗牌后的数组被赋值洗牌前的编号

  • 最后花色和数值的输出需要对编号进行 -1，这样是为了防止 13、26…这样的边界数字越界的情况，但输出数值时需要再 +1

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <cstdio>

int main()
{

    int times;
    scanf("%d", &times); // 输入洗牌几次
    int start[55], end[55], order[55];
    for (int i = 1; i < 55; i++)
    {
        scanf("%d", &order[i]); // 输入洗牌规则
        start[i] = i;           // 初始化默认排序
    }
    for (int i = 0; i < times; i++)
    {
        for (int j = 1; j < 55; j++)
        {
            end[order[j]] = start[j]; // 根据规则洗牌
        }
        for (int k = 1; k < 55; k++)
        {
            start[k] = end[k]; // 将每次洗完的牌放到初始数组，为下一次洗牌做准备
        }
    }
    char color[5] = {'S', 'H', 'C', 'D', 'J'}; // 字符花色数组
    for (int i = 1; i < 55; i++)
    {
        end[i]--;
        // 每次的序号都要自减，防止 13、26…这样的数字除和摸出 13 时得到的值不符合逻辑
        printf("%c%d", color[end[i] / 13], end[i] % 13 + 1);
        if (i != 54)
        { // 避免额外空格
            printf(" ");
        }
    }
    return 0;

}

1046

题目：Shortest Distance

The task is really simple: given N exits on a highway which forms a simple cycle, you are supposed to tell the shortest distance between any pair of exits.

Input Specification:

Each input file contains one test case. For each case, the first line contains an integer N (in [3,10510^5]), followed by N integer distances D1 D2 ⋯ DN, where Di is the distance between the i-th and the (i+1)-st exits, and DN is between the N-th and the 1st exits. All the numbers in a line are separated by a space. The second line gives a positive integer M (≤10410^4), with M lines follow, each contains a pair of exit numbers, provided that the exits are numbered from 1 to N. It is guaranteed that the total round trip distance is no more than 10710^7.

Output Specification:

For each test case, print your results in M lines, each contains the shortest distance between the corresponding given pair of exits.

Sample Input:

5 1 2 4 14 9
3
1 3
2 5
4 1

Sample Output:

3
10
7

思路： 实际上只有一条循环线路，只要求出单个方向（如顺时针）的值，用距离总和减去后获得反向距离，返回二者最小值

  • 创建一个距离数组 distance[]，其中distance[i] 中保存的是从 V1 点到 Vi+1 的距离，在输入时就将数组和距离总和记录下来减少复杂度

  • 输入的起点 begin 和终点 end 之间的顺时针距离 dis_left 为 dis_left=distance[end-1]-distance[begin-1]，需要判断 begin 与 end 的大小关系，始终保持小的在前

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int n;
    scanf("%d", &n);
    vector<int> dis(n + 1); // 动态数组分配空间后所有的值为 0
    int sum = 0, left, right;
    for (int i = 1; i <= n; i++)
    {
        int temp;
        scanf("%d", &temp);
        sum += temp;
        dis[i] = sum; // 距离数组保存的是 V1 到 Vi 的顺时针距离
    }
    int cnt;
    scanf("%d", &cnt); // 输入判断几对
    for (int i = 0; i < cnt; i++)
    {
        scanf("%d %d", &left, &right);
        if (left > right) // 始终保持顺时针判断
            swap(left, right);
        int temp = dis[right - 1] - dis[left - 1];
        printf("%d\n", min(temp, sum - temp));
    }
    system("pause");
    return 0;
}

1065

题目：A+B and C (64bit)

Given three integers A, B and C in [−2632^{63}, 2632^{63})，you are supposed to tell whether A+B>C.

Input Specification:

The first line of the input gives the positive number of test cases, T (≤10). Then T test cases follow, each consists of a single line containing three integers A, B and C, separated by single spaces.

Output Specification:

For each test case, output in one line Case #X: true if A+B>C, or Case #X: false otherwise, where X is the case number (starting from 1).

Sample Input:

3
1 2 3
2 3 4
9223372036854775807 -9223372036854775808 0

Sample Output:

Case #1: false
Case #2: true
Case #3: false

思路： 数据类型过大用 long long 型进行存储，同时需要考虑溢出的情况（同为正值溢出必大于，同为负值溢出必小于）

  • 因为 A、B 的大小为 [-2^63, 2^63），用 long long 存储 A 和 B 的值，以及他们相加的值 sum

  • 如果 A > 0, B < 0 或者 A < 0, B > 0，sum 是不可能溢出的

  • 如果 A > 0, B > 0，sum 可能会溢出，sum 范围理应为 (0, 2^64 – 2]，溢出得到的结果应该是 [-2^63, -2] 是个负数，所以 sum < 0 时候说明溢出了

  • 如果 A < 0, B < 0，sum 可能会溢出，同理，sum 溢出后结果是大于 0 的，所以 sum > 0 说明溢出了

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <cstdio>
#include <cstdlib>

int main()
{

    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        long long a, b, c;
        scanf("%lld %lld %lld", &a, &b, &c);
        long long sum = a + b;
        if (a > 0 && b > 0 && sum < 0)
        { // 正溢出，结果必定大于 C
            printf("Case #%d: true\n", i + 1);
        }
        else if (a < 0 && b < 0 && sum >= 0)
        { // 负溢出，两个负数相加而且溢出，必小于 C
            printf("Case #%d: false\n", i + 1);
        }
        else if (sum > c) // 无溢出，正常比较
        {
            printf("Case #%d: true\n", i + 1);
        }
        else
        {
            printf("Case #%d: false\n", i + 1);
        }
    }
    system("pause");
    return 0;

}

1002

题目：A+B for Polynomials

This time, you are supposed to find A+B where A and B are two polynomials.

Input Specification:

Each input file contains one test case. Each case occupies 2 lines, and each line contains the information of a polynomial:

K N1 aN1 N2 aN2 … NK aNK

where K is the number of nonzero terms in the polynomial, Ni and aNi (i=1,2,⋯,K) are the exponents and coefficients, respectively. It is given that 1≤K≤10，0≤NK<⋯< N2<N1≤1000.

Output Specification:

For each test case you should output the sum of A and B in one line, with the same format as the input. Notice that there must be NO extra space at the end of each line. Please be accurate to 1 decimal place.

Sample Input:

2 1 2.4 0 3.2
2 2 1.5 1 0.5

Sample Output:

3 2 1.5 1 2.9 0 3.2

思路： 使用浮点数组用指数作为下标，存储系数的值，只要指数相同就为同一项，系数直接相加即可

  • 数组长度为指数的最大值 1000，poly[i] = j表示指数 i 的系数为 j，接收 exponent 和 coefficient 输入的同时将对应指数的系数加入到 poly 数组中，所有非零系数的个数，然后从前往后输出所有系数不为 0 的指数和系数

  • 注意输出格式和输出的精度

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <cstdio>
#include <vector>
#include <cstdlib>
using namespace std;

int main()
{
    vector<double> coef(1001, 0); // 根据数据规模，创建浮点数组存储系数
    int cnt = 0;                  // 判断最后有多少项
    int m, n;                     // 获取每行有多少项
    scanf("%d", &m);
    for (int j = 0; j < m; j++)
    {
        int e_temp;
        double c_temp;
        scanf("%d %lf", &e_temp, &c_temp); // 根据项数输入指数和系数
        coef[e_temp] += c_temp;            // 用指数作为下标将系数相加
    }
    scanf("%d", &n);
    for (int j = 0; j < n; j++)
    {
        int e_temp;
        double c_temp;
        scanf("%d %lf", &e_temp, &c_temp);
        coef[e_temp] += c_temp;
    }
    for (int i = 0; i < coef.size(); i++)
    {
        if (coef[i])
        { // 记录所有不为 0 的项
            cnt++;
        }
    }
    printf("%d", cnt);
    for (int i = 1000; i >= 0; i--)
    {
        if (coef[i])
        { // 不为 0 便输出指数和系数，注意空格和小数点为 1 位
            printf(" %d %.1f", i, coef[i]);
        }
    }
    system("pause");
    return 0;
}

1009

题目：Product of Polynomials

This time, you are supposed to find A×B where A and B are two polynomials.

Input Specification:

Each input file contains one test case. Each case occupies 2 lines, and each line contains the information of a polynomial:

K N1 aN1 N2 aN2 … NK aNK

where K is the number of nonzero terms in the polynomial, Ni and aNi (i=1, 2, ⋯, K) are the exponents and coefficients, respectively. It is given that 1≤K≤10, 0≤NK<⋯<N2<N1≤1000.

Output Specification:

For each test case you should output the product of A and B in one line, with the same format as the input. Notice that there must be NO extra space at the end of each line. Please be accurate up to 1 decimal place.

Sample Input:

2 1 2.4 0 3.2
2 2 1.5 1 0.5

Sample Output:

3 3 3.6 2 6.0 1 1.6

思路： 建立两个数组，一个保存第一行的多项式，一个在第二行读入时，直接循环第一个数组的内容进行处理存储

  • 因为是乘法，根据最大指数为 1000，那么乘积的最大指数就是 2000，所以 ans 数组的数据规模为 2001

  • 无需将两个多项式分别保存完再处理，在输入第二个多项式时直接循环与第一个多项式的每一项相乘即可（只算非零）

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <cstdio>
#include <vector>
#include <cstdlib>
using namespace std; 

int main()
{

    vector<double> coef(1001, 0);
    vector<double> ans(2001, 0); // 根据指数最大为 1000，相乘后最大的指数为 1000+1000
    int cnt = 0;
    int m, n;
    scanf("%d", &m);
    for (int j = 0; j < m; j++)
    {
        int e_temp;
        double c_temp;
        scanf("%d %lf", &e_temp, &c_temp);
        coef[e_temp] += c_temp;
    }
    scanf("%d", &n);
    for (int j = 0; j < n; j++)
    {
        int e_temp;
        double c_temp;
        scanf("%d %lf", &e_temp, &c_temp);
        for (int i = 0; i < coef.size(); i++)
        { // 在第二行每输入一项，就与第一行的每项相乘，得到的值根据相同指数加到 ans 数组中
            if (coef[i])
            {
                ans[i + e_temp] += coef[i] * c_temp;
            }
        }
    }
    for (int i = 0; i < ans.size(); i++)
    {
        if (ans[i])
        {
            cnt++;
        }
    }
    printf("%d", cnt);
    for (int i = 2000; i >= 0; i--)
    {
        if (ans[i])
        {
            printf(" %d %.1f", i, ans[i]);
        }
    }
    system("pause");
    return 0;

}

查找元素

思想解释

在一组给定的元素中查找目标元素，范围较小可直接遍历查找，或者使用某些数据类型自带的 find() 函数，查找最大最小值可以使用 [algorithm] 下的 max_elemen() 函数等

二分查找

有些元素的数据范围较大，采用遍历消耗的时间难免过多，所以采用二分查找的方式能够用较小的时间复杂度来完成

具体思路就是每次确定中值mid=(left+right)/2，用要查询的数 x 与 mid 进行比较，根据大小关系再与另一半进行比较，值得注意的是，有些数据范围实在是太大导致 left+right 的值就已经超过的 int 支持的数据范围，这时可以使用mid=left+(right-left)/2
在 [algorithm] 下的模板函数为：binary_search(first,last,val)

类型练习

1011

题目：World Cup Betting

With the 2010 FIFA World Cup running, football fans the world over were becoming increasingly excited as the best players from the best teams doing battles for the World Cup trophy in South Africa. Similarly, football betting fans were putting their money where their mouths were, by laying all manner of World Cup bets.

Chinese Football Lottery provided a “Triple Winning” game. The rule of winning was simple: first select any three of the games. Then for each selected game, bet on one of the three possible results – namely W for win, T for tie, and L for lose. There was an odd assigned to each result. The winner’s odd would be the product of the three odds times 65%.

For example, 3 games’ odds are given as the following:

W T L
1.1 2.5 1.7
1.2 3.1 1.6
4.1 1.2 1.1

To obtain the maximum profit, one must buy W for the 3rd game, T for the 2nd game, and T for the 1st game. If each bet takes 2 yuans, then the maximum profit would be (4.1×3.1×2.5×65%−1)×2=39.31 yuans (accurate up to 2 decimal places).

Input Specification:

Each input file contains one test case. Each case contains the betting information of 3 games. Each game occupies a line with three distinct odds corresponding to W, T and L.

Output Specification:

For each test case, print in one line the best bet of each game, and the maximum profit accurate up to 2 decimal places. The characters and the number must be separated by one space.

Sample Input:

1.1 2.5 1.7
1.2 3.1 1.6
4.1 1.2 1.1

Sample Output:

T T W 39.31

思路： 每次输入时就与前一个值比较只获取最大值，利用输入时的顺序为下标输出字符，最好将每次最大值相乘，按公式输出

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <cstdio>
#include <cstdlib>

int main()
{
    char c[4] = {"WTL"}; // 还应存储一个 '\0' 表示结束
    double ans = 0.65;   // 答案初始为 0.65，无需输出时计算
    for (int i = 0; i < 3; i++)
    {
        double maxvalue = 0.0;
        int maxchar = 0;
        for (int j = 0; j < 3; j++)
        {
            double temp;
            scanf("%lf", &temp);
            if (maxvalue <= temp)
            {
                maxvalue = temp;
                maxchar = j;
            }
        }
        ans *= maxvalue;
        printf("%c ", c[maxchar]); // 输出符号
    }
    printf("%.2f", (ans - 1) * 2);
    system("pause");
    return 0;
}

1006

题目：Sign In and Sign Out

At the beginning of every day, the first person who signs in the computer room will unlock the door, and the last one who signs out will lock the door. Given the records of signing in’s and out’s, you are supposed to find the ones who have unlocked and locked the door on that day.

Input Specification:

Each input file contains one test case. Each case contains the records for one day. The case starts with a positive integer M, which is the total number of records, followed by M lines, each in the format:
ID_number Sign_in_time Sign_out_time

where times are given in the format HH: MM: SS , and ID_number is a string with no more than 15 characters.

Output Specification:

For each test case, output in one line the ID numbers of the persons who have unlocked and locked the door on that day. The two ID numbers must be separated by one space.

Note: It is guaranteed that the records are consistent. That is, the sign in time must be earlier than the sign out time for each person, and there are no two persons sign in or out at the same moment.

Sample Input:

3

CS301111 15:30:28 17:00:10
SC3021234 08:00:00 11:25:25
CS301133 21:45:00 21:58:40

Sample Output:

SC3021234 CS301133

思路： 将时间用 scanf() 读入转换为秒，最小的时间为开门人保存其 string 的 ID，最大为锁门人，因为是 string 型，用 iostream

  • 无需建立数组，最后只输出 ID，使用一个 string 型保存，其他用临时变量处理即可

  • 输入中的冒号符号和空格用 scanf 处理

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <climits>
using namespace std; 

int main()
{

    int n, max = INT_MIN, min = INT_MAX;
    string unlock, lock;
    scanf("%d", &n);            // 读入人数
    for (int i = 0; i < n; i++) // 建立人数循环
    {
        string Id;
        cin >> Id; // 输入每个人的 ID
        int h1, m1, s1, h2, m2, s2;
        scanf("%d:%d:%d %d:%d:%d", &h1, &m1, &s1, &h2, &m2, &s2);
        int in_temp = h1 * 3600 + m1 * 60 + s1; // 将所有的时间转换成秒
        int out_temp = h2 * 3600 + m2 * 60 + s2;
        if (min > in_temp) // 最小的时间就是开锁人
        {
            min = in_temp;
            unlock = Id; // 保存 ID
        }
        if (max < out_temp) // 最大的时间就是锁门人
        {
            max = out_temp;
            lock = Id; // 保存 ID
        }
    }
    cout << unlock << " " << lock;
    system("pause");
    return 0;

}

1036

题目：Boys vs Girls

This time you are asked to tell the difference between the lowest grade of all the male students and the highest grade of all the female students.

Input Specification:

Each input file contains one test case. Each case contains a positive integer N, followed by N lines of student information. Each line contains a student’s name, gender, ID and grade, separated by a space, where name and ID are strings of no more than 10 characters with no space, gender is either F (female) or M (male), and grade is an integer between 0 and 100. It is guaranteed that all the grades are distinct.

Output Specification:

For each test case, output in 3 lines. The first line gives the name and ID of the female student with the highest grade, and the second line gives that of the male student with the lowest grade. The third line gives the difference gradeF−gradeM. If one such kind of student is missing, output Absent in the corresponding line, and output NA in the third line instead.

Sample Input 1:

3
Joe M Math990112 89
Mike M CS991301 100
Mary F EE990830 95

Sample Output 1:

Mary EE990830
Joe Math990112
6

Sample Input 2:

1
Jean M AA980920 60

Sample Output 2:

Absent
Jean AA980920
NA

思路： 用 string 类型的 M 和 F 保存要求的学生的信息，F_max 和 M_min 处保存男生的最低分和女生的最高分

  • 输出姓名和编号时用一个字符串进行拼接即可

  • 如果成绩还为赋予的初始值说名没有符合条件的人，按条件进行更改输出

  • 最后输出的差要男女生的成绩同时被更改，判断大小关系（也可用绝对值输出）后输出

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
using namespace std;

int main()
{
    int n, M_min = 101, F_max = -1; // 设置人数变量，同时根据范围确定最大最小值
    string M, F;                    // 男女生输出的姓名和编号可以用一个字符串搞定
    cin >> n;
    for (int i = 0; i < n; i++) // 根据人数构建循环处理每行数据
    {
        string name_temp, Id_temp; // 临时字符串保存姓名和编号
        char gender;
        int grade;
        cin >> name_temp >> gender >> Id_temp >> grade;
        if (gender == 'M' && grade < M_min) // 男生且成绩小于男生成绩的最小值
        {
            M_min = grade;                 // 成绩覆盖
            M = name_temp + " " + Id_temp; // 保存姓名和编号
        }
        if (gender == 'F' && grade > F_max) // 女生且成绩大于女生成绩的最大值
        {
            F_max = grade;
            F = name_temp + " " + Id_temp;
        }
    }
    if (F_max != -1) // 如果成绩被改动说明有符合条件的人可以输出
    {
        cout << F << endl;
    }
    else
    {
        cout << "Absent\n";
    }
    if (M_min != 101)
    {
        cout << M << endl;
    }
    else
    {
        cout << "Absent\n";
    }
    if (M_min != 101 && F_max != -1) // 如果男女生的成绩都有符合条件的人
    {
        cout << abs(M_min - F_max); // 用绝对值输出，防止大小颠倒
    }
    else
    {
        cout << "NA";
    }
    system("pause");
    return 0;
}

图形输出

思想解释

根据题目给出的规则输出图形，主要考察的是对规则的总结，主要的实现手段有两种

  1. 根据规律直接进行输出

  2. 根据规律对二维数组进行填充，然后直接输出整个二维数组，如杨辉三角形，注意不论形状为何，统一用行列的方式填入，用空格控制输出

类型练习

1031

题目：Hello World for U

Given any string of N (≥5) characters, you are asked to form the characters into the shape of U . For example, helloworld can be printed as:

h d
e l
l r
lowo

That is, the characters must be printed in the original order, starting top-down from the left vertical line with n1 characters, then left to right along the bottom line with n2 characters, and finally bottom-up along the vertical line with n3 characters. And more, we would like U to be as squared as possible – that is, it must be satisfied that:

n1=n3=maxk∣k≤n2forall3≤n2≤Nwithn1+n2+n3−2=Nn1=n3=max {k | k≤n2 for all 3≤n2≤N} with n1+n2+n3−2=N

Input Specification:

Each input file contains one test case. Each case contains one string with no less than 5 and no more than 80 characters in a line. The string contains no white space.

Output Specification:

For each test case, print the input string in the shape of U as specified in the description.

Sample Input:

helloworld!

Sample Output:

h !
e d
l l
lowor

思路： 确定长和宽的值，根据规则直接输出或者填充到数组输出

  • 主要要求为：n1 == n3；n2 >= n1；n1 为在满足上述条件的情况下的最大值
  • 根据条件 n=length+2 得出 n1 = n / 3，n2 = n / 3 + n % 3
  • 注意：字符数组的输入不要用 gets() 函数，可能造成编译无法通过的情况

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <cstdio>
#include <cstring>
#include <cstdlib>

int main()
{

    // 数组型
    char str[81], map[30][30];     // 创建一个二维数组
    memset(map, ' ', sizeof(map)); // 全部初始化为空格
    scanf("%s", str);
    int length = strlen(str) + 2;
    int row = length / 3;
    int column = length - 2 * row;
    for (int i = 0; i < row - 1; i++)
    {
        map[i][0] = str[i];
        map[i][column - 1] = str[length - 3 - i];
    }
    for (int i = 0; i < column; i++)
    {
        map[row - 1][i] = str[row - 1 + i];
    } // 对二维数组填充
    for (int i = 0; i < row; i++)
    {
        for (int j = 0; j < column; j++)
        {
            printf("%c", map[i][j]);
        }
        if (i != row - 1)
        {
            printf("\n");
        }
    }
    printf("\n");
    // 直接输出型
    int n = strlen(str);
    int n1 = (n + 2) / 3, n3 = n1, n2 = (n + 2) - 2 * n1; // 确定 n1,n2,n3 的长度，n1 和 n3 一个就够
    for (int i = 0; i < n1 - 1; i++)
    { // 输出没有底层的所有
        printf("%c", str[i]);
        for (int j = 0; j < n2 - 2; j++)
        {
            printf(" ");
        }
        printf("%c\n", str[n - 1 - i]);
    }
    for (int i = 0; i < n2; i++)
    { // 输出底层
        printf("%c", str[n1 - 1 + i]);
    }
    system("pause");
    return 0;

}

1164

题目：Good in C

When your interviewer asks you to write “Hello World” using C, can you do as the following figure shows?

Input Specification:

Each input file contains one test case. For each case, the first part gives the 26 capital English letters A-Z, each in a 7×5 matrix of C’s and .'s. Then a sentence is given in a line, ended by a return. The sentence is formed by several words (no more than 10 continuous capital English letters each), and the words are separated by any characters other than capital English letters.

It is guaranteed that there is at least one word given.

Output Specification:

For each word, print the matrix form of each of its letters in a line, and the letters must be separated by exactly one column of space. There must be no extra space at the beginning or the end of the word.

Between two adjacent words, there must be a single empty line to separate them. There must be no extra line at the beginning or the end of the output.

Sample Input:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
..C..
.C.C.
C...C
CCCCC
C...C
CCCC.
C...C
CCCC.
C...C
CCCC.
.CCC.
C...C
C....
C...C
.CCC.
CCCC.
C...C
CCCC.
CCCCC
C....
CCCC.
C....
CCCCC
C....
CCCC.
C....
CCCC.
C...C
C....
C.CCC
C...C
CCCC.
C...C
CCCCC
C...C
CCCCC
..C..
CCCCC
....C
C...C
.CCC.
C...C
C..C.
C.C..
CC...
C.C..
C..C.
C...C
C....
CCCCC
C...C
CC.CC
C.C.C
C...C
CC..C
C.C.C
C..CC
C...C
.CCC.
C...C
.CCC.
CCCC.
C...C
CCCC.
C....
.CCC.
C...C
C.C.C
C..CC
.CCC.
CCCC.
C...C
CCCC.
CC...
C.C..
C..C.
C...C
.CCC.
C...C
C....
.CCC.
....C
C...C
.CCC.
CCCCC
..C..
C...C
.CCC.
C...C
.C.C.
..C..
C...C
C.C.C
CC.CC
C...C
.C.C.
..C..
.C.C.
C...C
.C.C.
..C..
CCCCC
....C
...C.
..C..
.C...
C....
CCCCC
HELLO~WORLD!

Sample Output:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
C... C CCCCC C.... C.... . CCC.
C... C C.... C.... C.... C... C
CCCCC CCCC. C.... C.... C... C
C... C C.... C.... C.... C... C
C... C CCCCC CCCCC CCCCC . CCC.

C... C . CCC. CCCC. C.... CCCC.
C... C C... C C... C C.... C... C
C... C C... C CCCC. C.... C... C
C. C. C C... C CC... C.... C... C
CC. CC C... C C. C.. C.... C... C
C... C C... C C.. C. C.... C... C
C... C . CCC. C... C CCCCC CCCC.

思路： 使用二维的字符串数组保存每个字母的七行，对目标单词不是大写字母的作为分割，将每一个单词的字母获取它的字母序号放入数组，对每个单词遍历输出每一行，使用标记记录是否有一个单词被输出，用来输出空行

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
#include <cctype>
#include <vector>
using namespace std;

string let[26][7], str; // 保存图形样式，保存目标字符串
vector<int> word;       // 保存每个符合条件的单词

int main()
{
    for (int i = 0; i < 26; i++)
    {
        for (int j = 0; j < 7; j++)
        {
            cin >> let[i][j];
        }
    }
    cin.ignore(); // 目标字符串要获取整行，忽略上一个换行
    getline(cin, str);
    bool flag = false; // 标记是否有单词被输出
    for (int i = 0; i < str.length(); i++)
    {
        if (isupper(str[i]) && i == str.size() - 1) // 存在最后一个的情况
        {
            word.push_back(str[i] - 'A');
        }

        if (isupper(str[i]) && i != str.size() - 1) // 用非大写字母或者结尾进行一次输出
        {
            word.push_back(str[i] - 'A');
        }
        else
        {
            if (flag) // 判断之前是否有单词被输出
            {
                cout << endl
                     << endl;
                flag = false;
            }

            for (int j = 0; j < 7; j++) // 每个单词输出 7 行
            {
                for (int k = 0; k < word.size(); k++) // 输出每个单词的每一行
                {
                    if (k != 0) // 空格相隔
                    {
                        cout << " ";
                    }
                    cout << let[word[k]][j];
                }
                if (j != 6) // 换行
                {
                    cout << endl;
                }
            }
            word.clear(); // 清空保存数组进行下一次输出
            flag = true;
        }
    }

    system("pause");
    return 0;
}

日期处理

思想解释

主要解决的是平年和闰年造成的二月日期差异，还有大小月的不同，PAT 暂没有这样的试题

类型练习

求日期差值：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
/*
题目：以 6 位格式输入两个日期，求两个日期之间的天数，包括这两个日期（如果两个日期相邻那么就是两天）
思路：书上是用循环模拟的方法写的，复杂度太高 
 先求出每个日期离开年过了多少天，如果年份相同，互减 +1 即可 
 年份不同，算出隔了多少年，在判断每年是闰年还是平年，得到相应的天数，最后减去较早年份已经过去的日子 +1
*/
#include <iostream>
using namespace std; 

bool judgeYear(int year)
{ // 判断是否闰年

    return year % 400 == 0 || (year % 4 == 0 && year % 100 != 0);

}
int countDate(int year, int month, int day)
{ // 计算每个日期离开年过去的天数

    int sum = 0;
    switch (month)
    {
    case 1:
        sum = 0;
        break;
    case 2:
        sum = 31;
        break;
    case 3:
        sum = 59;
        break;
    case 4:
        sum = 90;
        break;
    case 5:
        sum = 120;
        break;
    case 6:
        sum = 151;
        break;
    case 7:
        sum = 181;
        break;
    case 8:
        sum = 212;
        break;
    case 9:
        sum = 243;
        break;
    case 10:
        sum = 273;
        break;
    case 11:
        sum = 304;
        break;
    case 12:
        sum = 334;
        break;
    }
    sum += day;
    if (judgeYear(year) && month > 2)
    {
        sum++;
    }
    return sum;

}
int main()
{

    int date1, date2; 
    cin >> date1 >> date2; 
    int year1, month1, day1; 
    int year2, month2, day2; 
    if (date1 > date2)
    { // 始终让较早的日期在前
        int t = date1; 
        date1 = date2; 
        date2 = t; 
    }
    year1 = date1 / 10000; 
    month1 = date1 % 10000 / 100; 
    day1 = date1 % 100; 
    year2 = date2 / 10000; 
    month2 = date2 % 10000 / 100; 
    day2 = date2 % 100; 
    // 获取每个日期的实际年月日
    int difDay; // 记录相差天数
    if (year1 == year2)
    { // 年份相同的情况
        difDay = countDate(year2, month2, day2) - countDate(year1, month1, day1) + 1; 
    }
    else
    { // 年份不同
        difDay = countDate(year2, month2, day2); 
        int difYear = year2 - year1; 
        while (difYear)
        { // 判断每一年的天数
            judgeYear(year2 - difYear) ? difDay += 366 : difDay += 365; 
            difYear--; 
        }
        difDay -= countDate(year1, month1, day1) - 1; // 减去开始年份已经过去（在循环中也加上了）
    }
    cout << difDay << endl; 
    system("pause");
    return 0;

}

进制转换

思想解释

主要是不同进制的输入输出，熟练使用 strtol() 函数和 _itoa() 函数

类型练习

1019

题目：General Palindromic Number

A number that will be the same when it is written forwards or backwards is known as a Palindromic Number. For example, 1234321 is a palindromic number. All single digit numbers are palindromic numbers.

Although palindromic numbers are most often considered in the decimal system, the concept of palindromicity can be applied to the natural numbers in any numeral system. Consider a number N>0N>0 in base b≥2b≥2, where it is written in standard notation with k+1k+1 digits aia_i as ∑i=0k(aibi)∑^k_{i=0}(a_ib^i). Here, as usual, 0≤ai<b0≤a_i<b for all ii and aka_k is nonzero. Then NN is palindromic if and only if ai=ak−ia_i=a_{k−i} for all ii. Zero is written 0 in any base and is also palindromic by definition.

Given any positive decimal integer NNand a base bb, you are supposed to tell if NNis a palindromic number in base bb.

Input Specification:

Each input file contains one test case. Each case consists of two positive numbers NNand b, where 0<N≤1090<N≤10^9 is the decimal number and 2≤b≤1092≤b≤10^9 is the base. The numbers are separated by a space.

Output Specification:

For each test case, first print in one line Yes if NNis a palindromic number in base bb, or No if not. Then in the next line, print NN as the number in base bbin the form “akak−1...a0a_k a_{k−1} ... a_0”. Notice that there must be no extra space at the end of output.

Sample Input 1:

27 2

Sample Output 1:

Yes
1 1 0 1 1

Sample Input 2:

121 5

Sample Output 2:

No
4 4 1

思路： 构建一个数组，循环计算mod(N,k)，放到数组中，判断数组是否为回文即可

  • while 循环的判断条件为 N!=0 或者 !(N<k)采用第二种时还需把 N 的值放到数组作为最后一个余数，使用第一种

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <cstdio>
#include <vector>
#include <cstdlib>
using namespace std;

int main()
{
    vector<int> mod;
    int N, k;
    scanf("%d %d", &N, &k);
    /*
    while (!(N < k)) // 相等时仍要继续计算，也可以使用 N!=0 作为判断条件
    {
        mod.push_back(N % k);
        N /= k;
    }
    mod.push_back(N); // 将最后的 N 也放入数组
    */
    while (N)
    { // 更简洁的判断条件
        mod.push_back(N % k);
        N /= k;
    }
    bool flag = true;
    for (int i = 0; i < mod.size() / 2; i++)
    { // 判读获取的余数数组是不是回文数
        if (mod[i] != mod[mod.size() - 1 - i])
        {
            flag = false;
            break;
        }
    }
    if (flag)
    {
        printf("Yes\n");
    }
    else
    {
        printf("No\n");
    }
    for (auto i = mod.end() - 1; i != mod.begin(); i--)
    { // 反向输出
        printf("%d ", *i);
    }
    printf("%d", *mod.begin());
    system("pause");
    return 0;
}

1027

题目：Colors in Mars

People in Mars represent the colors in their computers in a similar way as the Earth people. That is, a color is represented by a 6-digit number, where the first 2 digits are for Red , the middle 2 digits for Green , and the last 2 digits for Blue . The only difference is that they use radix 13 (0-9 and A-C) instead of 16. Now given a color in three decimal numbers (each between 0 and 168), you are supposed to output their Mars RGB values.

Input Specification:

Each input file contains one test case which occupies a line containing the three decimal color values.

Output Specification:

For each test case you should output the Mars RGB value in the following format: first output # , then followed by a 6-digit number where all the English characters must be upper-cased. If a single color is only 1-digit long, you must print a 0 to its left.

Sample Input:

15 43 71

Sample Output:

#123456

思路： 十三进制的数字包括 ABC，可以放到字符数组中，用下标的方式进行输出

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
using namespace std; 

int main()
{

    int t1, t2, t3; 
    char c[14] = {"0123456789ABC"}; 
    cin >> t1 >> t2 >> t3; 
    cout << '#'; 
    cout << c[t1 / 13] << c[t1 % 13]; 
    cout << c[t2 / 13] << c[t2 % 13]; 
    cout << c[t3 / 13] << c[t3 % 13]; 
    system("pause");
    return 0;

}

1058

题目：A+B in Hogwarts

If you are a fan of Harry Potter, you would know the world of magic has its own currency system – as Hagrid explained it to Harry, “Seventeen silver Sickles to a Galleon and twenty-nine Knuts to a Sickle, it’s easy enough.” Your job is to write a program to compute A+B where A and B are given in the standard form of Galleon.Sickle.Knut (Galleon is an integer in [0,10710^7], Sickle is an integer in [0,17), and Knut is an integer in [0, 29)).

Input Specification:

Each input file contains one test case which occupies a line with A and B in the standard form, separated by one space.

Output Specification:

For each test case you should output the sum of A and B in one line, with the same format as the input.

Sample Input:

3.2.1 10.16.27

Sample Output:

14.1.28

思路： 处理读取后，按位相加，小位留余

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <cstdio>
#include <cstdlib>

int main()
{
    int a1, b1, c1, a2, b2, c2, a, b, c;
    scanf("%d.%d.%d %d.%d.%d", &a1, &b1, &c1, &a2, &b2, &c2);
    c = c1 + c2; // 由小位到大位，按位相加，小位留余
    b = b1 + b2 + c / 29;
    c = c % 29;
    a = a1 + a2 + b / 17;
    b = b % 17;
    printf("%d.%d.%d", a, b, c);
    /*
    int yuan, jiao, fen;
    scanf("%d.%d.%d", &yuan, &jiao, &fen);
    int t_y, t_j, t_f;
    scanf("%d.%d.%d", &t_y, &t_j, &t_f);
    yuan += t_y;
    jiao += t_j;
    fen += t_f;
    if (!(fen < 29))
    {
        jiao++;
        fen -= 29;
    }
    if (!(jiao < 17))
    {
        yuan++;
        jiao -= 17;
    }
    printf("%d.%d.%d", yuan, jiao, fen);
    */
    system("pause");
    return 0;
}

字符串处理

思想解释

注意细节和输出格式，字符可以直接进行加减，输出需要补零可以用 %02d

字符数组表示数字时使用 -'0' （如果时字母使用 -'A' ) 的方式，含义是使用 ASCII 码求差值

类型练习

1061

题目：Dating

Sherlock Holmes received a note with some strange strings: Let's date! 3485djDkxh4hhGE 2984akDfkkkkggEdsb s&hgsfdk d&Hyscvnm . It took him only a minute to figure out that those strange strings are actually referring to the coded time Thursday 14:04 – since the first common capital English letter (case sensitive) shared by the first two strings is the 4th capital letter D , representing the 4th day in a week; the second common character is the 5th capital letter E , representing the 14th hour (hence the hours from 0 to 23 in a day are represented by the numbers from 0 to 9 and the capital letters from A to N , respectively); and the English letter shared by the last two strings is s at the 4th position, representing the 4th minute. Now given two pairs of strings, you are supposed to help Sherlock decode the dating time.

Input Specification:

Each input file contains one test case. Each case gives 4 non-empty strings of no more than 60 characters without white space in 4 lines.

Output Specification:

For each test case, print the decoded time in one line, in the format DAY HH: MM , where DAY is a 3-character abbreviation for the days in a week – that is, MON for Monday, TUE for Tuesday, WED for Wednesday, THU for Thursday, FRI for Friday, SAT for Saturday, and SUN for Sunday. It is guaranteed that the result is unique for each case.

Sample Input:

3485djDkxh4hhGE
2984akDfkkkkggEdsb
s&hgsfdk
d&Hyscvnm

Sample Output:

THU 14:04

思路： 按照题目所给的方法找到相等的字符后判断即可，如果输出的时间不足 2 位数要在前面添 0，即用 %02d 输出

  • 因为在一对字符串的同一位置出现的相同字符才符合条件，使用一个外部循环条件，减少循环次数，方便操作

  • 符合条件的同时还需判断是否符合逻辑条件，如：星期的字母不会超过 G、小时可以是 N 之前的字母也可以是数字

  • 对星期的输出可以把每一日的代表字符串放到数组中，通过当前字符减去 A 的值作为下标

  • 小时需要根据数字还是字母的类型进行不同的操作，如果是字母减去 A 后还应 +10

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <cctype>
using namespace std; 

int main()
{

    string a, b, c, d; 
    cin >> a >> b >> c >> d; // 输入字符串
    char time[2]; // 记录星期和小时
    int i = 0, j = 0; // 控制字符串遍历，减少循环次数
    int m; // 记录分钟
    while (i < a.length() && i < a.length()) // 同时出现才算符合条件
    {
        if (a[i] == b[i] && (a[i] >= 'A' && a[i] <= 'G')) // 星期字母不会超过 G
        {
            time[0] = a[i]; 
            break; // 保留字符，跳出循环
        }
        i++; 
    }
    i++; 
    while (i < a.length() && i < a.length())
    {
        if (a[i] == b[i] && ((a[i] >= 'A' && a[i] <= 'N') || isdigit(a[i]))) // 数字或者 N 之前的字符
        {
            time[1] = a[i]; 
            break; // 保留并跳出
        }
        i++; 
    }
    while (j < c.length() && j < d.length())
    {
        if (c[j] == d[j] && isalpha(c[j])) // 分钟必须时字母
        {
            m = j; // 只需保存位置
            break; 
        }
        j++; 
    }
    string week[7] = {"MON ", "TUE ", "WED ", "THU ", "FRI ", "SAT ", "SUN "}; 
    printf("%s", week[time[0] - 'A'].c_str()); // 注意输出格式，转换为只读指针
    int h = isdigit(time[1]) ? time[1] - '0' : time[1] - 'A' + 10; //0 也是字符型必须有单引号
    printf("%02d:%02d", h, m); // 输出两位不足补零
    system("pause");
    return 0;

}

1073

题目：Scientific Notation

Scientific notation is the way that scientists easily handle very large numbers or very small numbers. The notation matches the regular expression [±][1-9].[0-9]+E[±][0-9]+ which means that the integer portion has exactly one digit, there is at least one digit in the fractional portion, and the number and its exponent’s signs are always provided even when they are positive.

Now given a real number A in scientific notation, you are supposed to print A in the conventional notation while keeping all the significant figures.

Input Specification:

Each input contains one test case. For each case, there is one line containing the real number A in scientific notation. The number is no more than 9999 bytes in length and the exponent’s absolute value is no more than 9999.

Output Specification:

For each test case, print in one line the input number A in the conventional notation, with all the significant figures kept, including trailing zeros.

Sample Input 1:

+1.23400E-03

Sample Output 1:

0.00123400

Sample Input 2:

-1.2E+10

Sample Output 2:

-12000000000

思路： 将底数和指数分别作为字符串和整数进行保存，然后根据符号和指数位分情况判断

  • 先判断字符串的第一位是否为符号，如果是转换数必然是负数，先输出一个负号

  • 如果指数为负数，那么转换数是小数，直接输出"0."，然后输出指数 -1 个 0，再将底数子串去小数点输出

  • 指数为正数，转换数是一个整数，先输出底数子串的第一位，略过小数点，同时判断输出越界和是否超过指数的大小

  • 如果子串已经全部输出，将指数的剩余大小补 0

  • 指数到达子串未全部输出，输出小数点后继续输出子串

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
using namespace std;

int main()
{
    string str;
    cin >> str;
    int index = 0;
    while (str[index] != 'E')
    {
        index++;
    }
    string f_str = str.substr(1, index - 1); // 从 'E' 进行分割，将指数前的字符去掉符号放到字符子串中
    int e = stoi(str.substr(index + 1));     // 正负号也会进行判断
    if (str[0] == '-')                       // 如果是一个负数，直接输出符号
    {
        cout << '-';
    }
    if (e < 0) // 如果指数是负数，说明结果是一个小数
    {
        cout << "0.";
        for (int i = 0; i < abs(e) - 1; i++)
        {
            cout << '0';
        }
        for (int j = 0; j < f_str.length(); j++)
        {
            if (f_str[j] != '.')
            {
                cout << f_str[j];
            }
        }
    }
    else // 如果是正数
    {
        cout << f_str[0]; // 先输出小数点之前的一位
        int j, cnt;
        for (j = 2, cnt = 0; j < f_str.length() && cnt < e; j++, cnt++)
        { // 略过小数点输出，同时判断长度并构造一个计数不超过指数
            cout << f_str[j];
        }
        if (j == f_str.length()) // 如果字符串全部输出，说明未到指数，后面补零
        {
            for (int k = 0; k < e - cnt; k++)
            {
                cout << '0';
            }
        }
        else // 指数到了指数未到，输出一个小数点继续输出
        {
            cout << '.';
            for (j; j < f_str.length(); j++)
            {
                cout << f_str[j];
            }
        }
    }
    system("pause");
    return 0;
}

1001

题目：A+B Format

Calculate a+ba+b and output the sum in standard format ——that is, the digits must be separated into groups of three by commas (unless there are less than four digits).

Input Specification:

Each input file contains one test case. Each case contains a pair of integers a and b where −106≤a,b≤106−10^6≤a, b≤10^6. The numbers are separated by a space.

Output Specification:

For each test case, you should output the sum of a and b in one line. The sum must be written in the standard format.

Sample Input:

-1000000 9

Sample Output:

-999, 991

思路： 将和值转换为字符串，通过下标判断逗号的输出

  • 判断条件可以从右往左看，当三位时输出一个逗号，也就是字符串的长度 mod3 的位置，在从左往右看，下标 i 从 0 开始，如果 (i + 1) % 3 == len % 3 成立就输出逗号，注意最后一位不输出

  • 第一位输出的可能是一个负号，如果是负号就直接 continue 进入下一次循环，无需判断

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
using namespace std; 

int main()
{

    int a, b; 
    cin >> a >> b; 
    string str = to_string(a + b); 
    int len = str.length(); 
    for (int i = 0; i < len; i++)
    {
        cout << str[i]; 
        if (str[i] == '-')
        {
            continue; // 直接进入下一次循环，防止负号后出现 comma 的情况
        }
        if ((i + 1) % 3 == len % 3 && i + 1 != len)
        {
            cout << ', '; 
        }
    }
    system("pause");
    return 0;

}

1004

题目：Spell It Right

Given a non-negative integer N, your task is to compute the sum of all the digits of N, and output every digit of the sum in English.

Input Specification:

Each input file contains one test case. Each case occupies one line which contains an N (≤10100).

Output Specification:

For each test case, output in one line the digits of the sum in English words. There must be one space between two consecutive words, but no extra space at the end of a line.

Sample Input:

12345

Sample Output:

one five

思路： 使用字符串输入，利用每个字符数组 -'0' 的方式求和，将 sum 转为字符数组，用其实际数字作下标输出英文数字的字符串数组

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using namespace std;

int main()
{
    string a;
    cin >> a;
    int sum = 0;
    for (int i = 0; i < a.length(); i++)
    {
        sum += a[i] - '0';// 将每一位相加（不 -0 计算的是数字存储的 ASCII 码）
    }
    string s = to_string(sum);
    string digit[10] = {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};
    // 将每个数字的读法放到数组中
    cout << digit[s[0] - '0'];
    for (int i = 1; i < s.length(); i++)
    {
        cout << " " << digit[s[i] - '0'];
    }
    system("pause");
    return 0;
}

1035

题目：Password

To prepare for PAT, the judge sometimes has to generate random passwords for the users. The problem is that there are always some confusing passwords since it is hard to distinguish 1 (one) from l (L in lowercase), or 0 (zero) from O (o in uppercase). One solution is to replace 1 (one) by @ , 0 (zero) by % , l by L , and O by o . Now it is your job to write a program to check the accounts generated by the judge, and to help the juge modify the confusing passwords.

Input Specification:

Each input file contains one test case. Each case contains a positive integer N (≤1000), followed by N lines of accounts. Each account consists of a user name and a password, both are strings of no more than 10 characters with no space.

Output Specification:

For each test case, first print the number M of accounts that have been modified, then print in the following M lines the modified accounts info, that is, the user names and the corresponding modified passwords. The accounts must be printed in the same order as they are read in. If no account is modified, print in one line There are N accounts and no account is modified where N is the total number of accounts. However, if N is one, you must print There is 1 account and no account is modified instead.

Sample Input 1:

3
Team000002 Rlsp0dfa
Team000003 perfectpwd
Team000001 R1spOdfa

Sample Output 1:

2
Team000002 RLsp%dfa
Team000001 R@spodfa

Sample Input 2:

1
team110 abcdefg332

Sample Output 2:

There is 1 account and no account is modified

Sample Input 3:

2
team110 abcdefg222
team220 abcdefg333

Sample Output 3:

There are 2 accounts and no account is modified

思路： 循环进行判断，将符合条件的字符串放入字符数组，判断完分情况输出

  • 输入密码后循环判断每一个字符（switch()或if()），更改即可；同时设置一个变量进行判断是否被修改

  • 若修改放入动态数组，最后根据数组大小和 N 的值输出相应结果

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>
#include <vector>
using namespace std; 

int main()
{

    int n; 
    cin >> n; 
    vector<string> list; 
    for (int i = 0; i < n; i++) // 建立人数循环
    {
        string name, password; 
        cin >> name >> password; 
        int flag = 0; 
        for (int j = 0; j < password.length(); j++)
        {
            switch (password[j]) // 依次更换符合要求的值
            {
            case '1':
                password[j] = '@'; 
                flag = 1; 
                break; // 这里的 break 不是跳出循环，而是不执行后面的判断
            case '0':
                password[j] = '%'; 
                flag = 1; 
                break; 
            case 'l':
                password[j] = 'L'; 
                flag = 1; 
                break; 
            case 'O':
                password[j] = 'o'; 
                flag = 1; 
                break; 
            }
        }
        if (flag) // 被更改则放入数组
        {
            string temp = name + " " + password; 
            list.push_back(temp); 
        }
    }
    if (list.size()) // 数组中有元素就输出被更改的元素
    {
        cout << list.size() << endl; 
        for (int i = 0; i < list.size(); i++)
            cout << list[i] << endl; 
    }
    else if (n == 1)
    {
        printf("There is 1 account and no account is modified"); 
    }
    else
    {
        printf("There are %d accounts and no account is modified", n); 
    }
    system("pause");
    return 0;

}

1077

题目：Kuchiguse

The Japanese language is notorious for its sentence ending particles. Personal preference of such particles can be considered as a reflection of the speaker’s personality. Such a preference is called “Kuchiguse” and is often exaggerated artistically in Anime and Manga. For example, the artificial sentence ending particle “nyan~” is often used as a stereotype for characters with a cat-like personality:

  • Itai nyan~ (It hurts, nyan~)

  • Ninjin wa iyada nyan~ (I hate carrots, nyan~)

Now given a few lines spoken by the same character, can you find her Kuchiguse?

Input Specification:

Each input file contains one test case. For each case, the first line is an integer N (2≤N≤100). Following are N file lines of 0~256 (inclusive) characters in length, each representing a character’s spoken line. The spoken lines are case sensitive.

Output Specification:

For each test case, print in one line the kuchiguse of the character, i.e., the longest common suffix of all N lines. If there is no such suffix, write nai.

Sample Input 1:

3
Itai nyan~
Ninjin wa iyadanyan~
uhhh nyan~

Sample Output 1:

nyan~

Sample Input 2:

3
Itai!
Ninjinnwaiyada T_T
T_T

Sample Output 2:

nai

思路： 每输入一个字符串，就把它逆序过来再比较

  • 首先 ans = s；后来每输入的一个字符串，都和 ans 比较，如果后面不相同的就把它截取掉，根据 ans 的长度判断输出

  • 输入数字后再获取整行字符时会直接获取数字后的换行符，可以使用 getchar() 截取，或使用 scanf("%d``\n``", &n); 输入数字

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include  [algorithm] 
using namespace std;

int main()
{
    int n;
    cin >> n;
    getchar(); // 截获、n，不然下面读取字符串时第一个读取的是换行符
    string ans;
    for (int i = 0; i < n; i++)
    {
        string s;
        getline(cin, s);
        reverse(s.begin(), s.end()); // 反转后方便判断
        if (i == 0)
        {
            ans = s;
            continue;
        }
        else
        {
            if (s.length() < ans.length()) // 判断最短的
            {
                swap(ans, s);
            }
            int minlen = min(s.length(), ans.length());
            for (int j = 0; j < minlen; j++)
            {
                if (ans[j] != s[j])
                {
                    ans = ans.substr(0, j); // 将公共子串截取出来
                    break;
                }
            }
        }
    }
    reverse(ans.begin(), ans.end()); // 再翻转回初始状态
    if (ans.length() == 0)
    {
        ans = "nai";
    }
    cout << ans;
    system("pause");
    return 0;
}

1082

题目：Read Number in Chinese

Given an integer with no more than 9 digits, you are supposed to read it in the traditional Chinese way. Output Fu first if it is negative. For example, -123456789 is read as Fu yi Yi er Qian san Bai si Shi wu Wan liu Qian qi Bai ba Shi jiu . Note: zero (ling ) must be handled correctly according to the Chinese tradition. For example, 100800 is yi Shi Wan ling ba Bai .

Input Specification:

Each input file contains one test case, which gives an integer with no more than 9 digits.

Output Specification:

For each test case, print in a line the Chinese way of reading the number. The characters are separated by a space and there must be no extra space at the end of the line.

Sample Input 1:

-123456789

Sample Output 1:

Fu yi Yi er Qian san Bai si Shi wu Wan liu Qian qi Bai ba Shi jiu

Sample Input 2:

100800

Sample Output 2:

yi Shi Wan ling ba Bai

思路： 同时设置 left 和 right 两个坐标，按四位一节进行输出

  • 先构建数字单词和位数单词数组，用下标控制读出来
  • 使用两个下标，确保间隔不超过四，始终指向同一小节
  • 循环嵌套，每次输出一个小节，同时注意单个小节的内位数（千、百、十）；每输出一小节判断其的外位数（万、亿）

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
using namespace std; 

int main()
{

    string num[10] = {"ling", "yi", "er", "san", "si", "wu", "liu", "qi", "ba", "jiu"}; // 数字单词
    string wei[5] = {"Shi", "Bai", "Qian", "Wan", "Yi"}; // 位数单词
    string str; 
    cin >> str; // 输入字符串
    int left = 0, right = str.length() - 1; // 设置左右下标，四位一组输出
    if (str[0] == '-')
    {
        cout << "Fu"; // 符号单独处理
        left++; // 从下标 1 开始
    }
    while (left + 4 <= right)
    {
        right -= 4; // 始终让 left 和 right 在同一节
    }
    while (left < str.length()) // 没全部读出就始终循环
    {
        bool zero = false; 
        bool isPrint = false; 
        while (left <= right) // 单节处理
        {
            if (left > 0 && str[left] == '0')
            { // 标识零位
                zero = true; 
            }
            else
            {
                if (zero) // 先判断之前有无零位
                {
                    cout << " ling"; 
                    zero = false; 
                }
                if (left > 0) // 只要不是第一个数组就必须用空格分割
                {
                    cout << " "; 
                }
                cout << num[str[left] - '0']; // 输出数字
                isPrint = true; // 标志有输出，需要进行万或者亿的输出
                if (left != right)            // 只要这一节没到最后一个字符就要输出千、百、十
                {
                    cout << " " << wei[right - left - 1]; 
                }
            }
            left++; // 左下标后移
        }
        if (isPrint && right != str.length() - 1) // 有输出而且不是最后一节
        {
            cout << " " << wei[(str.length() - right) / 4 + 2]; // 输出万或者亿
        }
        right += 4; // 右坐标移动到下一节
    }
    system("pause");
    return 0;

}

1040

题目：Longest Symmetric String

Given a string, you are supposed to output the length of the longest symmetric sub-string. For example, given Is PAT&TAP symmetric?, the longest symmetric sub-string is s PAT&TAP s, hence you must output 11.

Input Specification:

Each input file contains one test case which gives a non-empty string of length no more than 1000.

Output Specification:

For each test case, simply print the maximum length in a line.

Sample Input:

Is PAT&TAP symmetric?

Sample Output:

11

思路： 使用每个字符或者两个字符中的空格作为对称轴进行双向遍历，更新最大长度即可

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
using namespace std;

int main()
{
    string str;
    getline(cin, str);
    int maxlen = 0, j, k;
    for (int i = 0; i < str.size(); i++) // 以字符做对称轴
    {
        for (j = i, k = i; j >= 0 && k < str.size() && str[j] == str[k]; j--, k++)
            ;
        if (k - j - 1 > maxlen)
        {
            maxlen = k - j - 1;
        }
    }
    for (int i = 0; i < str.size() - 1; i++) // 字符中间做对称轴
    {
        for (j = i, k = i + 1; j >= 0 && k < str.size() && str[j] == str[k]; j--, k++)
            ;
        if (k - j - 1 > maxlen)
        {
            maxlen = k - j - 1;
        }
    }
    cout << maxlen;
    return 0;
}

总结

  1. 模拟类的题就是根据要求写代码即可，主要考察思路而不是算法，代码尽量简洁，善用数组和头文件
  2. 使用函数赋值变量时注意其返回值，指针和迭代器要进行取值
  3. 根据输入的第一个 N 创建循环，输入的数据尽量使用临时变量在循环中处理即可，减少时间复杂度
  4. 根据题意总结公式，输出的格式几乎都可以使用下标找到规律
  5. 字符串的处理要多变，如：翻转后方便处理，输出多个时直接相加
  6. 输入一个数字后紧跟 getline()进行字符串的输出，会接受到数字后的换行符，可在中间加一个 getchar()进行换行符的截获或者是使用 scanf("%d\n",&n); 的方式输入数字
  • 本文标题：PAT 甲级 - 入门模拟
  • 本文作者：Aidan
  • 创建时间：2021-08-08 15:44:06
  • 本文链接：https://aidanblog.top/pat_level_a-get_start/
  • 版权声明：本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
 评论