23-01-07
蓝桥杯day2
CH2 杂题
一、填空题
所谓杂题是指没有明确的解题算法，通过思考寻找最简单的解题路径。解题方式包括但不限于手算，编程，excel和简单的python程序
对于一些填空题，手算有时候更加方便快捷，当然手快选手除外。除了编程和手算，我们还可以合理利用电脑上的其他程序来进行计算。比如excel，计算器，word等。
例题1:《门牌制作》
题意：1-2020所有数字中有多少个2？
解题思路：显然，我们可以通过编程，循环mod10（类似day1中例题）来确定每一位是否是2并记录。除此之外，我们还可以输出1-2020，将其复制到word中，通过查找和替换来确定2的数量。或者在excel中下拉自动填充到2020。这两种方法对比编程来说可能更加方便，也不用再查找bug。
要合理的利用这些工具，帮助我们快速的解决填空题，腾出时间来处理后面的编程大题。
例题2：《卡片》
题意：有0-9，10种卡片，每种卡片2021张。问，最多可以用这些卡片组成1-多少的正整数。（如，0-9各30张最多可以拼到10）
解题思路：题干中明确写道建议使用计算机编程，确实，对于手快的，编程可能更加合适。书中依然使用excel进行解题，但书中写道“先估计可以拼出3000多个数”。对于我这种本b是估计不出来的，我可能更倾向于编程。编程的思路也类似与day1种的例题。循环每一位，记录cnt超过或等于时退出。如果超过则减一，如果相等则直接输出当前的i。
书中还给了python的代码。对于这种小题来说，python作为高级语言确实十分的方便，也更容易书写。大学生掌握一些python几千也是必须的。所以我建议大家可以稍微学习一下python语法，比赛时有可能会有奇效。但可能性价比不高，因为蓝桥杯不像xcpc，可以使用不同的编程语言提交程序。python只能用于解决填空题（或者写对拍？），不能在大题中使用，而填空题加起来才10分，相比于学习的付出，性价比不高，所以不用特地为此学习。只是之后如果有需求，不如早些以此为契机。
python代码：
s=['0','1','2','3','4','5','6','7','8','9']*2021
for i in range(1,10000):
a=list(str(i))
try:
for j in a: s.remove(j)
except:
print(i-1)
break
python代码确实非常的方便，直接进行模拟拼数字的过程，当找不到其中一种卡片时，就输出上一个数字。数组直接*2021、“j in a”、“s.remove(j)”这种操作时间复杂度很高，但也非常方便，确实是解决填空题的最优通解。
1.直接手模
有些填空题可以直接手动模拟来的得到答案，属于是最简单的一类题。
例题：《迷宫》
题意：在所给的地图中，每个位置有L（向左）、R、U（向上）、D四类指示，每个位置有个人，按指示走，多少人可以走出来。
解题思路：对于这道原题来说，100个位置，完全可以手动模拟一遍，但手模还是很费时间的。只针对这道题，可以用DFS来搜索，遍历每个位置，对可以走出去的人计数。两种方法个人感觉用时应该差不多。再进行思考，我们是否需要把所有位置都遍历呢？当一个人走不出去时，这个人走过的所有位置，都是走不出去的。这样想的话就很明显了。这个问题是闭环问题。
拓展：
即，给出一个有向图，问有多少个点不在环内。这样我们就把这个抽象成图论的一类问题。我们可以用记忆化搜索或者并查集、spfa这些算法来求解。当然对于数据量小的问题，还是可以用dfs来计算。单纯dfs的时间复杂度为O(n^2)（n为点数）。加上记忆化等操作可以优化为O(n)
下面给出纯暴力和带有简单标记的两种解法。
01-09 更新
暴力解法：暴力解法中也需要添加简单的vis标记。因为人可能会在途中进入循环，虽然不会回到起点但是还是会在环中转圈，这时候我们需要vis标记已经走过的地方，return之后清除标记。
#include<bits/stdc++.h>
using namespace std;
const int N=110;//此算法在1s的时间内最多处理m和n的乘积为10000的数据量
int n,m;
char mp[N][N];
char dir[4]={'L','R','U','D'};//四个方向记录下来，方便if判断
int ans=0;
bool vis[N][N];
void dfs(int x,int y){
if(vis[x][y]==1)//如果之前访问过就return
return;
else
vis[x][y]=1;
if(mp[x][y]==dir[0]){
if(y-1<0){//超出边界ans++
ans++;
return;
}
else{
dfs(x,y-1);//还在图内则递归判断
vis[x][y-1]=0;//判断完成后清除标记
}
}
else if(mp[x][y]==dir[1]){
if(y+1>=m){
ans++;
return;
}
else{
dfs(x,y+1);
vis[x][y+1]=0;
}
}
else if(mp[x][y]==dir[2]){
if(x-1<0){
ans++;
return;
}
else{
dfs(x-1,y);
vis[x-1][y]=0;
}
}
else if(mp[x][y]==dir[3]){
if(x+1>=n){
ans++;
return;
}
else{
dfs(x+1,y);
vis[x+1][y]=0;
}
}
}
int main(){
scanf("%d%d",&n,&m);//n为行数m为列数
for(int i=0;i<=n;i++){
for(int j=0;j<=m;j++)
vis[i][j]=0;
}
for(int i=0;i<n;i++){
scanf("%s",&mp[i]);
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
dfs(i,j);
vis[i][j]=0;
}
}
printf("%d\n",ans);
return 0;
}
非暴力解法可以使用并查集来进行求解。在之后碰到并查集算法时再以此举例。
