【2022天梯赛暑期集训】第三次试题（vector,string,map,pair,set,unordered_map,unordered_set）

发表于

1-1 日期格式化

分数 5

全屏浏览题目

切换布局

作者 陈越

单位 浙江大学

世界上不同国家有不同的写日期的习惯。比如美国人习惯写成“月-日-年”，而中国人习惯写成“年-月-日”。下面请你写个程序，自动把读入的美国格式的日期改写成中国习惯的日期。

输入格式：

输入在一行中按照“mm-dd-yyyy”的格式给出月、日、年。题目保证给出的日期是1900年元旦至今合法的日期。

输出格式：

在一行中按照“yyyy-mm-dd”的格式给出年、月、日。

输入样例：

1
03-15-2017

输出样例：

1
2017-03-15
1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
using namespace std;

int main()
{
    string s;
    cin >> s;
    cout << s[6] << s[7] << s[8] << s[9] << '-';
    cout << s[0] << s[1] << '-';
    cout << s[3] << s[4] << endl;
    return 0;
}

1-2 比较大小

分数 10

全屏浏览题目

切换布局

作者 杨起帆

单位 浙大城市学院

本题要求将输入的任意3个整数从小到大输出。

输入格式:

输入在一行中给出3个整数，其间以空格分隔。

输出格式:

在一行中将3个整数从小到大输出，其间以“->”相连。

输入样例:

1
4 2 8

输出样例:

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

int main()
{
    int a, b, c;
    cin >> a >> b >> c;
    if(a > b) swap(a,b);
    if(b > c) swap(b,c);
    if(a > b) swap(a,b);
    cout << a << "->" << b << "->" << c << endl;
    return 0;
}

1-3 6翻了

分数 15

全屏浏览题目

切换布局

作者 陈越

单位 浙江大学

666.JPG

“666”是一种网络用语，大概是表示某人很厉害、我们很佩服的意思。最近又衍生出另一个数字“9”，意思是“6翻了”，实在太厉害的意思。如果你以为这就是厉害的最高境界，那就错啦 —— 目前的最高境界是数字“27”，因为这是 3 个 “9”！

本题就请你编写程序，将那些过时的、只会用一连串“6666……6”表达仰慕的句子，翻译成最新的高级表达。

输入格式：

输入在一行中给出一句话，即一个非空字符串，由不超过 1000 个英文字母、数字和空格组成，以回车结束。

输出格式：

从左到右扫描输入的句子：如果句子中有超过 3 个连续的 6，则将这串连续的 6 替换成 9；但如果有超过 9 个连续的 6，则将这串连续的 6 替换成 27。其他内容不受影响，原样输出。

输入样例：

1
it is so 666 really 6666 what else can I say 6666666666

输出样例：

1
it is so 666 really 9 what else can I say 27
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 <algorithm>
#include <cstring>
#include <iostream>
using namespace std;

int main() {
    string s;
    getline(cin, s);
    for (int i = 0; i < s.size(); i++) {
        bool flag = false;
        int cnt = 1;
        int j = i + 1;
        if (s[i] == '6') {
            while (s[j++] == '6') cnt++;
            if (cnt > 9) {
                flag = true;
                cout << "27";
            } else if (cnt > 3) {
                flag = true;
                cout << "9";
            }
        }
        if (flag) {
            i = j - 2;
            continue;
        }
        cout << s[i];
    }
    return 0;
}

1-4 考试座位号

分数 15

全屏浏览题目

切换布局

作者 陈越

单位 浙江大学

每个 PAT 考生在参加考试时都会被分配两个座位号，一个是试机座位，一个是考试座位。正常情况下，考生在入场时先得到试机座位号码，入座进入试机状态后，系统会显示该考生的考试座位号码，考试时考生需要换到考试座位就座。但有些考生迟到了，试机已经结束，他们只能拿着领到的试机座位号码求助于你，从后台查出他们的考试座位号码。

输入格式：

输入第一行给出一个正整数 N（≤1000），随后 N 行，每行给出一个考生的信息：准考证号 试机座位号 考试座位号。其中准考证号由 16 位数字组成，座位从 1 到 N 编号。输入保证每个人的准考证号都不同，并且任何时候都不会把两个人分配到同一个座位上。

考生信息之后，给出一个正整数 M（≤N），随后一行中给出 M 个待查询的试机座位号码，以空格分隔。

输出格式：

对应每个需要查询的试机座位号码，在一行中输出对应考生的准考证号和考试座位号码，中间用 1 个空格分隔。

输入样例：

1
2
3
4
5
6
7
4
3310120150912233 2 4
3310120150912119 4 1
3310120150912126 1 3
3310120150912002 3 2
2
3 4

输出样例：

1
2
3310120150912002 2
3310120150912119 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
#include <algorithm>
#include <cstring>
#include <iostream>
#include <map>
#define x first
#define y second
using namespace std;
// 准考证 考试座位号
typedef pair<string, string> PII;
// 座位号
map<int, PII> m;

int main() {
    int N;
    cin >> N;
    while (N--) {
        string a, c;
        int b;
        cin >> a >> b >> c;
        m[b] = {a, c};
    }
    int M;
    cin >> M;
    while (M--) {
        int a;
        cin >> a;
        cout << m[a].x << " " << m[a].y << endl;
    }
    return 0;
}

1-5 天梯赛的善良

分数 20

全屏浏览题目

切换布局

作者 陈越

单位 浙江大学

天梯赛是个善良的比赛。善良的命题组希望将题目难度控制在一个范围内，使得每个参赛的学生都有能做出来的题目，并且最厉害的学生也要非常努力才有可能得到高分。

于是命题组首先将编程能力划分成了 106 个等级（太疯狂了，这是假的），然后调查了每个参赛学生的编程能力。现在请你写个程序找出所有参赛学生的最小和最大能力值，给命题组作为出题的参考。

输入格式：

输入在第一行中给出一个正整数 N（≤2×104），即参赛学生的总数。随后一行给出 N 个不超过 106 的正整数，是参赛学生的能力值。

输出格式：

第一行输出所有参赛学生的最小能力值，以及具有这个能力值的学生人数。第二行输出所有参赛学生的最大能力值，以及具有这个能力值的学生人数。同行数字间以 1 个空格分隔，行首尾不得有多余空格。

输入样例：

1
2
10
86 75 233 888 666 75 886 888 75 666

输出样例：

1
2
75 3
888 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <algorithm>
#include <cstring>
#include <iostream>
#include <map>
#define x first
#define y second
using namespace std;

map<int, int> m;

int main() {
    int N;
    cin >> N;
    while (N--) {
        int t;
        cin >> t;
        m[t]++;
    }
    cout << m.begin()->x << ' ' << m.begin()->y << endl;
    cout << m.rbegin()->x << ' ' << m.rbegin()->y << endl;
    return 0;
}

1-6 机工士姆斯塔迪奥

分数 20

全屏浏览题目

切换布局

作者 DAI, Longao

单位 杭州百腾教育科技有限公司

在 MMORPG《最终幻想14》的副本“乐欲之所瓯博讷修道院”里，BOSS 机工士姆斯塔迪奥将会接受玩家的挑战。

你需要处理这个副本其中的一个机制：N×M 大小的地图被拆分为了 N×M 个 1×1 的格子，BOSS 会选择若干行或/及若干列释放技能，玩家不能站在释放技能的方格上，否则就会被击中而失败。

给定 BOSS 所有释放技能的行或列信息，请你计算出最后有多少个格子是安全的。

输入格式:

输入第一行是三个整数 N,M,Q (1≤N×M≤105，0≤Q≤1000)，表示地图为 N 行 M 列大小以及选择的行/列数量。

接下来 Q 行，每行两个数 Ti​,Ci​，其中 Ti​=0 表示 BOSS 选择的是一整行，Ti​=1 表示选择的是一整列，Ci​ 为选择的行号/列号。行和列的编号均从 1 开始。

输出格式:

输出一个数，表示安全格子的数量。

输入样例:

1
2
3
4
5 5 3
0 2
0 4
1 3

输出样例:

1
12
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 <algorithm>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#define x first
#define y second
using namespace std;

int n, m, q;
set<int> r, c;
int main() {
    cin >> n >> m >> q;
    int T, C;
    while (q--) {
        cin >> T >> C;
        if (T == 0) {
            r.insert(C);
        } else {
            c.insert(C);
        }
    }
    cout << (n - r.size()) * (m - c.size()) << endl;
    return 0;
}

1-7 估值一亿的AI核心代码

分数 20

全屏浏览题目

切换布局

作者 陈越

单位 浙江大学

AI.jpg

以上图片来自新浪微博。

本题要求你实现一个稍微更值钱一点的 AI 英文问答程序，规则是：

  • 无论用户说什么，首先把对方说的话在一行中原样打印出来；
  • 消除原文中多余空格：把相邻单词间的多个空格换成 1 个空格，把行首尾的空格全部删掉，把标点符号前面的空格删掉；
  • 把原文中所有大写英文字母变成小写，除了 I；
  • 把原文中所有独立的 can you、could you 对应地换成 I can、I could—— 这里“独立”是指被空格或标点符号分隔开的单词；
  • 把原文中所有独立的 I 和 me 换成 you；
  • 把原文中所有的问号 ? 换成惊叹号 !；
  • 在一行中输出替换后的句子作为 AI 的回答。

输入格式：

输入首先在第一行给出不超过 10 的正整数 N，随后 N 行，每行给出一句不超过 1000 个字符的、以回车结尾的用户的对话，对话为非空字符串，仅包括字母、数字、空格、可见的半角标点符号。

输出格式：

按题面要求输出，每个 AI 的回答前要加上 AI: 和一个空格。

输入样例：

1
2
3
4
5
6
7
6
Hello ?
 Good to chat   with you
can   you speak Chinese?
Really?
Could you show me 5
What Is this prime? I,don 't know

输出样例：

1
2
3
4
5
6
7
8
9
10
11
12
Hello ?
AI: hello!
 Good to chat   with you
AI: good to chat with you
can   you speak Chinese?
AI: I can speak chinese!
Really?
AI: really!
Could you show me 5
AI: I could show you 5
What Is this prime? I,don 't know
AI: what Is this prime! you,don't know
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
#include <algorithm>
#include <cstring>
#include <iostream>

using namespace std;

int main() {
    int n;
    cin >> n;
    string s;
    getline(cin, s);
    while (n--) {
        string s;
        getline(cin, s);

        // 无论用户说什么，首先把对方说的话在一行中原样打印出来；
        cout << s << endl;

        // 把行首尾的空格全部删掉
        // s.erase(1);  删除集合s中的1这个元素
        // s.erase(s.begin()); 删除集合s中的第一个元素
        // s.erase(s.end() - 1); 删除集合s中的最后一个元素
        while (s[0] == ' ') s.erase(s.begin());
        while (s[s.size() - 1] == ' ') s.erase(s.end() - 1);
        // 把相邻单词间的多个空格换成 1 个空格，把标点符号前面的空格删掉；
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == ' ') {
                while (s[i + 1] == ' ') s.erase(s.begin() + i + 1);
                // isalnum() 函数用于检测字符串是否只包含字母和数字。
                // !isalnum() 检测是否是空格和标点符号。
                if (!isalnum(s[i + 1])) s.erase(s.begin() + i);
            }
        }

        // 把原文中所有大写英文字母变成小写，除了 I；
        for (int i = 0; i < s.size(); i++)
            // isupper() 函数检测是否是大写字母。
            if (isupper(s[i]) && s[i] != 'I')
                s[i] = tolower(s[i]);  // tolower() 函数用于把字符转换为小写。

        // 把原文中所有独立的 can you、could you 对应地换成 I can、I could——
        // 这里“独立”是指被空格或标点符号分隔开的单词；
        for (int beg = 0;; beg++) {
            beg = s.find("can you", beg);
            if (beg == -1) break;
            if ((beg == 0 || !isalnum(s[beg - 1])) &&
                (beg + 7 == s.size() || !isalnum(s[beg + 7]))) {
                s.replace(beg, 7, "A can");
            }
        }
        // 由于后面还要处理'I'这里先用'A'代替'I'，最后在变成'I'
        for (int beg = 0;; beg++) {
            beg = s.find("could you", beg);
            if (beg == -1) break;
            if ((beg == 0 || !isalnum(s[beg - 1])) &&
                (beg + 9 == s.size() || !isalnum(s[beg + 9]))) {
                s.replace(beg, 9, "A could");
            }
        }
        // 把原文中所有独立的 I 和 me 换成 you；
        for (int beg = 0;; beg++) {
            beg = s.find("I", beg);
            if (beg == -1) break;
            if ((beg == 0 || !isalnum(s[beg - 1])) &&
                (beg + 1 == s.size() || !isalnum(s[beg + 1]))) {
                s.replace(beg, 1, "you");
            }
        }
        for (int beg = 0;; beg++) {
            beg = s.find("me", beg);
            if (beg == -1) break;
            if ((beg == 0 || !isalnum(s[beg - 1])) &&
                (beg + 2 == s.size() || !isalnum(s[beg + 2]))) {
                s.replace(beg, 2, "you");
            }
        }

        // 把原文中所有的问号 ? 换成惊叹号 !；
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '?') s[i] = '!';
            if (s[i] == 'A') s[i] = 'I';
        }

        // 在一行中输出替换后的句子作为 AI 的回答。
        cout << "AI: " << s << endl;
    }
    return 0;
}