第十一届蓝桥杯大赛软件类决赛C/C++大学B组部分题解_7-7 压缩字符串分数 10全屏浏览题目切换布局作者 zhu weihua单位 新余学院实现一

试题 A: 美丽的 2

【问题描述】

小蓝特别喜欢 2，今年是公元 2020 年，他特别高兴。
他很好奇，在公元 1 年到公元 2020 年（包含）中，有多少个年份的数位中包含数字 2？
1
2

答案： 563

试题 B: 扩散

【问题描述】

小蓝在一张无限大的特殊画布上作画。
这张画布可以看成一个方格图，每个格子可以用一个二维的整数坐标表示。
小蓝在画布上首先点了一下几个点：(0, 0), (2020, 11), (11, 14), (2000, 2000)。
只有这几个格子上有黑色，其它位置都是白色的。
每过一分钟，黑色就会扩散一点。具体的，如果一个格子里面是黑色，它
就会扩散到上、下、左、右四个相邻的格子中，使得这四个格子也变成黑色
（如果原来就是黑色，则还是黑色）。
请问，经过 2020 分钟后，画布上有多少个格子是黑色的。
1
2
3
4
5
6
7
8

很简单的一个BFS题，注意染色可以至负数坐标，因此可预先+2500防止数组越界。

代码如下：

#include <bits/stdc++.h>
using namespace std;

bool mp[8000][8000];
struct node
{
    int x, y, step;
};
queue<node> q;

int sum = 2020;
int mov[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
void bfs()
{
    mp[0 + 2500][0 + 2500] = 1;
    mp[2020 + 2500][11 + 2500] = 1;
    mp[11 + 2500][14 + 2500] = 1;
    mp[2000 + 2500][2000 + 2500] = 1;
    q.push(node{0 + 2500, 0 + 2500, 0});
    q.push(node{2020 + 2500, 11 + 2500, 0});
    q.push(node{11 + 2500, 14 + 2500, 0});
    q.push(node{2000 + 2500, 2000 + 2500, 0});
    while (q.size())
    {
        node temp = q.front();
        q.pop();
        if (temp.step == sum)
            continue;
        for (int i = 0; i < 4; i++)
        {
            int xx = temp.x + mov[i][0];
            int yy = temp.y + mov[i][1];
            if (!mp[xx][yy])
            {
                mp[xx][yy] = 1;
                q.push(node{xx, yy, temp.step + 1});
            }
        }
    }
}
int main()
{
    bfs();
    int ans = 0;
    for (int i = 1; i < 8000; i++)
        for (int j = 1; j < 8000; j++)
            ans += mp[i][j];
    cout << ans << 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

答案： 20312088

试题 C: 阶乘约数

【问题描述】

定义阶乘 n! = 1 × 2 × 3 × · · · × n。
请问 100! （100 的阶乘）有多少个约数。
1
2

百度百科 唯一分解定理

代码如下：

#include <bits/stdc++.h>
using namespace std;

map<int, int> mp;
void get(int x)
{
    for (int i = 2; i * i <= x; i++)
    {
        if (x % i == 0)
        {
            while (x % i == 0)
            {
                x /= i;
                mp[i]++;
            }
        }
    }
    if (x > 1)
        mp[x]++;
}
int main()
{
    for (int i = 2; i <= 100; i++)
        get(i);
    long long ans = 1;
    for (map<int, int>::iterator pt = mp.begin(); pt != mp.end(); pt++)
        ans *= (long long)((pt->second) + 1);
    cout << ans << 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

答案： 39001250856960000

试题 D: 本质上升序列

【问题描述】

小蓝特别喜欢单调递增的事物。
在一个字符串中，如果取出若干个字符，将这些字符按照在字符串中的顺
序排列后是单调递增的，则成为这个字符串中的一个单调递增子序列。
例如，在字符串 lanqiao 中，如果取出字符 n 和 q，则 nq 组成一个单
调递增子序列。类似的单调递增子序列还有 lnq、i、ano 等等。
小蓝发现，有些子序列虽然位置不同，但是字符序列是一样的，例如取第
二个字符和最后一个字符可以取到 ao，取最后两个字符也可以取到 ao。小蓝
认为他们并没有本质不同。
对于一个字符串，小蓝想知道，本质不同的递增子序列有多少个？
例如，对于字符串 lanqiao，本质不同的递增子序列有 21 个。它们分别
是 l、a、n、q、i、o、ln、an、lq、aq、nq、ai、lo、ao、no、io、lnq、
anq、lno、ano、aio。
请问对于以下字符串（共 200 个小写英文字母，分四行显示）：（如果你把
以下文字复制到文本文件中，请务必检查复制的内容是否与文档中的一致。在
试题目录下有一个文件 inc.txt，内容与下面的文本相同）
tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhf
iadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqij
gihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmad
vrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl
本质不同的递增子序列有多少个？
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

代码如下：

#include <bits/stdc++.h>
using namespace std;

int dp[1000][30];
int main()
{
    char s[210];
    scanf("%s", s + 1);
    int len = strlen(s + 1);
    for (int i = 1; i <= len; i++)
        dp[i][s[i] - 'a' + 1] = 1;
    for (int i = 1; i <= len; i++)
    {
        int now = s[i] - 'a' + 1;
        for (int j = 1; j < now; j++) //转移方程
            dp[i][now] += dp[i - 1][j];
        for (int j = 1; j <= 26; j++)
            dp[i][j] = max(dp[i][j], dp[i - 1][j]);
    }
    int ans = 0;
    for (int i = 1; i <= 26; i++)
        ans += dp[len][i];
    cout << ans << endl;
    return 0;
}
/*
tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhfiadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqijgihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmadvrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl
*/
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

答案： 3616159

试题 E: 玩具蛇

【问题描述】

小蓝有一条玩具蛇，一共有 16 节，上面标着数字 1 至 16。每一节都是一
个正方形的形状。相邻的两节可以成直线或者成 90 度角。
小蓝还有一个 4 × 4 的方格盒子，用于存放玩具蛇，盒子的方格上依次标着
字母 A 到 P 共 16 个字母。
小蓝可以折叠自己的玩具蛇放到盒子里面。他发现，有很多种方案可以将
玩具蛇放进去。
请帮小蓝计算一下，总共有多少种不同的方案。如果两个方案中，存在玩
具蛇的某一节放在了盒子的不同格子里，则认为是不同的方案。
1
2
3
4
5
6
7
8

下图给出了两种方案：

答案： 3616159

代码如下：

#include <bits/stdc++.h>
using namespace std;

int vis[10][10];
int mov[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
int res;
void dfs(int x, int y, int step)
{
    if (step == 16)
    {
        res++;
        return;
    }
    for (int i = 0; i < 4; i++)
    {
        int xx = x + mov[i][0];
        int yy = y + mov[i][1];
        if (xx >= 1 && xx <= 4 && yy >= 1 && yy <= 4 && !vis[xx][yy])
        {
            vis[xx][yy] = 1;
            dfs(xx, yy, step + 1);
            vis[xx][yy] = 0;
        }
    }
}

int main()
{
    int ans = 0;
    for (int i = 1; i <= 4; i++)
        for (int j = 1; j <= 4; j++)
        {
            res = 0;
            vis[i][j] = 1;
            dfs(i, j, 1);
            vis[i][j] = 0;
            ans += res;
        }
    cout << ans << 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

答案： 552

试题 G: 游园安排

【问题描述】

L 星球游乐园非常有趣，吸引着各个星球的游客前来游玩。小蓝是 L 星球
游乐园的管理员。
为了更好的管理游乐园，游乐园要求所有的游客提前预约，小蓝能看到系
统上所有预约游客的名字。每个游客的名字由一个大写英文字母开始，后面跟
0 个或多个小写英文字母。游客可能重名。
小蓝特别喜欢递增的事物。今天，他决定在所有预约的游客中，选择一部
分游客在上午游玩，其他的游客都在下午游玩，在上午游玩的游客要求按照预
约的顺序排列后，名字是单调递增的，即排在前面的名字严格小于排在后面的
名字。
一个名字 A 小于另一个名字 B 是指：存在一个整数 i，使得 A 的前 i 个字
母与 B 的前 i 个字母相同，且 A 的第 i+ 1 个字母小于 B 的第 i+ 1 个字母。（如
果 A 不存在第 i + 1 个字母且 B 存在第 i + 1 个字母，也视为 A 的第 i + 1 个字
母小于 B 的第 i + 1 个字母）
作为小蓝的助手，你要按照小蓝的想法安排游客，同时你又希望上午有尽
量多的游客游玩，请告诉小蓝让哪些游客上午游玩。如果方案有多种，请输出
上午游玩的第一个游客名字最小的方案。如果此时还有多种方案，请输出第一
个游客名字最小的前提下第二个游客名字最小的方案。如果仍然有多种，依此
类推选择第三个、第四个……游客名字最小的方案。
【输入格式】
输入包含一个字符串，按预约的顺序给出所有游客的名字，相邻的游客名
字之间没有字符分隔。
【输出格式】
按预约顺序输出上午游玩的游客名单，中间不加任何分隔字符。
【样例输入】
WoAiLanQiaoBei
【样例输出】
AiLanQiao
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

将名字离散化为数字，nlogn求最长上升子序列，最后回溯最小字典序。

（不会回溯最小字典序的解，待补。

试题 H: 答疑

【问题描述】

有 n 位同学同时找老师答疑。每位同学都预先估计了自己答疑的时间。
老师可以安排答疑的顺序，同学们要依次进入老师办公室答疑。
一位同学答疑的过程如下：
1. 首先进入办公室，编号为 i 的同学需要 si 毫秒的时间。
2. 然后同学问问题老师解答，编号为 i 的同学需要 ai 毫秒的时间。
3. 答疑完成后，同学很高兴，会在课程群里面发一条消息，需要的时间可
以忽略。
4. 最后同学收拾东西离开办公室，需要 ei 毫秒的时间。一般需要 10 秒、
20 秒或 30 秒，即 ei 取值为 10000，20000 或 30000。
一位同学离开办公室后，紧接着下一位同学就可以进入办公室了。
答疑从 0 时刻开始。老师想合理的安排答疑的顺序，使得同学们在课程群
里面发消息的时刻之和最小。
【输入格式】
输入第一行包含一个整数 n，表示同学的数量。
接下来 n 行，描述每位同学的时间。其中第 i 行包含三个整数 si, ai, ei，意
义如上所述。
【输出格式】
输出一个整数，表示同学们在课程群里面发消息的时刻之和最小是多少。
【样例输入】
3
10000 10000 10000
试题H: 答疑 12
第十一届蓝桥杯大赛软件类决赛 C/C++ 大学 B 组
20000 50000 20000
30000 20000 30000
【样例输出】
280000
【样例说明】
按照 1, 3, 2 的顺序答疑，发消息的时间分别是 20000, 80000, 180000。

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

贪心，按照si+ai+ei从小到大排序，如果si+ai+ei相等，再按si+ai排序。