第十二届蓝桥杯题解

注释：这段时间正好在写蓝桥杯的题，将部分的题目的解法和大家分享，代码中的网址是该代码蒟蒻当时参考其他大佬的题解文章所在的网址，鸣谢大佬，如有错误，欢迎各位大佬指正
有部分网址是提交答案的oj传送门

A 卡片

暴力枚举即可，注意小错误

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
#include <bits/stdc++.h>
using namespace std;
// https://www.lanqiao.cn/courses/2786/learning/?id=280825
// 3181
int a[9];
bool judge(int n)
{
    while (n)
    {
        int remp = n % 10;
        if (a[remp] == 0)
            return false;
        a[remp]--;
        n /= 10;
    }
    return true;
}
int main()
{
    for (int i = 0; i <= 9; i++)
    {
        a[i] = 2021;
    }
    int num = 0;
    while (judge(num+1))
    {
        num++;
    }
    cout<<num;
    return 0;
}

B 直线

这道题想了很久，没有想到特别好的办法，只能暴力枚举。
注意当斜率不存在时要单独讨论，最后加上，否则会出bug

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
#include <bits/stdc++.h>
using namespace std;
// https://blog.csdn.net/qq_36306833/article/details/121872050
struct node
{
    double x;
    double y;
} point[1000000];
long long num = 0;
long long ans = 0;
map<pair<double, double>, bool> visit;
void judge(node p1, node p2)
{
    double x1 = p1.x, x2 = p2.x;
    double y1 = p1.y, y2 = p2.y;
    if (x1 == x2)
        return;
    double k = (y2 - y1) / (x2 - x1);
    double b = (x2 * y1 - y2 * x1) / (x2 - x1);
    if (!visit[{k, b}])
    {
        visit[{k, b}] = 1;
        ans++;
    }
}
int main()
{
    for (int i = 0; i < 20; i++)
        for (int j = 0; j < 21; j++)
        {
            point[++num].x = i;
            point[num].y = j;
        }
    for (int i = 1; i <= num; i++)
    {
        for (int j = i + 1; j <= num; j++)
        {
            judge(point[i], point[j]);
        }
    }
    cout << ans + 20;
    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
#include <bits/stdc++.h>
using namespace std;
map<pair<double, double>, bool> line;
long long ans = 0;
int main()
{
	for (double x1 = 0; x1 < 20; x1++)
		for (double y1 = 0; y1 < 21; y1++)
			for (double x2 = 0; x2 < 20; x2++)
				for (double y2 = 0; y2 < 21; y2++)
				{
					if (x1 == x2)
						continue;
					double k = (y1 - y2) / (x1 - x2);
					double b = (y2 * x1 - y1 * x2) / (x2 - x1);
					if (!line[{k, b}])
						ans++;
					line[{k, b}] = 1;
				}
	cout << ans + 20;
	return 0;
}

C 货物摆放

可以考虑将所有的因数直接枚举，然后三重循环判断即可

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
#include <bits/stdc++.h>
using namespace std;
long long ans = 0;
long long tar = 2021041820210418;
vector<long long> a;
int main()
{
    long long remp = tar;
    for (int i = 1; i <= sqrt(remp); i++)
    {
        if (remp % i == 0)
        { 
            a.push_back(i);
            if (i * i != remp)
                a.push_back(remp / i);
        }
    }
    int len = a.size();
    for (int i = 0; i < len; i++)
        for (int j = 0; j < len; j++)
            for (int k = 0; k < len; k++)
                if (a[i] * a[j] * a[k] == tar)
                    ans++;
    cout << ans;
    return 0;
}

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
35
36
37
38
39
#include <bits/stdc++.h>
using namespace std;
// floyed算法(会超时大概一分钟之后得到答案/捂脸）)
// 传送门：https://blog.csdn.net/qq_36306833/article/details/121872050
// 答案：10266837
int edge[2030][2030];
int gcd(int x, int y)
{
    if (y == 0)
        return x;
    else
        return gcd(y, x % y);
}
int lcm(int x, int y)
{
    return x / gcd(x, y) * y;
}
int main()
{
    memset(edge, 0x3f, sizeof(edge));
    for (int i = 1; i <= 2021; i++)
        for (int j = i + 1; j <= 2021; j++)
        {
            if (j - i > 21)
                continue;
            int cost = lcm(i, j);
            edge[i][j] = cost;
            edge[j][i] = cost;
        }
    for (int k = 1; k <= 2021; k++)
        for (int i = 1; i <= 2021; i++)
            for (int j = 1; j <= 2021; j++)
            {
                edge[i][j] = min(edge[i][k] + edge[k][j], edge[i][j]);
            }
    cout<<edge[1][2021];
    // cout<<lcm(3,5);
    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
#include <bits/stdc++.h>
using namespace std;
// 传送门：https://blog.csdn.net/qq_36306833/article/details/121872050
// 迪杰斯特拉算法(首次使用紫书模板)
 #define INF 0x3f3f3f3f
int edge[2030][2030];
int path[2030];
bool visit[2030];
int gcd(int x, int y)
{
    if (y == 0)
        return x;
    else
        return gcd(y, x % y);
}
int lcm(int x, int y)
{
    return x / gcd(x, y) * y;
}
int main()
{
    memset(edge, INF, sizeof(edge));
    for (int i = 1; i <= 2021; i++)
        for (int j = i + 1; j <= 2021; j++)
        {
            if (j - i > 21)
                continue;
            int cost = lcm(i, j);
            edge[i][j] = cost;
            edge[j][i] = cost;
        }
    // 算法开始
    memset(visit, 0, sizeof(visit));
    memset(path, INF, sizeof(path));
    path[1] = 0;
    for (int i = 1; i <= 2021; i++)
    {
        int start, min1 = INF;
        for (int j = 1; j <= 2021; j++)
        {
            if (!visit[j] && path[j] <= min1)
            {
                min1 = path[j];
                start = j;
            }
        }
        visit[start] = 1;
        for (int j = 1; j <= 2021; j++)
        {
            path[j] = min(path[j], path[start] + edge[start][j]);
        }
    }
    cout << path[2021];
    return 0;
}

E 回路数

这道题是状态压缩数组，具体注释看代码，更直观

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
#include <bits/stdc++.h>
using namespace std;
// 传送门：https://blog.csdn.net/qq_36306833/article/details/121872050
// 题解：https://blog.csdn.net/weixin_50533561/article/details/122753240?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522164440729916780264043462%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=164440729916780264043462&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~first_rank_ecpm_v1~rank_v31_ecpm-6-122753240.first_rank_v2_pc_rank_v29&utm_term=%E8%93%9D%E6%A1%A5%E6%9D%AF%E5%9B%9E%E8%B7%AF%E8%AE%A1%E6%95%B0&spm=1018.2226.3001.4187
// 状压dp
bool edge[30][30];
const int N = 22, M = 1 << 21; // 即M为二进制10000...000(21个0), M-1 = 21个1
long long dp[M][30];           // dp[i][j]代表状态为i时,走到第j个点时此时的方案数
// 数组要long long，否则溢出(别问我怎么知道的T_T)
int gcd(int x, int y)
{
    if (y == 0)
        return x;
    else
        return gcd(y, x % y);
}
bool judge(int x, int y)
{
    if (gcd(x, y) == 1)
        return true;
    else
        return false;
}
int main()
{
    for (int i = 1; i <= 21; i++)
        for (int j = 1; j <= 21; j++)
            if (judge(i, j))
                edge[i][j] = 1;
    // 状压dp
    dp[1][1] = 1;                                                          //从1号点出发，此时状态为00000...0001
    for (int i = 1; i <= M - 1; i++)                                       // M-1后为111....11111(21个1)，枚举所有状态
        for (int j = 1; j <= 21; j++)                                      //枚举1-21点
            if (i >> (j - 1) & 1)                                          //从左边数第j个，此时若为真，则代表该状态中从左数第j个已走过
                for (int k = 1; k <= 21; k++)                              //若状态中含有该点，则枚举j联通的点，寻找以k为中转到达j点
                    if (edge[k][j] && (i - (1 << (j - 1))) >> (k - 1) & 1) //在未走j之前，状态为 i-(1<<j) 判断是否走过k点
                    //(i - (1 << (j - 1))) >> k & 1)判断i状态时没走j是否走了k
                    {
                        dp[i][j] += dp[(i - (1 << (j - 1)))][k]; //若走过k，说明到达j的状态i可以由挖去j但是含有k的状态完成
                    }
    long long ans = 0;
    for (int i = 2; i <= 21; i++) // dp[1111111..1111][i]代表最终走完并且终点为i点的情况
    //要从i=2开始！因为终点不可能是起点！
    {
        ans += dp[M - 1][i];
    }
    cout << ans;
    return 0;
}

F 砝码称重

类背包，暴力枚举即可

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
#include <bits/stdc++.h>
using namespace std;
// 传送门：https://blog.csdn.net/m0_46260869/article/details/115838370?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522164441437816780366563231%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=164441437816780366563231&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_click~default-2-115838370.first_rank_v2_pc_rank_v29&utm_term=%E7%A0%9D%E7%A0%81%E7%A7%B0%E9%87%8D&spm=1018.2226.3001.4187
// 类背包问题+dp
#define maxn 200000
int n;
long long sum = 0;
int cost[110];
bool dp[110][maxn]; // dp[i][j]代表重量j能否由前i个砝码称出
int main()
{
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> cost[i], sum += cost[i];
    // sum为上界
    for (int i = 1; i <= n; i++)       //枚举1-n个物品
        for (int j = 1; j <= sum; j++) //枚举所有可能重量
        {
            dp[i][j] = dp[i - 1][j]; //之前能称的，现在仍然可以称
            if (dp[i-1][j] == 0)
            {
                if (cost[i] == j)
                    dp[i][j] = 1;
                if (dp[i - 1][j + cost[i]])
                    dp[i][j] = 1;
                if (dp[i - 1][abs(j - cost[i])])
                    dp[i][j] = 1;
            }
        }
    long long ans = 0;
    for (int i = 1; i <= sum; i++)
        if (dp[n][i])
            ans++;
    cout << ans;
    return 0;
}

F 左儿子右兄弟

树形dp
关键是：对于任意一个子节点，它的最大深度是子节点的子树最大深度+儿子数

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;
// 题解：https://blog.csdn.net/qq_52652816/article/details/122333311?ops_request_misc=&request_id=&biz_id=102&utm_term=%E5%B7%A6%E5%AD%A9%E5%AD%90%E5%8F%B3%E5%85%84%E5%BC%9F&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduweb~default-4-122333311.first_rank_v2_pc_rank_v29&spm=1018.2226.3001.4187
// 如果我们把>2的兄弟节点标号排序的话，那么标号在最后一个节点它的深度是最大的，整棵任意节点的高度就等于高度加深度，所以如果我们想要获得更大的高度，只需要把高度最大的那个节点找出来，将它放到最后一个即可。
// 这样的话，递归关系就出来了，找到高度最大的孩子节点，加上它距离原来的父节点的深度
// 知识点：树形dp
vector<int> edge[100000];
int dp[1000090]; // dp[i]代表第i个结点当根节点时，此时以它为结点的子树的深度最大为多少
void dfs(int x)  // x为当前节点
{
    int len=edge[x].size();
    int max1=0;
    for(int i=0;i<len;i++)//寻找子树高度最大的子节点
    {
        int son=edge[x][i];
        dfs(son);
        max1=max(max1,dp[son]);
    }
    dp[x]=max1+len;
}
int main()
{
    int n;
    cin >> n;
    for (int i = 2; i <= n; i++)
    {
        int remp;
        cin >> remp;
        edge[remp].push_back(i);
    }
    dfs(1);
    cout << dp[1];
    return 0;
}