1004 成绩排名 (20分)

题目

读入 n（>0）名学生的姓名、学号、成绩，分别输出成绩最高和成绩最低学生的姓名和学号。

输入格式：

每个测试输入包含 1 个测试用例，格式为

1
2
3
4
5

第 1 行：正整数 n
第 2 行：第 1 个学生的姓名 学号 成绩
第 3 行：第 2 个学生的姓名 学号 成绩
  ... ... ...
第 n+1 行：第 n 个学生的姓名 学号 成绩

其中姓名和学号均为不超过 10 个字符的字符串，成绩为 0 到 100 之间的一个整数，这里保证在一组测试用例中没有两个学生的成绩是相同的。

输出格式：

对每个测试用例输出 2 行，第 1 行是成绩最高学生的姓名和学号，第 2 行是成绩最低学生的姓名和学号，字符串间有 1 空格。

输入样例：

3

Joe Math990112 89

Mike CS991301 100

Mary EE990830 95

输出样例：

Mike CS991301

Joe Math990112

思路分析

此题考查对对输入输出流的把握能力

对于不属于同一数据类型的变量使用结构体把控

即 max min tem 3项

注意题干，无相同成绩

注意第一层循环就要用tem 替换 max min 保证不为空

举一反三

std 的 cin 只会读到下一个空格或是换行符 $，如果需要一次读一行需要使用 getline() 函数

代码

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

#include <iostream>

using namespace std;

struct student {
    string name, id;
    int score;
};

int main() {
    student tem;
    student max{"", "", 0};
    student min{"", "", 100};
    int n;
    cin >> n;
    while (n--) {
        cin >> tem.name >> tem.id >> tem.score;
        max = tem.score > max.score ? tem : max;
        min = tem.score < min.score ? tem : min;
    }
    cout << max.name << " " << max.id << "\n";
    cout << min.name << " " << min.id << endl;

    return 0;
}

1003 我要通过！

题目

“答案正确” 是自动判题系统给出的最令人欢喜的回复。本题属于 PAT 的“答案正确”大派送 —— 只要读入的字符串满足下列条件，系统就输出“答案正确”，否则输出“答案错误”。

得到“答案正确”的条件是：

1. 字符串中必须仅有 P、 A、 T这三种字符，不可以包含其它字符；

2. 任意形如 xPATx 的字符串都可以获得“答案正确”，其中 x 或者是空字符串，或者是仅由字母 A 组成的字符串；

3. 如果 aPbTc 是正确的，那么 aPbATca 也是正确的，其中 a、 b、 c 均或者是空字符串，或者是仅由字母 A 组成的字符串。

现在就请你为 PAT 写一个自动裁判程序，判定哪些字符串是可以获得“答案正确”的。

输入格式：

每个测试输入包含 1 个测试用例。第 1 行给出一个正整数 n (<10)，是需要检测的字符串个数。接下来每个字符串占一行，字符串长度不超过 100，且不包含空格。

输出格式：

每个字符串的检测结果占一行，如果该字符串可以获得“答案正确”，则输出 YES，否则输出 NO。

输入样例：

8

PAT

PAAT

AAPATAA

AAPAATAAAA

xPATx

PT

Whatever

APAAATAA

输出样例：

YES

YES

YES

YES

NO

NO

NO

NO

思路分析

这题我想复杂了，看到条件二 xPATx 不自觉想到正则表达式的反向引用，但是条件三用正则比较复杂，虽然此题 AC 了，但是做的实在是很不漂亮，以后有时间还得重新研究一下。

条件1，2都非常简单

条件3要难点在于条件是递归式的，简单计算易得， a * b = c

c++ 应该使用 “.” 保证转义，如 .1

正则搜索迭代器 regex_search() 注意不能用 “A*” 等无底线要求，会无限迭代

最后输出注意空行 \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

#include <iostream>
#include <regex>
/*注意事项：
 * 条件1，2都非常简单
 * 条件3要难点在于条件是递归式的，简单计算易得， a * b = c
 * c++ 应该使用 "\\" 保证转义，如 "\\1"
 * 正则迭代器注意不能用 "A*" 等无底线要求，会无限迭代
 * 最后输出注意空行 "\n"
 * */
using namespace std;

int num = 0;
string str;
regex regex_1("[P|A|T]+");//满足条件一
regex regex_2("(A*)PAT\\1");//满足条件二直接输出
regex regex_3("A*PA+TA*");//条件三的大前提
regex regex_4("A+");//找到 A 的数量

bool checkString(string str) {
    int i = 0;
    bool r1, r2, r3, r4;
    smatch result;
    string temp[3];
    string::const_iterator iterStart = str.begin();
    string::const_iterator iterEnd = str.end();

    r1 = regex_match(str, regex_1);
    r2 = regex_match(str, regex_2);
    r3 = regex_match(str, regex_3);


    //使用迭代器，将正则匹配到的结果存在 temp[] 里
    while (regex_search(iterStart, iterEnd, result, regex_4)) {
        temp[i++] = result[0];
        iterStart = result[0].second;
    }

    //满足 a * b = c
    r4 = ((temp[0].size() * temp[1].size() == temp[2].size()));

    //r1 必须满足，r2 或 r3 && r4 满足即可
    if (r1 && (r2 || (r3 && r4))) {
        return true;
    } else return false;
}

int main() {
    cin >> num;
    string arr[num];
    for (int i = 0; i < num; i++) {
        cin >> str;
        if (checkString(str)) {
            arr[i] = "YES";
        } else arr[i] = "NO";
    }
    for (int i = 0; i < num; i++) {
        cout << arr[i] << "\n";
    }

    return 0;
}

1002 写出这个数 (20分)

题目

读入一个正整数 n，计算其各位数字之和，用汉语拼音写出和的每一位数字。

输入格式：

每个测试输入包含 1 个测试用例，即给出自然数 n 的值。这里保证 n 小于 10^100

输出格式：

在一行内输出 n 的各位数字之和的每一位，拼音数字间有 1 空格，但一行中最后一个拼音数字后没有空格。

输入样例：

1234567890987654321123456789

输出样例：

yi san wu

思路分析

考察的重点其实是 string char 和 int 来回转换

读取求和即可，注意末位没有空格

举一反三

一个利用 ASCII 取巧的方法：

本质上是各字符编码的号的距离

想从char 获得int，使用-'0'

如 1 = '1'-'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

#include <iostream>

using namespace std;

int main() {
    string input;
    int sum = 0;
    string arr[10] = {
            "ling", "yi", "er", "san", "si", "wu", "liu", "qi", "ba", "jiu"
    };

    cin >> input;
    for (int i = 0; i < input.size(); i++) {
        sum += input[i] - '0';
    }

    string res = to_string(sum);

    for (int i = 0; i < res.size(); i++) {
        // If reach the end, cout end
        if (i == res.size() - 1) {
            cout << arr[res[i] - '0'];
            cout << endl;
        }
            // else print number and space
        else {
            cout << arr[res[i] - '0'];
            cout << " ";

        }
    }
}

算法复杂度：$S(n)$ 与 $T(n)$

复杂度的观察应该是宏观的，不用纠结于每行代码运行时的消耗，而是从另一个高度把握。

空间复杂度 $S(n)$

我们做一个简单的规定：$S(n)$ 为算法的空间复杂度，观察程序执行时占用储存单元的长度。n 即为数据的规模，显然复杂度过高会吃爆内存造成程序中断。

现代计算机 pc 内存多以 GB 为单位，程序的空间占用不是这么紧缺。换言之，空间复杂度为一般程序次要的考察因素。

嵌入式开发，大型服务器运维，仍需要考虑空间分配。

时间复杂度 $T(n)$

$T(n)$ 关注的是程序的运行时间与数据规模 n 的 关系，无论时代如何发展，只要人们不能减速时间，时间消耗就还是最重要的程序消耗，当然，计算机的发展会加快计算速度，并提升 cpu 带宽，但是与如今程序规模的发展相比，仍是杯水车薪。大量并发，亿万级大数据已成主流，时间就是金钱。

所以，对程序时间消耗有更强的掌控力已经是程序员的必修课。

最小上界 $O(n)$

关于上下界的严格数学证明不再赘述

引入 $O(n)$ 作为对程序时间复杂度的粗略上界估计，$O(n)$ 为最小上界

算法的渐进表示

1. 算法加和，考虑更慢的一边
2. 算法的嵌套，复杂度做乘法
3. $T(n)$ 是 n 的 k 阶多项式，$T(n)=\Theta(n^k)$
4. for 循环嵌套，$T(n)$ 为各层循环次数的积再乘以循环体复杂度
5. if-else 结构考虑条件，两个分支，三者中最慢的一个。

首先做一个小小的假设

我们假设有一台运行速度足够快，内存足够大的电脑（突破普朗克常量物理极限，达到数学层面的无限），快到可以瞬间做完任何任务，大到可以塞下任何程序栈，那么我们从此似乎不再需要继续钻研数据结构和算法了，暴力求解，暴力递归就是一切，显然，这样的电脑是不存在的。

举这个例子就是想说明：数据结构和算法问题必须放在具体时空条件下，具体情况具体分析，所以我们爱用优化这个词，我们倾向于用更少的空间，更少的时间，做更多的计算，理论上软件优化是有极限的，因为总要给磁盘，内存，cpu 物理工作的时间。

我们碰到的问题无非是在受限的时空条件下，完成目标的计算任务，或是基于源程序做定向优化。

那么总得有个标准吧

定标准看起来是一件比较容易的事：

时间嘛，看程序运行多少毫秒就完事了，快就是好。

空间嘛，看占了多少 bit，少就是好。

似乎很有道理，仔细琢磨一下有这样一个问题：

程序 A 在数据量比较小的情况下时空消耗都还好，感觉数据量增大了也不多，消耗却像细胞分裂一样吃掉了远远高于预期的资源，慢慢尝试后我们会发现，隐隐约约消耗与数据量有着函数关系式的对应，或是线性，或是呈指数。

于是为了抛弃上面那种粗略量化的糟粕，我们有了更精确的定性定量的工具。

引入一个数学工具来帮助我们

离散数学讨论了这样一个问题：$y=x$ 和 $y=x^2$，当 x 越来越大时，谁增长的更快呢？

显然是 $x ^ 2$，那么当我们研究一个 $y = 2x + 3x ^ 2$，这样的问题时，是不是可以忽略 $2x$ 这项的消耗呢？

举个简单的例子，小胖和小美一起吃饭，当两人吃的时间足够长，东西足够多的时候，我们是不是可以断言，伙食费里面的绝大部分都是小胖吃的？

所以一个很聪明的办法是在更大的损耗面前，忽略那些不这么重要的消耗。

而算法导论等著作中，关于时空消耗有着非常清晰且规整的介绍!