第八届蓝桥杯题解

胡言乱语

鼠鼠开学又延迟了呜呜呜呜呜呜呜呜
我以为高考结束是我的最长的假期
但是事实证明：
我太年轻了.jpg
（所以这是你摆烂的理由吗fw）
在这里插入图片描述
言归正传

迷宫

在这里插入图片描述
在这里插入图片描述
可以考虑深搜来做，只要能到边界我们认为就是可以走出来，那么咱们怎么知道他走不出来呢？处理方式很简单，众所周知，细心的你肯定能发现，假如想每个方格只走一次且一直走下去是不可能的，如果走不出来，肯定是在兜圈子，那么我们只要当走到走过的地点，我们认为它不行。实现很简单，设一个visit数组即可

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
#include <bits/stdc++.h>
using namespace std;
// 传送门：https://www.lanqiao.cn/courses/2786/learning/?id=67724
// dfs
// 答案：31
char edge[110][110];
map<char, int> dirx, diry;
int visit[110][110];
bool dfs(int x, int y)
{
    if (!(x <= 10 && x >= 1 && y <= 10 && y >= 1))
        return true;
    if (visit[x][y]) //如果走不出去，肯定是走到原来走过的点转圈圈
        return false;
    char tar = edge[x][y];
    visit[x][y] = 1;
    int next_x = x + dirx[tar];
    int next_y = y + diry[tar];
    return dfs(next_x, next_y);
}
int main()
{
    int ans = 0;
    dirx['D'] = 1, diry['D'] = 0;
    dirx['U'] = -1, diry['U'] = 0;
    dirx['L'] = 0, diry['L'] = -1;
    dirx['R'] = 0, diry['R'] = 1;
    for (int i = 1; i <= 10; i++)
    {
        string remp;
        cin >> remp;
        for (int j = 0; j < 10; j++)
        {
            edge[i][j + 1] = remp[j];
        }
    }
    for (int i = 1; i <= 10; i++)
    {
        for (int j = 1; j <= 10; j++)
        {
            memset(visit, 0, sizeof(visit));
            if (dfs(i, j))
                ans++;
        }
    }
    cout << ans << endl;
    return 0;
}
/*
样例：
UDDLUULRUL
UURLLLRRRU
RRUURLDLRD
RUDDDDUUUU
URUDLLRRUU
DURLRLDLRL
ULLURLLRDU
RDLULLRDDD
UUDDUDUDLL
ULRDLUURRR
*/

二刷的新写法

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;
map<char,pair<int,int>> dir;
char maze[100][100];
int visit[100][100]; 
int ans;
void init()
{
	dir['U']={-1,0};
	dir['D']={1,0};
	dir['L']={0,-1};
	dir['R']={0,1};
}
bool dfs(int x,int y)
{
	if(!(x<=10&&x>=1&&y<=10&&y>=1))
	{
		return true;
	}
	if(visit[x][y])
	{
		return false;
	}
		
	visit[x][y]=1;
	char d=maze[x][y];
	int rempx=x+dir[d].first;
	int rempy=y+dir[d].second;
	return dfs(rempx,rempy); 
}
int main()
{
	init();
	for(int i=1;i<=10;i++)
	{
		string remp;
		cin>>remp;
		int l=remp.length();
		for(int j=0;j<l;j++)
		{
			maze[i][j+1]=remp[j];
		}
	}
	for(int i=1;i<=10;i++)
	{
		for(int j=1;j<=10;j++)
		{
			memset(visit,0,sizeof(visit));
			if(dfs(i,j))
			ans++;
		}
	}
	cout<<ans;
	return 0;
}

跳蚱蜢

在这里插入图片描述

一道bfs题，第一眼看上去没啥思路，很难想到是bfs，但是想到了就很简单，我们考虑用数字字符串模拟，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
56
57
58
59
60
61
62
63
 #include <bits/stdc++.h>
using namespace std;
// 传送门：https://www.lanqiao.cn/courses/2786/learning/?id=67724
// bfs模板题
struct node
{
    string path;
    int step;
};
int ans;
queue<node> q;
string start = "087654321";
string tar = "012345678"; // 0代表空盘子
int dir[] = {-2, -1, 1, 2};
map<string, bool> visit;
int find(string str, char ch)
{
    int len = str.length();
    for (int i = 0; i < len; i++)
    {
        if (str[i] == ch)
            return i;
    }
}
void bfs()
{
    node s;
    s.path = start;
    s.step = 0;
    q.push(s);
    while (!q.empty())
    {
        node now = q.front();
        q.pop();
        string remp = now.path;
        if (visit[remp])
            continue;
        visit[remp] = 1;
        int nowstep = now.step;
        int pos = find(remp, '0');
        // cout << remp << " " << nowstep << endl;
        for (int i = 0; i < 4; i++)
        {
            string next = remp;
            swap(next[pos], next[(pos + dir[i] + 9) % 9]); //防止溢出
            if (next == tar)
            {
                ans = nowstep + 1;
                return;
            }
            node nextnode;
            nextnode.path = next;
            nextnode.step = nowstep + 1;
            q.push(nextnode);
        }
    }
}
int main()
{
    bfs();
    cout << ans << endl;
    return 0;
}

方格分割

在这里插入图片描述
在这里插入图片描述

这道题第一眼看很吓人，但是有了突破口很容易，因为图形是对称，所以构造分割线肯定在图形中心开始延展，因为对称，所以向一个方向延申，其另一头必然从相反一头延展。我们只要记录能延展到边界的分割线个数即可
结果要除4，因为有旋转对称，只要能通过旋转得到，就是同一个

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
#include <bits/stdc++.h>
using namespace std;
// 传送门：https://www.lanqiao.cn/courses/2786/learning/?id=67724
// dfs深搜
// 思路很巧妙，利用中心点向边缘发散，因为是对称的，所以扩展方向只有两种，免去了最终判断是否是对称的必要
// 只需要计算能到达边界的分割线个数即可
// 结果需要除4，因为旋转相同算同一种分法
bool visit[10][10];
int ans;
int dirx[4] = {0, 0, -1, 1};
int diry[4] = {-1, 1, 0, 0};
void dfs(int x, int y)
{
    if (x == 1 || y == 1 || x == 7 || y == 7)
    {
        ans++;
        return;
    }
    if (visit[x][y])
        return;
    visit[x][y] = 1;
    visit[8 - x][8 - y] = 1;
    for (int i = 0; i < 4; i++)
    {
        if (x <= 7 && x >= 1 && y <= 7 && y >= 1)
            dfs(x + dirx[i], y + diry[i]);
    }
    visit[x][y] = 0;
    visit[8 - x][8 - y] = 0;
}
int main()
{
    dfs(4, 4);
    cout << ans / 4;
    return 0;
}

更新：二刷的时候又仔细想了一下，感觉不是很严谨，visit回溯修改应该放在for里面，虽然感觉有点问题，但是答案两种写法结果一样，不知道什么原因，有懂哥知道的话说一下
这是二刷的代码

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;
bool visit[10][10];
int dirx[]={0,0,-1,1};
int diry[]={1,-1,0,0};
int ans;
void dfs(int x,int y)
{
	if(x==1||x==7||y==1||y==7)
	{
		ans++;
		return;
	}
	for(int i=0;i<4;i++)
	{
		int rempx=x+dirx[i];
		int rempy=y+diry[i];
		if(visit[rempx][rempy])
			continue;
		visit[rempx][rempy]=visit[8-rempx][8-rempy]=1;
			dfs(rempx,rempy);
		visit[rempx][rempy]=visit[8-rempx][8-rempy]=0;
	}
}
int main()
{
	visit[4][4]=1;
	dfs(4,4);
	cout<<ans/4;
	return 0;
}

字母组串

在这里插入图片描述
其实道理很简单，长度为n的字符串肯定由n-1个字符串得到，n-1个字符串缺少的字母有三种情况：缺a，缺b，缺c
无脑加起来就好了

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=67724
// 简单递归
// a个A，b个B，c个C 字母，能组成多少个不同的长度为n的串。
int f(int a, int b, int c, int n)
{
    if (a < 0 || b < 0 || c < 0)
        return 0;
    if (n == 0)
        return 1;

    return f(a, b, c - 1, n - 1) + f(a - 1, b, c, n - 1) + f(a, b - 1, c, n - 1); // 填空
}
// 简单递归，n个字符由n-1的三种字符相加而成
int main()
{
    printf("%d\n", f(1, 1, 1, 2));
    printf("%d\n", f(1, 2, 3, 3));
    return 0;
}

最大公共子串

在这里插入图片描述
这个也很容易，a[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
#include <bits/stdc++.h>
using namespace std;
#define N 256
// 传送门：https://www.lanqiao.cn/courses/2786/learning/?id=67724
// 这个不难，看懂思路就可以填出来
int f(const char *s1, const char *s2)
{
    int a[N][N];
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    int i, j;

    memset(a, 0, sizeof(int) * N * N);
    int max = 0;
    for (i = 1; i <= len1; i++)
    {
        for (j = 1; j <= len2; j++)
        {
            if (s1[i - 1] == s2[j - 1])
            {
                a[i][j] = a[i - 1][j - 1] + 1; //填空
                if (a[i][j] > max)
                    max = a[i][j];
            }
        }
    }

    return max;
}

int main()
{
    printf("%d\n", f("abcdkkk", "baabcdadabc"));
    return 0;
}

正则问题


题目意思有点晦涩，大概是定义新运算吧(正则我也不知道是什么东西)
遇到“|”就比较其左右两边的大小 如样例((xx|xxx)x|(x|xx))xx
(xx|xxx)的长度为3，遇到x加上1得4，(x|xx)=2，4|2=4，遇到
xx得到6
这个思路是从大佬学的，思路确实很强悍，化繁为简，很难想到，但是想到就很容易
大体思路就是：设置一个max值，temp进行计数，每当遇到“|”或者“）”就结算一次，将max更新，然后计数器temp清零

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
#include <bits/stdc++.h>
using namespace std;
// 传送门：http://lx.lanqiao.cn/problem.page?gpid=T2823
// 递归(思路很巧妙)
int pos; //指针
int len; //字符串长度
string str;
int ans() // ans()计算的是一个"(...)"值
{
    int max1 = 0;
    int temp = 0;
    while (pos < len)
    {
        if (str[pos] == '(')
        {
            pos++;
            temp += ans(); //遇到
        }
        else if (str[pos] == 'x')
        {
            pos++;
            temp++;
        }
        else if (str[pos] == '|')
        {
            pos++;
            max1 = max(temp, max1); //时刻更新这个max1，到最后直接返回max1
            temp = 0;
        }
        else if (str[pos] == ')')
        {
            pos++;
            max1 = max(temp, max1);
            return max1; //切记：这个地方temp就别清零了！！因为括号还可能有'x'
        }
    }
    max1 = max(temp, max1);
    return max1;
}
int main()
{
    ios::sync_with_stdio(false);
    cin >> str;
    len = str.length();
    cout << ans();
    return 0;
}

包子凑数

在这里插入图片描述

完全背包问题
这个地方有一个结论，就是假如这些包子数的公因数是1，答案就是有限个，否则是INF
关于这个结论的解释：如果输入的数的最大公约数不为1，那么就会有无数种数目是凑不出的，比如最大公约数是3，那么选出n笼后的结果就一定是3的倍数，这样不是3的倍数的数字就凑不出了。
（鸣谢cjmdyl大佬！！！结论的解释！）

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
#include <bits/stdc++.h>
using namespace std;
// 传送门：https://www.lanqiao.cn/courses/2786/learning/?id=67724
// 完全背包
// 记住：假如输入的数最大公约数不是1，则就是INF
#define maxn 10010
int value[maxn];
int visit[maxn];
int n;
int gcd(int x, int y)
{
    if (y == 0)
        return x;
    else
        return gcd(y, x % y);
}
// 0和任何数的最大公因数是这个数自己
bool judge(int x, int y)
{
    if (gcd(x, y) == 1)
        return true;
    else
        return false;
}
int main()
{
    ios::sync_with_stdio(false);
    int flag = 0;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> value[i];
        flag = gcd(flag, value[i]);
    }
    if (flag != 1)
    {
        cout << "INF" << endl;
    }
    else
    {
        visit[0] = 1;
        for (int i = 1; i <= n; i++)
        {
            for (int j = value[i]; j <= maxn; j++)
            {
                if (visit[j - value[i]])
                    visit[j] = 1;
            }
        }
        int ans = 0;
        for (int i = 1; i <= 10000; i++)
        {
            if (!visit[i])
                ans++;
        }
        cout << ans;
    }
    return 0;
}