第十一届蓝桥杯大赛软件类决赛

题目在这里

部分自己写的，大部分学习好友therainisme

试题 A: 美丽的 2

1
2
3
4
5
6
7
8
9
10
11
# 暴力求解
count = 0
for i in range(1, 2021):
    temp = i
    while temp != 0:
        if temp % 10 == 2:
            count += 1
            break
        # 记得这里要取整
        temp = int(temp/10)
print(count)

答案：563

试题 B: 扩散

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
#include <bits/stdc++.h>
// 这题宽搜
using namespace std;
// 获取数对时偷懒
#define x first
#define y second
// 记录坐标
typedef pair<int, int> PII;
// 整个图的存储和偏执，避免出现负数索引
const int N = 10000, D = 4000;
// 创建图
int g[N][N];
// 四个方向
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
// 最后的结果
int res = 4;

void bfs()
{
    // 先标记已经用过的点
    g[0 + D][0 + D] = g[2020 + D][11 + D] = g[11 + D][14 + D] = g[2000 + D][2000 + D] = 1;
    // 初始化时间和当前在队列中的点数
    int minutes = 0;
    int times = 4;
    // 创建队列
    queue<PII> q;
    q.push({0 + D, 0 + D});
    q.push({2020 + D, 11 + D});
    q.push({11 + D, 14 + D});
    q.push({2000 + D, 2000 + D});
    // 如果栈不为空就继续染色
    while (q.size())
    {
        // 本次染色起始点的个数
        int now = times;
        times = 0;
        // 开始遍历这些点
        for (int i = 0; i < now; i++)
        {
            // 出队
            PII ing = q.front();
            q.pop();
            // 遍历四个方向
            for (int j = 0; j < 4; j++)
            {
                int nx = ing.x + dx[j], ny = ing.y + dy[j];
                // 没有被用过就+1
                if (g[nx][ny] == 0)
                {
                    g[nx][ny] = 1;
                    times++;
                    res++;
                    // 重新入队
                    q.push({nx, ny});
                }
            }
        }
        // 循环一次就过一分钟
        minutes++;
        // 到点就结束
        if (minutes == 2020)
            break;
    }
}

int main()
{
    bfs();
    cout << res << endl;
}

答案：20312088

试题 C: 阶乘约数

解题思路

约数个数可以转化成每个类型的质因数的不同指数乘积的形式

求解约数的个数就可以看作，第一个质因数有b1+1（还有指数为0的情况）种选择,第二个有b2+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
#include <bits/stdc++.h>
using namespace std;
//求1~100的质因数，然后每个质因数的乘积+1
map<int, int> zhi;
map<int, int>::iterator it;
long long res = 1;

// 求解质因数
void getzhi(int x)
{
    for (int i = 2; i * i <= x; i++)
    {
        if (x % i == 0)
            while (x % i == 0)
            {
                zhi[i]++;
                x /= i;
            }
    }
    if (x > 1)
        zhi[x]++;
}

int main()
{
    // 获取每个约数的u质因数
    for (int i = 1; i <= 100; i++)
    {
        getzhi(i);
    }
    // 将质因数的个数+1乘起来就是结果了
    for (it = zhi.begin(); it != zhi.end(); it++)
    {
        res *= (it->second + 1);
    }
    cout << res << endl;
    return 0;
}

答案：39001250856960000

试题 D: 本质上升序列

不太懂

代码：

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
#include <bits/stdc++.h>
using namespace std;
string s = "tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhfiadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqijgihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmadvrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl";
int len = s.length();
// dp表示第i个字符的本质上升字序列个数
int dp[210];
long long res;
int main()
{
    // 单个字符就算一个
    for (int i = 0; i < len; i++)
    {
        dp[i] = 1;
    }
    // 遍历吧！
    for (int i = 0; i < len; i++)
    {
        for (int j = 0; j < i; j++)
        {
            // 如果第i个字母>第j个字母，就可以有dp[j]中方法，加上本身有的方法
            if (s[i] > s[j])
                dp[i] += dp[j];
            // 如果第i个字母=第j个字母，说明如果前dp[j]中方法已经有过了，所以需要减去
            if (s[i] == s[j])
                dp[i] -= dp[j];
        }
    }
    // 所有字母的组合加起来
    for (int i = 0; i < len; i++)
        res += dp[i];
    cout << res << endl;
    return 0;
}

答案：3616159

试题E：玩具蛇

思路

遍历蛇头的位置，然后开始深搜，对当前位置向四个方向拓展，注意不能超界，不能拓展已经拓展过的地方，然后每拓展一次就让长度+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
40
#include <bits/stdc++.h>
using namespace std;
int g[4][4];
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int res;
void dfs(int x, int y, int len)
{
    // 达到蛇长度
    if (len == 16)
    {
        res++;
        return;
    }
    // 当前点向四个方向拓展
    for (int i = 0; i < 4; i++)
    {
        int nx = x + dx[i], ny = dy[i] + y;
        if (nx >= 0 && ny >= 0 && nx < 4 && ny < 4 && !g[nx][ny])
        {
            g[nx][ny] = 1;
            dfs(nx, ny, len + 1);
            g[nx][ny] = 0;
        }
    }
}
int main()
{
    // 遍历蛇头的位置
    for (int i = 0; i < 4; i++)
    {
        for (int j = 0; j < 4; j++)
        {
            g[i][j] = 1;
            dfs(i, j, 1);
            g[i][j] = 0;
        }
    }
    cout << res << endl;
    return 0;
}

答案：552