第六届蓝桥杯题解

前言

新蝙蝠侠太好看了！！！姥爷牛逼！！！
在这里插入图片描述
强推去看！！！！！

方程整数解

在这里插入图片描述
这道题可以直接暴力来写，答案有点坑，题目没有说不是负数！答案是 -30

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
// 传送门：https://www.lanqiao.cn/courses/2786/learning/?id=67081
// 答案：-30
int main()
{
    int ans = -1;
    for (int i = 0; i <= 40; i++)
        for (int j = 0; j <= 40; j++)
            for (int z = 0; z <= 40; z++)
            {
                if (i * i + j * j + z * z == 1000)
                {
                    ans = max(ans, j);
                    ans = max(ans, z);
                    ans = max(ans, i);
                }
            }
    cout << "-" << ans;
    return 0;
}

星系炸弹

在这里插入图片描述
直接嗯模拟即可，其实也可以直接用excel来算 （太犯规了），代码解法贴在下面

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
#include <bits/stdc++.h>
using namespace std;
// 传送门：https://www.lanqiao.cn/courses/2786/learning/?id=67081
// 模拟
// 答案：2017-8-05
int month[2][13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31,
                    0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int main()
{
    int y, m, d;
    y = 2014;
    m = 11;
    d = 9;
    int sum = 1000;
    while (sum)
    {
        if (y % 4 == 0)
        {
            if (sum - (month[1][m] - d) < 0)
            {
                d += sum;
                sum = 0;
            }
            else
            {
                sum -= (month[1][m] - d);
                m++;
                d = 0;
                if (m == 13)
                {
                    m = 1;
                    y++;
                }
            }
        }
        else
        {
            if (sum - (month[0][m] - d) < 0)
            {
                d += sum;
                sum = 0;
            }
            else
            {
                sum -= (month[0][m] - d);
                m++;
                d = 0;
                if (m == 13)
                {
                    m = 1;
                    y++;
                }
            }
        }
    }
    cout << y << " " << m << " " << d;
    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;
int mon[2][13]={0,31,28,31,30,31,30,31,31,30,31,30,31,
				0,31,29,31,30,31,30,31,31,30,31,30,31};
int y,m,d;
int main()
{
	y=2014,m=11,d=9;
	int last=1000;
	while(last)
	{
		if(y%4)
		{
			if(last>=(mon[0][m]-d))
			{
				last-=(mon[0][m]-d);
				d=0;
				m++;
			}
			else
			{
				d+=last;
				last=0;
				break;
			}
			if(m>12)
			{
				m=1;
				y++;
			}
		}
		else
		{
			if(last>=(mon[1][m]-d))
			{
				last-=(mon[1][m]-d);
				d=0;
				m++;
			}
			else
			{
				d+=last;
				last=0;
				break;
			}
			if(m>12)
			{
				m=1;
				y++;
			}			
		}
	}
	cout << y << " " << m << " " << d;
	return 0;
}

奇妙的数字

在这里插入图片描述
直接暴力就完了，从1到1000枚举，算到谁是谁

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://www.lanqiao.cn/courses/2786/learning/?id=67081
// 暴力枚举
int visit[10];
bool judge(int x, int y)
{
    int cnt1 = 0, cnt2 = 0;
    while (x)
    {
        visit[x % 10] = 1;
        cnt1++;
        x /= 10;
    }
    while (y)
    {
        visit[y % 10] = 1;
        cnt2++;
        y /= 10;
    }
    if (cnt1 + cnt2 != 10)
    {
        return false;
    }
    for (int i = 0; i < 10; i++)
    {
        if (visit[i] != 1)
            return false;
    }
    return true;
}
int main()
{
    for (int i = 1; i <= 10000; i++)
    {
        memset(visit, 0, sizeof(visit));
        if (judge(i * i * i, i * i))
        {
            cout << i;
        }
    }
    return 0;
}

格子中输出

在这里插入图片描述
在这里插入图片描述
这道题实属有点恶心，如果不知道printf的这种用法多半是寄了 （比如说我）
(width-2-strlen(buf))/2,” “,buf,(width-2-strlen(buf)+1)/2,” “
因为它题目要求如果没有办法中间，要向左上靠，所以前面是除2，后面直接减去

九数组

在这里插入图片描述
在这里插入图片描述
这道题考察的是对深搜回溯的理解，dfs回溯写多的可以妙出答案
t = x[k], x[k] = x[i], x[i] = t;

牌型种数

在这里插入图片描述
在这里插入图片描述
简化一下模型，就是13种牌，每种牌有四张，然后取13张，有多少种取法
这道题解法很多：
首先是暴力枚举，直接枚举每种牌的个数,如果和能等于13就行

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
#include <stdio.h>
int main () {
 
	int ans = 0;
	for (int a = 0;a < 5;a++) {
		for (int b = 0;b < 5;b++) {
		for (int c = 0;c < 5;c++) {
		for (int d = 0;d < 5;d++) {
		for (int e = 0;e < 5;e++) {
		for (int f = 0;f < 5;f++) {
		for (int g = 0;g < 5;g++) {
		for (int h = 0;h < 5;h++) {
		for (int i = 0;i < 5;i++) {
		for (int j = 0;j < 5;j++) {
		for (int k = 0;k < 5;k++) {
		for (int l = 0;l < 5;l++) {
		for (int m = 0;m < 5;m++) {
		if ((a+b+c+d+e+f+g+h+i+j+k+l+m) == 13)
			ans++;
	}
		}
	}
		}
	}
		}
	}
		}
	}
		}
	}
		}
	}
	printf ("%d",ans);
	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
#include <bits/stdc++.h>
using namespace std;
// 传送门：https://blog.csdn.net/alidadaaaa/article/details/79690108?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522164793048016780274131254%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=164793048016780274131254&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~first_rank_ecpm_v1~rank_v31_ecpm-1-79690108.142^v3^pc_search_result_cache,143^v4^control&utm_term=%E7%89%8C%E5%9E%8B%E7%A7%8D%E6%95%B0&spm=1018.2226.3001.4187
// dfs
int ans;
void dfs(int n, int cardnum) // n是代表牌的花色，cardnum代表牌的总数
{
    if (n > 13)
    {
        return;
    }
    if (cardnum == 13)
    {
        ans++;
        return;
    }
    if (cardnum > 13)
    {
        return;
    }
    dfs(n + 1, cardnum);
    dfs(n + 1, cardnum + 1);
    dfs(n + 1, cardnum + 2);
    dfs(n + 1, cardnum + 3);
    dfs(n + 1, cardnum + 4);
}
int main()
{
    dfs(0, 0);
    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
#include <bits/stdc++.h>
using namespace std;
int ans;
void dfs(int num,int cardnum)
{
	if(cardnum>13&&num>14)
		return;
	if(num==14&&cardnum==13)
	{
		ans++;
	}
	if(num<=13)
	{
		dfs(num+1,cardnum);
		dfs(num+1,cardnum+1);
		dfs(num+1,cardnum+2);
		dfs(num+1,cardnum+3);
		dfs(num+1,cardnum+4);
	}
}
int main()
{
	dfs(1,0);
	cout<<ans;
	return 0;
}

手链样式

在这里插入图片描述

我们首先要理解它题目的转动和反转的意思
就好比AAABBBBCCCCC是一个链
首先我们理解第一个词，转动—–手链是一个环，所以说呢，我们先放第一个简单的情况进行类比
第一种情况就是 AAABBBBCCCCC,然后串成环，头部的A和尾部的C就连接起来了
现在我们进行一次转动，转动一个单位，字符串就成了AABBBBCCCCCA,但是呢，在手链这个环中，样式还是没变，也就是说，当我们转动其中一种情况的环时，同时能诞生出好几种不同字符串相同样式的环，这些情况就不能算进去。
另外一种情况翻转，翻转这种情况的实际上其实就是将手链转动一周，例如：AAABBBBCCCCC转动一周后就是CCCCCBBBBAAA。
那么问题来了，我们搜到一种排列方式，我们要标记他的转动和翻转，怎么实现呢？
很简单也很巧妙！！！比如AAABBBBCCCCC，我们将其str=str+str，自己加上自己，相同的字符串连到一起，这样变成AAABBBBCCCCCAAABBBBCCCCC！!这样就可以解决转动的问题！我们再将字符串倒序，就可以解决反转的问题！！！
因此综上所述，我们有效的处理这两种限制情况的办法就是构建两个个新的字符串，一个为两个字符串相拼接，另一个是将前一个字符串倒序。（temp1 = str + str，temp=reverse（str+str））
参考大佬思路

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 <bits/stdc++.h>
using namespace std;
// 传送门：https://blog.csdn.net/bettle_king/article/details/115028506?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522164793155016782184611226%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=164793155016782184611226&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~first_rank_ecpm_v1~rank_v31_ecpm-1-115028506.142^v3^pc_search_result_cache,143^v4^control&utm_term=%E6%89%8B%E9%93%BE%E6%A0%B7%E5%BC%8F&spm=1018.2226.3001.4187
// 环上问题
int ans = 0;
vector<string> a;
int main()
{
    string tar = "AAABBBBCCCCC";
    do
    {
        bool flag = true;
        for (int i = 0; i < a.size(); i++)
        {
            if (a[i].find(tar) != string::npos) //假如在已经储存的字符串依次遍历找不到新字符串的子串
            {
                flag = false;
                break;
            }
        }
        if (!flag)
            continue;
        string remp1 = tar + tar;
        a.push_back(remp1);
        reverse(remp1.begin(), remp1.end());
        a.push_back(remp1);
        ans++;

    } while (next_permutation(tar.begin(), tar.end()));
    cout << ans;
    return 0;
}

另外补一下这个next_premutation的说明，这是stl内置求一个序列全排列的函数，可以自动枚举不同次序字符串
模板：

1
2
3
4
5
6
7
int a[]={1,2,3,4,5};
do
{
	for(int i=0;i<len;i++)
	cout<<a[i];
	cout<<endl;
}while(next_premutation(0,len-1))

next_premutation详解

饮料换购

直接模拟就行，老老实实按步骤来
在这里插入图片描述

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 <bits/stdc++.h>
using namespace std;
// 传送门：http://lx.lanqiao.cn/problem.page?gpid=T2796
// 嗯模拟
int main()
{
    ios::sync_with_stdio(false);
    int num = 0;
    int ans = 0;
    int ping = 0;
    cin >> num;
    while (num)
    {
        num--;
        ans++;
        ping++;
        if (ping == 3)
        {
            ping = 0;
            num++;
        }
    }
    cout << ans;
    return 0;
}

垒骰子

在这里插入图片描述
这道题的题目很坑，当时做的时候看样例一脸懵逼，两个骰子为啥会有500多种方法？
其实可以想象一下，一个骰子，当朝上的方向固定时，它可以转动：
在这里插入图片描述
理解题意之后，可以考虑两种方式入手
第一种：深搜：（TLE）只能37分
这应该时考场上没有办法的办法了

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
#include <bits/stdc++.h>
using namespace std;
// http://lx.lanqiao.cn/problem.page?gpid=T2797
const long long mod = 1e9 + 7;
int link[7][7];
map<int, int> edge;
int n, m; // n个骰子，m个排斥关系
long long ans;
void start()
{
    edge[1] = 4;
    edge[2] = 5;
    edge[3] = 6;
    edge[4] = 1;
    edge[5] = 2;
    edge[6] = 3;
    for (int i = 1; i <= 6; i++)
        for (int j = 1; j <= 6; j++)
            link[i][j] = 1;
}
void dfs(int cnt, int up) // up代表上方数字
{
    if (cnt == n)
    {
        (ans++) % mod;
        return;
    }
    for (int i = 1; i <= 6; i++) //枚举下一个上方数字
    {
        // cout << link[up][edge[i]] << endl;
        if (link[up][edge[i]]) // 如果和下面的骰子不矛盾
        {
            // cout << cnt << endl;
            dfs(cnt + 1, i);
        }
    }
    return;
}
long long fast_power(long long a, long long b, long long c)
{
    long long ans = 1;
    while (b)
    {
        if (b % 2)
            ans = (ans * a) % c;
        b /= 2;
        a = (a * a) % c;
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    start();
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int remp1, remp2;
        cin >> remp1 >> remp2;
        link[remp1][remp2] = link[remp2][remp1] = 0;
    }
    for (int i = 1; i <= 6; i++)
    {
        dfs(1, i);
    }
    ans = (ans * fast_power(4, n, mod)) % mod;
    cout << ans;
    return 0;
}

第二种：dp（TLE）75分
dp[i][j]代表第i层骰子朝上的面是j时，此时的方案数

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
#include <bits/stdc++.h>
using namespace std;
// dp解法：http://lx.lanqiao.cn/problem.page?gpid=T2797
// 75分
const long long mod = 1e9 + 7;
long long dp[50000][7]; // dp[i][j]代表第i层j朝上时，此时有多少种方案
int op[7];              //对立面
int conflict[7][7];     //冲突
int n, m;
long long fast_power(long long a, long long b, long long c)
{
    long long ans = 1;
    while (b)
    {
        if (b % 2)
            ans = (ans * a) % c;
        b /= 2;
        a = (a * a) % c;
    }
    return ans;
}
void init() //初始化
{
    op[1] = 4;
    op[2] = 5;
    op[3] = 6;
    op[4] = 1;
    op[5] = 2;
    op[6] = 3;
    for (int i = 1; i <= 6; i++)
    {
        dp[1][i] = 1;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    init();
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int remp1, remp2;
        cin >> remp1 >> remp2;
        conflict[remp1][remp2] = conflict[remp2][remp1] = 1;
    }
    for (int i = 2; i <= n; i++) //枚举层数
    {
        for (int j = 1; j <= 6; j++) //枚举上面的骰子顶部数字
        {
            for (int k = 1; k <= 6; k++) //枚举上面骰子顶部数字
            {
                int down = op[k];
                if (conflict[j][down] == 0)
                {
                    dp[i][k] = dp[i][k] + dp[i - 1][j];
                    dp[i][k] %= mod;
                }
            }
        }
    }
    long long ans = 0;
    for (int i = 1; i <= 6; i++)
    {
        ans = ans + dp[n][i];
        ans %= mod;
    }
    ans = ans * fast_power(4, n, mod);
    ans %= mod;
    cout << ans;
    return 0;
}

第三种：矩阵快速幂（AC）100
（我不会我是菜鸡）