• PAT (Basic Level) Practice 1023~1044

    PTA Basic Level Practice 解题思路和代码，主要用的是 C++。每22题一篇博客，可以按目录来进行寻找。

    文章目录

    1023 组个最小数

    思路：
    只需要注意，若数字0的个数不为1，那么先打印一个最小的非零数，题目保证了输入至少有一个非零数，所以第一个 while 循环停止时得到的 i 就是最小的非零数。

    #include 
using namespace std;

int main()
{
    int a[10] = {0}, n, i = 0;
    for (int j = 0; j < 10; ++j)        // 输入每个数字的个数
        cin >> a[j];
    if (a[0] != 0)
    {
        while (++i < 10 && a[i] == 0);  // 注意 i 不能大于数组长度
        cout << i;
        --a[i]; // 个数减1
    }

    for (i = 0; i < 10; ++i)    // 依次将剩余的数字输出完即可
        while (a[i]--)
            cout << i;

    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    1024 科学计数法

    思路：
    输入的是 a . b ∗ 1 0 c a.b*10^c a.b∗10c 的字符串形式，用字符串 n 保存 a.b ，整数 e 保存 c 的整数值。

    • 当指数小于0时小数点需要向左移动，那么先打印 “0.”，然后打印 abs(e) - 1个0，最后打印 n（不打印小数点）。
    • 当指数大于等于0时小数点需要向右移动，那么先打印 n 中的 a，跳过小数点；打印 b，每打印一个数字 e 就减1。

    注意：

    1. 如打印完 n 后 e 的值不为0，就在后面补上 e - n.size() 个0，e 如果等于 n.size() 就不会打印0。
    2. 如果循环结束了 n 没被打印完，说明 e 为0，此时补一个小数点，继续打印 n 剩余的字符。

    注意是科学计数法，所以整数部分一定是非零的数。这里提供几组测试数据：

    // 测试数据			// 结果
-1.400510E+13		-14005100000000
+1.23400E-03		0.00123400
-1.2E+10			-12000000000
-1.001482650E+6		-1001482.650
+2.515E+3			2515

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    补充：

    • stoi() 会把字符串转换为相应的整数，即 string to int；要转为浮点数可以用 stod 函数，即 string to double。它会自动识别正负号以及小数点。
    • substr(int a, int b) 返回的是调用对象下标 [a, b] 之间的字符串。
    #include 
using namespace std;

int main()
{
    string s, n;
    int i = 0;
    cin >> s;
    while (s[++i] != 'E');              // 当 s[i] = 'E' 时停止循环
    n = s.substr(1, i - 1);
    int e = stoi(s.substr(i + 1));      // 将指数部分的字符串转为整数，保存在 e 中
    if (s[0] == '-') cout << "-";       // 负数需要打印负号
    if (e < 0)  // 指数小于0
    {
        cout << "0.";
        for (int j = 0; j < abs(e) - 1; ++j) cout << "0";
        for (int j = 0; j < n.size(); ++j)
            if (n[j] != '.') cout << n[j];  // 打印 n 中除小数点外的所有数字
    }
    else        // 指数大于0
    {
        cout << n[0];
        for (i = 2; i < n.size() && e > 0 ; ++i, --e) cout << n[i]; // 跳过小数点开始打印
        if (i == n.size())  // 循环结束后 n 被打印完了，则打印0
            while(e--) cout << "0";
        else                // 循环结束了 n 没有被打印完
        {
            cout << ".";    // 先打印小数点
            while (i < n.size()) cout << n[i++];                    // 打印 n 剩余的部分
        }
    }

    return 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

    代码解答：

    1. 最后一个 for 循环的判定块，为什么是 e > 0 而不是 e >= 0？

    在 for 循环中，每打印一个字符的的同时 e 会减去1，当 e 为0时就表明已经打印了 e 个字符。如果判定条件是 e >= 0，会导致循环多走一次，e 的值就变为-1了。

    1. 为什么最后一个 if 不用 e > 0 来判定而是 i == n.size()？

    在上一个问题中提到，for 循环中每打印一个字符的的同时 e 会减去1。也就表明当 e = 0 或 i = n.size() 的时候循环会结束。之所以只有后者能成为判定条件的原因是，如果在循环开始时，e = n.size()，那么循环结束后 e = 0 和 i = n.size() 同时成立。此时判定 if (e > 0) 会失败，进入 else 语句块，从而多打印一个小数点，但实际上并不需要。

    1025 反转链表

    思路：
    reverse(b, e) 的作用是倒转 [b, e) 范围内的元素。我将结点信息单独抽出来定义成数组，将地址当下标，数据和下一结点的地址存入下标对应的空间中。结点之间的先后顺序就放在 node 数组中，每个元素的值对应一个结点的地址。使用 reverse 函数就可以很方便的改变它们的先后顺序，输出时就只需要输出 node[i] 即可。

    • 不一定是所有输入的结点都在链表上，所以读取完数据后，要先遍历一遍链表统计一下有效结点的个数。
    • 不选用结构体来存储每个结点信息的原因在于，reverse 函数只能改变元素的相对顺序，并没有改变其中的结点信息（Data 和 Next）。
    #include 
#include 
using namespace std;

int main()
{
    int first, n, k, _addr, i, cnt = 0;
    int node[100010], data[100010], next[100010];
    cin >> first >> n >> k;
    while (n--)
    {
        cin >> _addr;
        cin >> data[_addr] >> next[_addr];
    }

    while (first != -1)         // 遍历链表，统计有效结点的个数
    {
        node[cnt++] = first;    // 将链表上的结点按顺序存入 node 数组中
        first = next[first];    // 令 first 指向下一个结点
    }
    for (int i = 0; i < (cnt - cnt % k); i += k)    // 倒转每 k 个元素
        reverse(begin(node) + i, begin(node) + i + k);
    for (int i = 0; i < cnt - 1; ++i)               // -1不需要格式化输出，所以单独写作一行
        printf("%05d %d %05d\n", node[i], data[node[i]], node[i + 1]);
    printf("%05d %d -1", node[cnt - 1], data[node[cnt - 1]]);

    return 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

    1026 程序运行时间

    #include 
#include 
using namespace std;

int main()
{
    int c1, c2;
    cin >> c1 >> c2;
    int t = floor((c2 - c1)/100.0 + 0.5);
    printf("%02d:%02d:%02d", t / 3600,  t % 3600 / 60, t % 60);

    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    1027 打印沙漏

    思路：
    用 m 来代表上三角的行数，对 m 不断自增，同时计算沙漏中总的字符个数，直到其大于 n 为止。我使用的是等差数列的求和公式，读者可以思考其他的方法。

    • 假设上三角有 n 行，那么上三角的字符个数是 n 2 n^2 n2，沙漏中总的字符个数就为 2 n 2 − 1 2n^2-1 2n2−1。
    • while 循环执行完后 m 要执行减1操作。因为退出循环时的 m 值，比上三角的实际行数要大1。
    #include 
using namespace std;

int main()
{
    int n, m = 0;
    char c;
    cin >> n >> c;
    while (2 * m * m - 1 <= n) ++m;  // 计算上三角的行数
    m -= 1;
    for (int i = m; i > 0; --i)
    {   // 打印上三角，打印到沙漏中间顶点处
        for (int j = 0; j < m - i; ++j) cout << " ";     // 打印空白
        for (int j = 0; j < 2 * i - 1; ++j) cout << c;  // 打印字符
        cout << endl;
    }
    for (int i = 2; i <= m; ++i)
    {   // 打印下三角，因为顶点已经打印过，所以从第二行开始打印
        for (int j = 0; j < m - i; ++j) cout << " ";     // 打印空白
        for (int j = 0; j < 2 * i - 1; ++j) cout << c;  // 打印字符
        cout << endl;
    }
    cout << n - 2 * m * m + 1;

    return 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

    1028 人口普查

    思路：
    用结构体来存储每个人的姓名和出生日期，对输入的数据进行逐个处理。old 和 young 分别存储当前的最年长和最年轻的人；temp 保存当前输入；left 和 right 分别表示左界和右界，只有当出生日期处于这个区间内才算有效生日。

    • 生日日期越大的人越年轻，生日日期越小越年长。
    • iostream 头文件中已经包含了头文件 stdio.h，所以不需要再 include 一次。

    另外有个问题记录一下。如果引入了头文件 iostream，那么在定义结构体时同时定义变量 left 和 right（也就是说将 left 和 right 定义成全局变量），会出现如下报错：

    error: reference to ‘left’ is ambiguous
    error: reference to ‘right’ is ambiguous

    原因是在 iostream 头文件中包含有同名的全局结构体变量 left 和 right，当然这时的结构体并不是我们自己定义的结构体。但编译器区分不了你指的是头文件中的还是你自己定义的，解决办法就是给变量换个名字（加个大写、下划线什么的），或者将变量的定义放到函数中，将其定义成局部变量。本代码采用后者。

    最后补充一点，在 C 语言中，定义结构体变量时必须加上 struct 关键字，如下：

    struct person temp;

    • 1

    在 C++ 11 之后就可以直接用结构名来定义结构体变量了。

    #include 
using namespace std;

struct person
{
    char name[10];
    int y, m, d;
};

bool LessEqu(person a, person b)
{   // 小于等于函数，a 比 b 年长、即生日更小时返回 true
    if (a.y != b.y) return a.y < b.y;
    else if (a.m != b.m) return a.m < b.m;
    else return a.d <= b.d;
}

bool MoreEqu(person a, person b)
{   // 大于等于函数，a 比 b 年轻、即生日更大时返回 true
    if (a.y != b.y) return a.y > b.y;
    else if (a.m != b.m) return a.m > b.m;
    else return a.d >= b.d;
}

int main()
{
    person old, young, left, right, temp;
    young.y = left.y = 1814;    // 左界是 1814.09.06，右界是 2014.09.06
    old.y = right.y = 2014;
    young.m = old.m = left.m = right.m = 9;
    young.d = old.d = left.d = right.d = 6;
    int n, cnt = 0;
    scanf("%d", &n);
    while (n--)
    {
        scanf("%s %d/%d/%d", temp.name, &temp.y, &temp.m, &temp.d);
        if (MoreEqu(temp, left) && LessEqu (temp, right))
        {   // 比右界小，比左界大才的生日纳入统计和比较
            ++cnt;
            if (LessEqu(temp, old)) old = temp;
            if (MoreEqu(temp, young)) young = temp;
        }
    }
    if (cnt == 0) cout << "0";
    else cout << cnt << " " << old.name << " " << young.name;

    return 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

    1029 旧键盘

    思路：
    第二个字符串 b 是第一个字符串 a 的删减版，题目的要求就是打印删减掉的字符，小写字母则转为大写字母打印。p[x] = 0 表示对应的字符 x 还没输出过。i 和 j 分别指向 a 和 b，如果对应的字符相等，i，j 同时向后移动；不相等时，说明 i 指向的字符不在 b 中，此时如果其是小写字母就先转为大写字母，再将其打印出来。最后别忘记打印 a 中没输出过但也不在 b 中的字符。

    #include 
using namespace std;

int main()
{
    string a, b;
    int i = 0, j = 0, p[128] = {0};
    cin >> a >> b;
    for (; i < a.size() && j < b.size(); ++i)
    {
        if (a[i] != b[j])
        {
            if (a[i] >= 'a' && a[i] <= 'z') a[i] -= 32; // 将小写字母转为大写字母
            if (p[a[i]] == 0)
            {
                cout << a[i];
                p[a[i]] = 1;
            }
        }
        else ++j;
    }
    for (; i < a.size(); ++i)   // 将 b 中剩余的部分打印出来
    {
        if (a[i] >= 'a' && a[i] <= 'z') a[i] -= 32;     // 将小写字母转为大写字母
        if (p[a[i]] == 0)
        {
            cout << a[i];
            p[a[i]] = 1;
        }
    }

    return 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

    柳婼大神的代码，短小精悍到让我膜拜。她的思路是这样的：用 ans 来保存缺失的字符。遍历字符串 a 中的字符，如果其不在字符串 b 中，且其大写也不在 ans 中，则将其添加到 ans 末尾。对 string 对象调用 find(x) 函数，返回的是字符 x 在字符串中的位置，没找到的话返回 string::npos，其值是-1。toupper(x) 函数将 x 转为大写字母并返回，如果 x 不是小写字母则返回 x：

    #include 
using namespace std;

int main()
{
    string a, b, ans;
    cin >> a >> b;
    for (int i = 0; i < a.length(); ++i)
        if (b.find(a[i]) == string::npos && ans.find(toupper(a[i])) == string::npos)
            ans += toupper(a[i]);	// 转为大写后再存入 ans
    cout << ans;

    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    1030 完美数列

    思路：
    将所有正整数读入一个数组，然后用 sort 进行递增排序，那么完美数列一定是这个数组序列的子集。基本思想是外循环令i 指向子数列的头，每次循环向后移动；内循环令j 指向数列的尾，每次循环后向后移动。这样子 i 和 j 之间的元素就组成了一个子序列。类似于滑动窗口一样，固定住头部 i 然后尾部不断后移以寻找最大的完美数列。ans 保存每一轮外循环后得到的完美数列中正整数个数的最大值，temp 保存当前内循环中找到的完美数列中正整数的个数。

    外循环下标 i 从0开始，也就是最小值开始；因为是为了寻找最大的 ans，所以 j 从 i 之后的 ans 个位置开始遍历。如果 i 指向的最小值乘上 p 大于等于 j，表明其符合完美数列的要求，然后计算 i 和 j 之间的正整数的个数，如果大于 ans 就更新；否则退出内循环，因为此时再往后都不符合完美数列的要求。

    • 测试点四需要优化双循环，否则会出现超时。建议不要从尾部开始遍历，因为排序后较大的正整数集中在数组尾部，此时乘法运算结果会很耗时。
    • 测试点五会出现超过 int 的数，所以需要将变量用 long long 来定义，否则一定会答案错误。
    #include 
#include 
#include 
using namespace std;

int main()
{
    long long n, p, t, ans = 1, temp = 0;	// ans 至少为1，即 m = M 时
    cin >> n >> p;
    vector<long long> vec(n, 0);
    for (int i = 0; i < n; ++i)			// 从柳神那学到的方法，很好用
        cin >> vec[i];
    sort(vec.begin(), vec.end());       // 递增排序
    for (int i = 0; i < n; ++i)			// 外循环，固定子序列的头部 i
    {
        for (int j = i + ans; j < n; ++j)
        {	// 内循环 j 不停地后移，直到包含的子序列不满足完美数列
            if (vec[i] * p >= vec[j])
            {
                temp = j - i + 1;       // 更新完美数列中正整数的个数
                if (temp > ans) ans = temp;
            }
            else break;                 // 不满足完美数列要求，就没必要继续循环
        }

    }
    cout << ans;

    return 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

    1031 查验身份证

    思路：
    加权求和就是将每一位的数乘上权值，最后取和。

    #include 
using namespace std;

int main()
{
    int n, sum, flag = 0, i, cnt = 0;
    int  weight[] = {7, 9, 10, 5, 8, 4, 2, 1, 6, 3, 7, 9, 10, 5, 8, 4, 2};
    string id, M("10X98765432");
    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        cin >> id;
        int j, sum = 0;
        for (j = 0; j < 17; ++j)
        {	// j 如果能正常执行到17说明前17位都是数字
            if (id[j] >= '0' && id[j] <= '9')
                sum += (id[j] - '0') * weight[j];
            else break;
        }
        if (j == 17 && id[17] == M[sum % 11]) ++cnt;
        else cout << id << endl;
    }
    if (cnt == n) cout << "All passed";

    return 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

    1032 挖掘机技术哪家强

    #include 
using namespace std;

int main()
{
    int n, i, j, p, q = -1, score[100010] = {0};
    cin >> n;
    while (n--)	// 输入数据的同时寻找最大总分，并记录学校编号
    {
        cin >> i >> j;
        score[i] += j;
        if (score[i] > q)
        {
            p = i;
            q = score[i];
        }
    }
    cout << p << " " << q;

    return 0;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    1033 旧键盘打字

    s1 保存坏键，s2 保存应输入的文字。输入 s1，s2，然后遍历 s2。如果字母是小写字母，则查找其大写是否在 s1中；如果字母是大写字母，则查找上档键是否在 s1 中；其他的键则直接查找其是否在 s1 中。此题可参考 1029 旧键盘。

    • 只有 “+” 是上档键。
    • 测试点2的第二行输入是空白，用 cin 无法读入空白，所以要用 getline 来读取空字符串。
    • 测试点4考察代码是否能够正确判断大小写。如果坏键中有大写字母，相应的应输入的文字里的大小写都不能打印；如果没有大写字母但有上档键，应数入的文字里的所有大写都不能打印。
    • 在 C 中 isupper() 和 toupper() 是声明在头文件 ctype.h 里的，但是头文件 iostream 也已经包含了它俩，因此不用 include。
    #include 
using namespace std;

int main()
{
    string s1, s2;
    getline(cin, s1);
    getline(cin, s2);
    for (int i = 0; i < s2.size(); ++i)
    {
        if (s1.find(toupper(s2[i])) != string::npos) continue;
        if (isupper(s2[i]) && s1.find('+') != string::npos) continue;
        cout << s2[i];
    }

    return 0;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    1034 有理数四则运算

    思路：
    有理数的四则运算可以参考博客：OJ 刷题必备知识总结（一） 25、分数的表示和化简。

    #include 
#include 
using namespace std;
typedef long long ll;

ll gcd(ll a, ll b)
{   // 求 a 与 b 的最大公约数
    return !b ? a : gcd(b, a % b);
}

struct Fraction     // 分数结构体
{
    ll up, down;    // 分别表示分子和分母
}a, b;

Fraction reduction(Fraction result)     // 化简
{
    if (result.down < 0)    // 分子为负，分子分母变相反数
    {
        result.up = -result.up;
        result.down = -result.down;
    }
    if (result.up == 0)     // 分子为0，分母变1
        result.down = 1;
    else                    // 分子不为0，约分
    {
        int d = gcd(abs(result.up), abs(result.down));  // 求分子分母的最大公约数
        result.up /= d;     // 约去最大公约数
        result.down /= d;
    }

    return result;
}

Fraction add(Fraction f1, Fraction f2)          // 分数加法
{
    Fraction result;
    result.up = f1.up * f2.down + f2.up * f1.down;
    result.down = f1.down * f2.down;
    return reduction(result);
}

Fraction minu(Fraction f1, Fraction f2)         // 分数减法
{
    Fraction result;
    result.up = f1.up * f2.down - f2.up * f1.down;
    result.down = f1.down * f2.down;
    return reduction(result);
}

Fraction multiply(Fraction f1, Fraction f2)     // 分数乘法
{
    Fraction result;
    result.up = f1.up * f2.up;
    result.down = f1.down * f2.down;
    return reduction(result);
}

Fraction divide(Fraction f1, Fraction f2)       // 分数除法
{
    Fraction result;
    result.up = f1.up * f2.down;
    result.down = f1.down * f2.up;
    return reduction(result);
}


void showResult(Fraction r)
{
    r = reduction(r);       //先化简

    if (r.up < 0) cout << "(";
    if (r.down == 1) cout << r.up;          // 整数
    else if (abs(r.up) > r.down)            // 假分数
        cout << r.up / r.down << " " << abs(r.up) % r.down << "/" << r.down;
    else cout << r.up << "/" << r.down;     // 真分数
    if (r.up < 0) cout << ")";
}

int main()
{
    scanf("%lld/%lld %lld/%lld", &a.up, &a.down, &b.up, &b.down);
    // 加法
    showResult(a);
    cout << " + ";
    showResult(b);
    cout << " = ";
    showResult(add(a, b));
    cout << endl;
    // 减法
    showResult(a);
    cout << " - ";
    showResult(b);
    cout << " = ";
    showResult(minu(a, b));
    cout << endl;
    // 乘法
    showResult(a);
    cout << " * ";
    showResult(b);
    cout << " = ";
    showResult(multiply(a, b));
    cout << endl;
    // 除法
    showResult(a);
    cout << " / ";
    showResult(b);
    cout << " = ";
    if (b.up == 0)cout << "Inf";
    else showResult(divide(a, b));
    cout << endl;

    return 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
    • 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
    • 111
    • 112
    • 113
    • 114
    • 115

    1035 插入与归并

    思路：
    排序算法的知识可参考博客：四大排序算法：插入、交换、选择以及归并排序 1.1 直接插入排序 和 3.2 归并排序递归实现。

    如果实在不明白如何做，可以在代码中写出归并和插入排序的函数，然后创建初始序列的一个副本，两者分别调用一个排序函数。检查排序过程中得到的序列和输入的中间序列是否相同，属于比较常规的解法。

    这里采用柳婼大佬的思路：插入排序有一个很重要的特征便是，其中间序列分为左边的有序部分和右边的无序部分。无序部分的元素与初始序列的元素是完全一样的，以此可以来判断题目给定的输入序列是否是插入排序的中间序列。如果不是，则是归并排序，可以手动对序列进行一次归并排序，然后打印它的结果。

    判断是否是插入排序的两个 for 循环：i 用于遍历序列中的有序部分，因为生成的是中间序列，所以第二行的序列最多只有前 n - 1 个元素是有序的。第一个 for 循环停止时，i 指向的刚好是有序部分的最后一个元素。j 指向 i 之后、无序部分的第一个元素，用于比较无序部分的元素与初始序列的后部分元素是否一样。如果完全一样，当循环结束时，j 的值应为 n。题目要求打印用排序算法再迭代一轮后的结果，只需利用 sort 函数排序即可，当然你也可以自己写出插入排序来实现。sort(a, b) 函数对 [a, b) 内的元素进行排序，所以传入的参数应该是 a 和 a + i + 2。

    对原始序列进行归并排序，每次都检查当前的序列与题给的中间序列是否相等。相等则说明找到了，则不修改 flag 的值，在下面进行一次迭代后打印即可；不相等则使 flag 保持为1继续迭代。

    注意第十一行一定要用小于等于，因为输入的序列中可能存在重复的元素。

    #include 
#include 
using namespace std;

int main()
{
    int a[110], b[110], n, i, j;
    cin >> n;
    for (i = 0; i < n; ++i) cin >> a[i];
    for (i = 0; i < n; ++i) cin >> b[i];
    for (i = 0; i < n - 1 && b[i] <= b[i + 1]; ++i);
    for (j = i + 1; j < n && a[j] == b[j]; ++j);
    if (j == n)
    {
        cout << "Insertion Sort" << endl;
        sort(a, a + i + 2);
    }
    else
    {
        cout << "Merge Sort" << endl;
        int step = 1, flag = 1;
        while (flag)
        {
            flag = 0;
            for (i = 0; i < n; ++i          // 对应元素不相等，说明还没迭代到题给的中间序列
                if (a[i] != b[i]) flag = 1; // flag = 1 表明还需要迭代
            step *= 2;                      // 每次循环乘2，相当于两组合并为了一组
            for (i = 0; i < n; i += step)   // 迭代一次归并排序
                sort(a + i, a + min(i + step, n));
        }
    }
    cout << a[0];                           // 首元素之前不打印空格
    for (i = 1; i < n; ++i)
        cout << " " << a[i];

    return 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

    1036 跟奥巴马一起编程

    #include 
using namespace std;

int main()
{
    int n, col;
    char c;
    cin >> n >> c;
    for (int i = 0; i < n; ++i) cout << c;
    col = n % 2 == 0 ? n / 2 : n / 2 + 1;
    for (int i = 0; i < col - 2; ++i)
    {
        cout << "\n" << c;
        for (int j = 0; j < n - 2; ++j) cout << " ";
        cout << c;
    }
    cout << endl;
    for (int i = 0; i < n; ++i) cout << c;

    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    1037 在霍格沃茨找零钱

    #include 
using namespace std;

int main()
{
    int P, A, G, S, K, g, s, k;
    scanf("%d.%d.%d", &G, &S, &K);
    scanf("%d.%d.%d", &g, &s, &k);
    P = G * 493 + S * 29 + K;
    A = g * 493 + s * 29 + k;
    int t = fabs(P - A);
    if (P < A) printf("%d.%d.%d", t / 493, t % 493 / 29, t % 29);
    else printf("%d.%d.%d", -t / 493, t % 493 / 29, t % 29);

    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    1038 统计同成绩学生

    #include 
using namespace std;

int main()
{
    int hashTable[110] = {0}, n, k, score;
    cin >> n;
    while (n--)
    {
        cin >> score;
        ++hashTable[score];
    }
    cin >> k;
    while (k--)
    {
        cin >> score;
        cout << hashTable[score];
        if (k) printf(" ");
    }

    return 0;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23

    1039 到底买不买

    思路：
    摊主的串保存在 s1 中，小红想要的串保存在 s2 中。用一个数组来保存 s1 中每个字符的个数，下标是字符的 ASCII 值。枚举 s2 中的每个字符，如果对应的数组值不为0，就减1，否则 ++cnt，cnt 拿来统计缺失的字符个数。最后 cnt 不为0就输出 No，否则输出 Yes，多余的珠子个数就是两个串的长度差。

    #include 
using namespace std;

int main()
{
    int p[130] = {0}, cnt = 0;
    string s1, s2;
    cin >> s1 >> s2;
    for (auto i : s1) ++p[i];
    for (auto i : s2)
    {
        if (p[i] > 0) --p[i];
        else ++cnt;
    }
    if (cnt) cout << "No " << cnt;
    else cout << "Yes " << s1.size() - s2.size();

    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    1040 有几个PAT

    思路：
    以字符 A 为核心来统计。先统计字符串中 T 的个数，然后从头枚举字符串中的每个字符：

    • 如果是 P，则计数+1。
    • 如果是 T，则计数-1。
    • 如果是 A，其左边的 P 的个数乘上右边 T 的个数即为以该 A 为中心组成的 PAT 个数。将其结果加到 ans 上，结果要取个余数。

    另一个注意点就是计数变量要用 long long 来定义。

    #include
using namespace std;

int main()
{
    string s;
    long long ans = 0, cnt_P = 0, cnt_T = 0, n = 1000000007;
    cin >> s;
    for (auto i : s)
        if (i == 'T') ++cnt_T;
    for (int i = 0; i < s.size(); ++i)
    {
        if (s[i] == 'P') ++cnt_P;       // 左边 P 的个数+1
        else if (s[i] == 'T') --cnt_T;  // 右边 T 的个数-1
        else ans = (ans + cnt_P * cnt_T) % n;
    }
    cout << ans;

    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    1041 考试座位号

    思路：
    定义一个 string 的二维数组 stu[1010][2]，试机座位号为 s，stu[s][0] 保存学生准考证号 id，stu[s][1] 保存考试座位号 seat。然后直接根据输入的要查询的试机号 s 打印 stu[s][0] 和 stu[s][1] 。

    #include 
using namespace std;

int main()
{
    string stu[1010][2], id, seat;
    int n, m, s;
    cin >> n;
    while (n--)
    {
        cin >> id >> s >> seat;
        stu[s][0] = id;
        stu[s][1] = seat;
    }
    cin >> m;
    while (m--)
    {
        cin >> s;
        cout << stu[s][0] << " " << stu[s][1] << endl;
    }
    
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23

    1042 字符统计

    思路：
    字符串保存在 s 中，定义一个字符数组 c 统计所有小写字母出现的个数。统计时将大写字母与 A 或小写字母与 a 的 ASCII 码的差值作为下标。maxi 为数组最大值的下标，初始化为0。将其加上 a 再转换为字符类型即可打印成字符而不是整数。

    #include 
using namespace std;

int main()
{
    int c[26] = {0}, maxi = 0;
    string s;
    getline(cin, s);
    for (auto i : s)
    {
        if (isupper(i)) ++c[i - 'A'];
        if (islower(i)) ++c[i - 'a'];
    }
    for (int i = 0; i < 26; ++i)
        if (c[i] > c[maxi]) maxi = i;
    cout << char(maxi + 'a') << " " << c[maxi];

    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    1043 输出PATest

    思路：
    定义一个数组 hashTable，用于保存每个字符出现的个数。在循环中输出 PATest，每输出一个字符就将其个数减1。

    #include 
using namespace std;

int main()
{
    int hashTable[128] = {0}, c;
    while ((c = cin.get()) != EOF) ++hashTable[c];
    while (hashTable['P'] > 0 || hashTable['A'] > 0 || hashTable['T'] > 0
           || hashTable['e'] > 0 || hashTable['s'] > 0 || hashTable['t'] > 0)
    {
        if (hashTable['P']-- > 0) cout << 'P';
        if (hashTable['A']-- > 0) cout << 'A';
        if (hashTable['T']-- > 0) cout << 'T';
        if (hashTable['e']-- > 0) cout << 'e';
        if (hashTable['s']-- > 0) cout << 's';
        if (hashTable['t']-- > 0) cout << 't';
    }

    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    1044 火星数字

    思路：
    这一题的难点主要在于测试点2和4，需要从测试用例中观察。可以看到，如果输入的是 tam，转化的数是 13。反之，输入的是13，输出的就该是 tam 而不是 tam tret（不是“13 0”）。它与我们印象中十进制转二进制不一样（比如十进制数2的二进制是10），该题中十进制数13的倍数，转为十三进制的火星文是没有个位数的。比如 13 的火星文是 tam，26的火星文是 hel。

    关于进制转换的知识可参考：OJ 刷题必备知识总结（一） 20 进制转换。

    用两个 string 数组分别保存火星文的高位 tens 和低位 units（地球文最大数是168，所以火星文只有两位）。我的代码思路是先读取字符串，如果第一位是数字，表明字符串是地球文，先将其转为整数 m：

    • 如果 m 小于13，其火星文就只有一位，直接输出即可。
    • 如果 m 是13的倍数，这是特殊情况，火星文也只有一位。
    • 如果 m 大于13且不是13的倍数，其火星文有两位，对照输出即可。

    如果第一位是字母，表明字符串是火星文，先初始化其对应的阿拉伯数字的高位 high 和低位 low（比如 tam feb 的阿拉伯数字“1 2”、jou dec 的阿拉伯数字“12 12”）。由于火星文最多有两个单词，用 s1 保存第一个，s2 保存第二个。此时有三种情况：

    • 只有一个单词，且是低位单词，保存在 s1。
    • 只有一个单词，且是高位单词，保存在 s1。
    • 有两个单词，前面一个是高位，后面一个是低位，分别保存在 s1 和 s2。

    所以可以看到 s1 会出现两种情况，可能是低位也可能是高位，而 s2 如果非空则一定是低位单词。在遍历高低位数组的时候，第一个 if 判断的是低位单词，第二个 if 判断的是高位单词。所以第一个 if 有两个条件，第二个 if 只有一个条件。

    #include 
using namespace std;

int main()
{
    string units[] = {"tret", "jan", "feb", "mar", "apr", "may", "jun", "jly", "aug", "sep", "oct", "nov", "dec"};
    string tens[] = {"tret", "tam", "hel", "maa", "huh", "tou", "kes", "hei", "elo", "syy", "lok", "mer", "jou"};
    string s, s1, s2;
    int n, m, high, low;
    cin >> n;
    getchar();      // 这句必须写上，作用是过滤输入 n 后的回车
    while (n--)
    {
        getline(cin, s);
        if (isdigit(s[0]))  // 第一位是数字，则表明输入的是地球文
        {
            m = stoi(s);    // 将字符串转为整数保存在 m 中
            if (m < 13) cout << units[m] << endl;                       // m 小于13，输出一个低位单词
            else if (m % 13 == 0) cout << tens[m / 13] << endl;         // m是13的倍数，输出一个高位单词
            else cout << tens[m / 13] << " " << units[m % 13] << endl;  // 输出一个低位和一个高位
        }
        else
        {
            high = low = 0;     // 将高位和低位初始化
            s1 = s.substr(0, 3), s2 = "";           // s1 保存火星文的第一个单词
            if (s.size() > 3) s2 = s.substr(4, 7);  // s2 保存火星文的第二个单词
            for (int i = 0;  i < 13; ++i)           // 枚举两个数组的元素
            {
                if (units[i] == s1 || units[i] == s2) low = i;
                if (tens[i] == s1) high = i;
            }
            cout << high * 13 + low << endl;
        }
    }

    return 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

    希望本篇博客能对你有所帮助，也希望看官能动动小手点个赞哟~~。

  • 相关阅读:
    打工人准时下班踩点利器——python写一个自动关机程序并打包成exe文件
    JDK对String操作优化
    策略模式和模板模式
    git reset 三种形式
    ChatGPT：深度学习和机器学习的知识桥梁
    win10安全中心设置不扫描某个文件夹的方法
    微服务项目：尚融宝（20）（后端搭建：OSS文件上传整合）
    现代企业管理笔记——控制
    MYSQL 高可用集群搭建 ---MHA
    ArrayList 扩容源码浅析
  • 原文地址：https://blog.csdn.net/qq_37701948/article/details/127899882