- 1【springboot】springboot实现短信验证功能:_springboot短信验证码
- 2How to checkout non-master branch_如何checkout nobranch
- 3深度学习入门——波士顿房价预测
- 4NLP-词向量-发展：词袋模型【onehot、tf-idf】 -＞ 主题模型【LSA、LDA】 -＞ 词向量静态表征【Word2vec、GloVe、FastText】 -＞ 词向量动态表征【Bert】_词袋表征
- 5用AI算法起中文名字 ---- 传统起名字方法（2）：传统经典起名方法罗列（1）_ai 对话 取名
- 6基于jQuery.i18n.properties 实现前端页面的资源国际化_html5 静态页面 国际化
- 7开源流程图表库（01）：Mermaid.js生成流程图、时序图、甘特图等_流程图 js库
- 8ros:使用gmapping 和 hector_slam功能包实现SLAM仿真，并将简历完成的地图保存到功能包的maps文件夹中，以及基于move_base和amcl功能包的机器人自主导航仿真_hector_slam导航
- 9[精简整理]疏通中国历史脉络——“元、明、清(1840鸦片战争止)”篇_python人马大战csdn免费专区
- 10【Mac】破解死循环，成功安装 Homebrew、curl、wget，快速配置 zsh_mac 安装curl
倪文迪陪你学蓝桥杯2021寒假每日一题：（2017省赛A第1、2题）_蓝桥杯迷宫填空2017
赞
踩
2021年寒假每日一题，2017~2019年的省赛真题。
本文内容由倪文迪（华东理工大学计算机系软件192班）和罗勇军老师提供。
OJ：可以到http://oj.ecustacm.cn/交题，从第3页开始是历年真题：http://oj.ecustacm.cn/problemset.php?page=3
后面的每日一题，每题发一个新博文，请大家看博客目录：https://blog.csdn.net/weixin_43914593
一、2017年蓝桥杯软件类 C语言大学A组
共10题，题目总览：
1、迷宫
2、跳蚱蜢
3、魔方状态
4、方格分割
5、字母组串
6、最大公共子串
7、正则问题
8、包子凑数
9、分巧克力
10、油漆面积
第一天：2021.1.3日
1. 迷宫
题目链接： http://oj.ecustacm.cn/problem.php?id=1317
（1）投机取巧的搞法
根据本文的“附考生须知”，第1题是填空题，只交答案就行了。如果不想编码，直接用手一个个去数那100个点，几分钟就数完了，答案是31，比编码还要快。
在OJ上这样交就能AC：
#include<iostream>
using namespace std;
int main(){
cout << 31 << endl;
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
（2）还是用这题来练练DFS编码吧
题解：
一道搜索题，可以选择暴力dfs，代码简短
我写的稍微长一点，但可以确保每个点只走到一次，稍微优化了那么一丢丢
此题唯一的坑点是提交到OJ时，千万不要写输入！！555
直接输出一个数字就好惹…
参考代码：（罗老师注：倪文迪没有用递归写DFS。参考这篇用递归写的DFS，更好懂：https://www.cnblogs.com/-citywall123/p/12316760.html）
#include<iostream> #include<algorithm> #include<cstring> #include<string> #include<vector> #include<cmath> #include<cstdio> using namespace std; int mp[20][20]; int vis[20][20]; bool tag[200]; int cnt[200]; int X[] = {0, 0, 0, -1, 1}; int Y[] = {0, -1, 1, 0, 0}; void solve(int x, int y, int id) { while(x >= 1 && x <= 10 && y >= 1 && y <= 10 && !vis[x][y]){ vis[x][y] = id; cnt[id]++; int now = mp[x][y]; x += X[now]; y += Y[now]; } if(x < 1 || x > 10 || y < 1 || y > 10){ tag[id] = true; return ; } if(vis[x][y]){ if(tag[vis[x][y]]) tag[id] = true; } return ; } int main(){ for(int i = 1 ; i <= 10 ; i++){ string s; cin >> s; for(int j = 0 ; j < 10 ; j++){ if(s[j] == 'L') mp[i][j + 1] = 1; else if(s[j] == 'R') mp[i][j + 1] = 2; else if(s[j] == 'U') mp[i][j + 1] = 3; else if(s[j] == 'D') mp[i][j + 1] = 4; } } int id = 1; for(int i = 1 ; i <= 10 ; i++){ for(int j = 1 ; j <= 10 ; j++){ if(!vis[i][j]){ solve(i, j, id); id++; } } } /*for(int i = 1 ; i <= 10 ; i++){ for(int j = 1 ; j <= 10 ; j++){ printf("%3.d",vis[i][j]); } cout << endl; }*/ int res = 0; for(int i = 1 ; i < id ; i++){ if(tag[i]) res += cnt[i]; } printf("%d\n", res); 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
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
第二天：2021.1.4日
2. 跳蚱蜢
题目链接： http://oj.ecustacm.cn/problem.php?id=1318
又是一道填空题，能用手数出答案吗？
提前告诉大家，答案是20。数字好像不大，可是，用手数出来好像不可能，还是老实编码吧。
2.1 建模
直接让蚱蜢跳到空盘有点麻烦，因为有很多蚱蜢在跳，跳晕了。如果看成空盘跳到蚱蜢的位置就简单多了，只有一个空盘在跳。
题目给的是一个圆圈，不好处理，此时祭出一个建模大法：“化圆为线”！ 把空盘看成0，那么有9个数字{0,1,2,3,4,5,6,7,8}，一个圆圈上的9个数字，拉直成了一条线上的9个数字。
等等，这不就是八数码问题吗？八数码是经典的BFS问题。
八数码有9个数字{0,1,2,3,4,5,6,7,8}，它有9！=362880种排列。也不多，
本题的初始状态是“012345678”，终止状态是“087654321”。
从初始状态跳一次，有4种情况：
2.2 判重
这题要是写个裸的BFS，不判重，能运行出来吗？
第1步到第2步，有4种跳法；第2步到第3步，有4*4种；…；第20步，有4^20=1万亿种！太多了！BFS的队列也放不下呀。
还是得判重，如果跳到一个曾经出现过的情况，就不用往下跳了。八数码只有9！=362880种排列，好判。
如何判重？比赛的时候紧张，当然得用STL，用map、set判重都行，效率都好。另外，有一种数字方法，叫康托判重，得自己写，一般不用。
2.3 map判重
把9个数字的排列定义为一种状态，即字符串s，例如初始状态“012345678”是一个串。对应交换之后产生的s，我们可以使用map判重，将该字符串以及它首次出现的时间作为一个单位推入队列中，由于BFS的性质我们能看出，首次找到结果状态的时间t即是最小的答案。
倪文迪的代码：
#include<bits/stdc++.h> using namespace std; struct node { node(){} node(string ss, int tt){ s = ss, t = tt; } string s; int t; }; map<string, bool> mp; queue<node> q; void solve() { while(!q.empty()){ node now = q.front(); q.pop(); string s = now.s; int t = now.t; if(s == "087654321"){ cout << t << endl; break; } int i; for(i = 0 ; i < 10 ; i++){ if(s[i] == '0') break; } for(int j = i - 2 ; j <= i + 2 ; j++){ int k = (j + 9) % 9; if(k == i) continue; char tmp; tmp = s[i];s[i] = s[k];s[k] = tmp; if(!mp[s]){ mp[s] = true; q.push(node(s, t + 1)); } tmp = s[i];s[i] = s[k];s[k] = tmp; } } } int main(){ string s = "012345678"; q.push(node(s, 0)); mp[s] = true; solve(); 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
2.4 set判重
代码参考：https://blog.csdn.net/crazymooo/article/details/108816699
2.5 康托判重
map和set的判重效率是很高的。另外有一种数学判重方法，叫做康托判重，运行起来比map和set快，下面介绍一下。
在《算法竞赛入门到进阶》（清华大学出版社，罗勇军著）47页详解了八数码的康托判重。这里附上截图：
以上是截图。
下面是书中的代码，用“BFS + 康托(Cantor)”解决了八数码问题，其中BFS用STL的queue实现。
#include<bits/stdc++.h> const int LEN = 362888; //状态共9!=362880种 using namespace std; struct node{ int state[9]; //记录一个八数码的排列，即一个状态 int dis; //记录到起点的距离 }; int dir[4][2] = {{-1,0}, {0,-1},{1,0},{0,1}}; //左、上、右、下顺时针方向。左上角坐标是(0,0) int visited[LEN]={0}; //与每个状态对应的记录，Cantor函数对它置数，并判重 int start[9]; //开始状态 int goal[9]; //目标状态 long int factory[] = {1,1,2,6,24,120,720,5040,40320,362880}; //Cantor用到的常数 bool Cantor(int str[], int n) { //用康托展开判重 long result = 0; for(int i = 0; i < n; i++) { int counted = 0; for(int j = i+1; j < n; j++) { if(str[i] > str[j]) //当前未出现的元素中是排在第几个 ++counted; } result += counted*factory[n-i-1]; } if(!visited[result]) { //没有被访问过 visited[result] = 1; return 1; } else return 0; } int bfs() { node head; memcpy(head.state, start, sizeof(head.state)); //复制起点的状态 head.dis = 0; queue <node> q; //队列中放状态 Cantor(head.state, 9); //用康托展开判重，目的是对起点的visited[]赋初值 q.push(head); //第一个进队列的是起点状态 while(!q.empty()) { //处理队列 head = q.front(); q.pop(); //可在此处打印head.state，看弹出队列的情况 int z; for(z = 0; z < 9; z++) //找这个状态中元素0的位置 if(head.state[z] == 0) //找到了 break; //转化为二维，左上角是原点(0, 0)。 int x = z%3; //横坐标 int y = z/3; //纵坐标 for(int i = 0; i < 4; i++){ //上、下、左、右最多可能有4个新状态 int newx = x+dir[i][0]; //元素0转移后的新坐标 int newy = y+dir[i][1]; int nz = newx + 3*newy; //转化为一维 if(newx>=0 && newx<3 && newy>=0 && newy<3) {//未越界 node newnode; memcpy(&newnode,&head,sizeof(struct node));//复制这新的状态 swap(newnode.state[z], newnode.state[nz]);//把0移动到新的位置 newnode.dis ++; if(memcmp(newnode.state,goal,sizeof(goal)) == 0) //与目标状态对比 return newnode.dis; //到达目标状态，返回距离，结束 if(Cantor(newnode.state, 9)) //用康托展开判重 q.push(newnode); //把新的状态放进队列 } } } return -1; //没找到 } int main(){ for(int i = 0; i < 9; i++) cin >> start[i]; //初始状态 for(int i = 0; i < 9; i++) cin >> goal[i]; //目标状态 int num = bfs(); if(num != -1) cout << num << endl; else cout << "Impossible" << 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
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
2.6 扩展学习
另外，可以用双向BFS来进一步优化八数码，参考这篇博文：https://blog.csdn.net/weixin_43914593/article/details/104761298
附：2017年第八届蓝桥杯大赛个人赛省赛（软件类） C/C++ 大学A组考生须知
考生须知：
♦考试开始后，选手首先下载题目，并使用考场现场公布的解压密码解压试题。
♦考试时间为4小时。时间截止后，提交答案无效。
♦在考试强制结束前，选手可以主动结束考试（需要身份验证），结束考试后将无法继续提交或浏览答案。
♦选手可浏览自己已经提交的答案。被浏览的答案允许拷贝。
♦对同一题目，选手可多次提交答案，以最后一次提交的答案为准。
♦选手切勿在提交的代码中书写“姓名”、“考号”，“院校名”等与身份有关的信息或其它与竞赛题目无关的内容，否则成绩无效。
♦选手必须通过浏览器方式提交自己的答案。选手在其它位置的作答或其它方式提交的答案无效。
♦试题包含三种类型：“结果填空”、“代码填空”与“程序设计”。
结果填空题：要求选手根据题目描述直接填写结果。求解方式不限。不要求源代码。
把结果填空的答案直接通过网页提交即可，不要书写多余的内容。
代码填空题：要求选手在弄清给定代码工作原理的基础上填写缺失的部分，使得程序逻辑正确、完整。
把代码填空的答案（仅填空处的答案，不包括题面已存在的代码或符号）直接通过网页提交即可，不要书写多余的内容。
使用ANSI C/ANSI C++ 标准，不要依赖操作系统或编译器提供的特殊函数。
程序设计题目：要求选手设计的程序对于给定的输入能给出正确的输出结果。考生的程序只有能运行出正确结果才有机会得分。
注意：在评卷时使用的输入数据与试卷中给出的示例数据可能是不同的。选手的程序必须是通用的，不能只对试卷中给定的数据有效。
对于编程题目，要求选手给出的解答完全符合ANSI C++标准，不能使用诸如绘图、Win32API、中断调用、硬件操作或与操作系统相关的API。
代码中允许使用STL类库。
注意: main函数结束必须返回0
注意: 所有依赖的函数必须明确地在源文件中 #include ， 不能通过工程设置而省略常用头文件。
所有源码必须在同一文件中。调试通过后，拷贝提交。
提交时，注意选择所期望的编译器类型。
1.结果填空 (满分5分)
问题的描述在考生文件夹下对应题号的“题目.txt”中。相关的参考文件在同一目录中。请先阅读题目，不限解决问题的方式，只要求提交结果。
必须通过浏览器提交答案。
2.结果填空 (满分11分)
问题的描述在考生文件夹下对应题号的“题目.txt”中。相关的参考文件在同一目录中。请先阅读题目，不限解决问题的方式，只要求提交结果。
必须通过浏览器提交答案。
3.结果填空 (满分13分)
问题的描述在考生文件夹下对应题号的“题目.txt”中。相关的参考文件在同一目录中。请先阅读题目，不限解决问题的方式，只要求提交结果。
必须通过浏览器提交答案。
4.结果填空 (满分17分)
问题的描述在考生文件夹下对应题号的“题目.txt”中。相关的参考文件在同一目录中。请先阅读题目，不限解决问题的方式，只要求提交结果。
必须通过浏览器提交答案。
5.代码填空 (满分7分)
问题的描述在考生文件夹下对应题号的“题目.txt”中。相关的参考文件在同一目录中。请先阅读题目，不限解决问题的方式。
只要求填写缺失的代码部分，千万不要画蛇添足，填写多余的已有代码或符号。
必须通过浏览器提交答案。
6.代码填空 (满分9分)
问题的描述在考生文件夹下对应题号的“题目.txt”中。相关的参考文件在同一目录中。请先阅读题目，不限解决问题的方式。
只要求填写缺失的代码部分，千万不要画蛇添足，填写多余的已有代码或符号。
必须通过浏览器提交答案。
7.程序设计（满分19分）
问题的描述在考生文件夹下对应题号的“题目.txt”中。相关的参考文件在同一目录中。请先阅读题目，必须通过编程的方式解决问题。
注意：在评卷时使用的输入数据与试卷中给出的示例数据可能是不同的。选手的程序必须是通用的，不能只对试卷中给定的数据有效。
仔细阅读程序的输入、输出要求，千万不要输出没有要求的、多余的内容，例如：“请您输入xx数据：”。
建议仔细阅读示例，不要想当然！
程序处理完一个用例的数据后，立即退出（return 0），千万不要循环等待下一个用例的输入。
程序必须使用标准输入、标准输出，以便于机器评卷时重定向。
对于编程题目，要求选手给出的解答完全符合ANSI C++标准，不能使用诸如绘图、Win32API、中断调用、硬件操作或与操作系统相关的API。
代码中允许使用STL类库。
注意: main函数结尾需要return 0
注意: 所有依赖的函数必须明确地在源文件中 #include ， 不能通过工程设置而省略常用头文件。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
提交时，注意选择所期望的编译器类型。
8.程序设计（满分21分）
问题的描述在考生文件夹下对应题号的“题目.txt”中。相关的参考文件在同一目录中。请先阅读题目，必须通过编程的方式解决问题。
注意事项同上题
9.程序设计（满分23分）
问题的描述在考生文件夹下对应题号的“题目.txt”中。相关的参考文件在同一目录中。请先阅读题目，必须通过编程的方式解决问题。
注意事项同上题
10.程序设计（满分25分）
问题的描述在考生文件夹下对应题号的“题目.txt”中。相关的参考文件在同一目录中。请先阅读题目，必须通过编程的方式解决问题。
注意事项同上题
