写在前面

蓝桥杯省赛将在4月初举行，距离比赛也就剩一个多月的时间。为了提高自己的编程能力，在比赛中取得比较👌的成绩。接下来的一个多月我会在博客中更新蓝桥杯的学习。争取在考前将一些重要的算法过一遍。

蓝桥杯常考的算法我整理到了一张思维导图里面，小伙伴可以看一下噢。

这张蓝桥杯思维导图可能不太全面，以后会经常补充的。。

我是这样想滴，我会对常考的算法做个专题总结，分专题来讲。文章更新的速度呢取决于我刷题的速度啦！ 因为每写一个专题必然要写运用到这种算法的题目啦~鲁迅先生说过 “只讲解算法思想，不实际运用就是在耍流氓”。写蓝桥杯文章的过程是这个样子的，先确定要写哪个专题，然后呢大量刷题，模板题啦，经典题啦，最最重要的是历届的蓝桥杯真题啦。刷完之后呢做总结理清这种算法的基本思路，最后就形成了一篇蓝桥杯备考文章啦。当然文章是要时常更改补充的，因为在刷题的过程中可能对某些算法思想有了新的感悟~也要参加蓝桥杯的小伙伴们可以一起期待噢，关注我一定不会让你失望的。噢还有我参加的是C++组所以呢我写的题解也是C++的。

我的CSDN博客 https://blog.csdn.net/ccevv/

---

好啦接下来进入正题。

我们知道蓝桥杯俗称暴力杯，搜索在蓝桥杯中是最最基本的算法思想。学会DFS和BFS是在蓝桥杯比赛中取得好成绩的基础。我会从这几个方面入手，给小伙伴们详细讲解搜索专题。

本篇的内容主要有以下几个方面噢，小伙伴们可以有个大致了解。

DFS基本思想(DFS+回溯）
深度优先搜索模板
DFS例题
剪枝思想
剪枝思想在DFS中的应用

---

---

一、深度优先搜索(DFS)+回溯

DFS是一种搜索的策略，简单来说就是一条路走到黑。当走到尽头之后就回退到上一个结点，继续一条路走到黑。回退的过程就叫做回溯。
DFS一般采用递归的方式实现。

对递归的详细讲解会在以后出一个独立的专题，小伙伴们可以期待一下噢！

DFS可以用一个递归搜索树来形象描述，那这棵树长什么样子呢，小伙伴们继续往下看。

事实上对所有的合法DFS求解过程都可以把它画成树的形式，死胡同就相当于叶子结点。分岔口就相当于非叶子结点。

对某个DFS类型的题目，不妨把一些状态作为树的结点，问题就变得很直观了。

DFS搜索的顺序是A-B-D-E-C-F。从结点A出发，它有两条路可以走，我们选择最左边那一条，到达结点B，结点B有两个分支，选择最左边那个，到达结点D。结点D没有路可走了也就是到达死胡同了，返回上一个结点B，也就是回溯的过程。B还有一条路可走，到达结点E。同理结点E回溯到结点B，结点B没有分支了，回溯到上一个结点A，结点A还有一个分支可以走，到达结点C,结点C有一个分支到达结点F，结点F是死胡同。至此所有的结点都访问了，搜索结束。

其实DFS的搜索顺序和树的先序遍历是一样的。树的先序遍历就是根左右。

从递归树我们就能看出DFS的时间复杂度是很高的，是$O(2^n)$。所以我们常说暴力搜索嘛，就是因为它时间复杂度太高了，当数据很大时很容易就TLE(超时)的。同时我们还能看出DFS会走遍所有的路径，并且走到死胡同就代表一条完整的路径形成。因此深度优先搜索是一种枚举所有路径，遍历所有情况的搜索策略。

---

二、DFS模板

在备战蓝桥杯的过程中记住一些算法模板还是非常重要滴。

#include <iostream>
using namespace std;
bool check()
{
	...
}
void dfs()
{
	if (满足边界条件)
	{
		
		return;
	}
	for (int i = 0; i < 可扩展的路径数; i++)
	{
		if (check())
		{
			修改现场;
			dfs(下一种情况);
			还原现场;
		}
	}
}	

模板不是固定不变的，我们要根据题目灵活地运用它。

---

三、DFS经典例题

1.模板题——迷宫问题

题目链接

题目分析

迷宫问题是拿来练习DFS与BFS很经典的题目。迷宫问题有很多种问法，比如迷宫从起点到终点有没有路径，有几条，最短路径是多少。

求从起点到终点的方案数显而易见也是要用DFS，遍历所有的情况。我们要考虑这样一个问题，迷宫里的某点(x,y)是否要被访问呢。当这点是障碍物肯定不能访问，该点不在迷宫里面也不能访问，该点访问过了那就不能访问了。(题目中有每个方格最多经过一次)。因此我们需要一个check()函数来判断某一点是否合法。合法我们就去访问该点。

其实这个过程就是一个剪枝的过程，根据题目条件限制，剪掉一些不可能存在解的分支。

另外我们该如何知道某点是障碍点呢，可以设置一个map数组来表示该迷宫。

• 当map[x][y]==1时表示该点是障碍点
• map[x][y]==0表示该点是正常点

AC代码

#include <iostream>
using namespace std;

const int N = 100;

int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};//方向数组技巧
int n, m, T;//n行m列T障碍总数
int ans;//记录方案总数
int sx, sy, fx, fy, l, r;//起点坐标(sx,sy)终点坐标(fx,fy)障碍点坐标(l,r)
bool visited[N][N];//记录某点是否被访问过
int map[N][N];//map[i][j] == 1表示是障碍

bool check(int x, int y)//check某点是否合法
{
    if (x < 1 || x > n || y < 1 || y > m) return false;//该点出界不合法
    if (map[x][y]) return false;//该点是障碍点不合法
    if (visited[x][y]) return false;//该点被访问过不合法
    return true;//其他情况访问合法
}

void dfs(int x, int y)//dfs维护点的坐标参数
{
    if (x == fx && y == fy)//满足边界条件，到达终点
    {
        ans++;//方案数+1
        return;
    }
    for (int i = 0; i < 4; i++)//枚举四个方向
    {
        int newx = x + dx[i];
        int newy = y + dy[i];
        if (check(newx, newy))//该点合法
        {
            visited[x][y] = true;//将(x,y)设置成已访问,修改现场
            dfs(newx, newy);//dfs下一个点
            visited[x][y] = false;//回溯,恢复现场
        }
    }
}

int main()
{
    cin >> n >> m >> T;
    cin >> sx >> sy >> fx >> fy;
    while(T--)
    {
        cin >> l >> r;
        map[l][r] = 1;
    }
    dfs(sx, sy);//从起点开始搜索
    cout << ans << endl;
    return 0;
}

小伙伴们每道例题都要好好看一下AC代码噢，上面有很详细的注释。

这道题还可以优化下空间，可以只用maze数组来表示迷宫，同时记录迷宫内的某点是否访问过。具体见下面的代码。

//空间优化
#include <iostream>
using namespace std;

const int N = 100;

int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};//方向数组
int n, m, T;
int ans;
int sx, sy, fx, fy, l, r;
//bool visited[N][N];
int map[N][N];//map[i][j] == 1表示是障碍
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                          
bool check(int x, int y)//判断某点是否可以访问
{
    if (x < 1 || x > n || y < 1 || y > n) return false;
    if (map[x][y] || map[x][y] == 3 ) return false;//该点是障碍点或已经访问过，不能访问
    //if (visited[x][y]) return false;
    return true;
}

void dfs(int x, int y)
{
    if (x == fx && y == fy)
    {
        ans++;
        return;
    }
    for (int i = 0; i < 4; i++)
    {
        int newx = x + dx[i];
        int newy = y + dy[i];
        if (check(newx, newy))
        {
            map[x][y] = 3;//标记成已访问
            dfs(newx, newy);
            //点(x,y)能访问说明它不是障碍点所以回溯要让map[x][y]=0
            //而不是map[x][y]=1
            map[x][y] = 0;
        }
    }
}
int main()
{
    cin >> n >> m >> T;
    cin >> sx >> sy >> fx >> fy;
    while(T--)
    {
        cin >> l >> r;
        map[l][r] = 1;
    }
    dfs(sx, sy);
    cout << ans << endl;
    return 0;
}

2.01背包问题(DFS暴力搜索)

题目链接

题目分析

01背包问题是一个很经典的问题，它有多种解法。DFS是其中一种，在学习动态规划的时候还会提到它噢。

第i件物品无非就是选和不选两种情况，在搜索的过程中DFS函数必须要记录当前处理的物品编号index，当前背包的容量sumW，当前的总价值sumC。

• 当不选第index个物品时，那么sumW,sumC是不变的，接着处理第index+1个物品，也就是DFS(index+1, sumW, sumC)。
• 当选择第index个物品时，sumW变成sumW+w[index]，sumC变成sumC+v[index]，接着处理第index+1个物品，也就是DFS(index+1, sumW+w[index],sumC+v[index])。边界条件也就是把最后一件物品也处理完了，即index=n（注意默认index从0开始）。

当一条分支结束了该干什么呢，很简单呀就是判断该分支最终满不满足总重量不大于背包容量。即sumW<=v。满足的话我们就更新价值maxvalue，即maxvalue=max(maxvalue,sumC)。

AC代码

//01背包问题的dfs版本
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 10010;
int n, v, maxvalue;
int w[N], c[N];
//DFS维护三个参数，正在选第index个物品，当前的总体积，当前的总价值
void dfs(int index, int sumW, int sumC)
{
    if (index == n)
    {
        if (sumW <= v)
        {
            maxvalue = max(maxvalue, sumC);
        }
        return;
    }
    dfs(index + 1, sumW, sumC);//不选第index个物品
    dfs(index + 1, sumW + w[index], sumC + c[index]);//选第index个物品
}

int main()
{
    cin >> n >> v;
    for (int i = 0; i < n; i++)
    {
        cin >> w[i] >> c[i];
    }
    dfs(0, 0, 0);//开始时对第1件物品进行选择，此时背包重量0价值也是0
    cout << maxvalue << endl;
    return 0;
}

当然了01背包问题如果用DFS来解决的话，当数据比较大时，是不能AC的。这道题会超出时间限制。即便经过剪枝也是无能为力的。

3.回溯——[USACO1.5]八皇后 Checker Challenge

题目链接


题目分析

八皇后问题是学习回溯很经典的例题，这道题是八皇后问题的扩展，N皇后问题。也就是棋盘的大小是任意的。

这道题DFS的思路还是比较清晰的，每行有且只有一个棋子，那么DFS可以记录下当前处理的是第几行的棋子。假设当前处理的是第i行的棋子，那么要枚举处在该行的棋子位置，判断哪个是合法的。
什么样的位置算是合法的呢，这个位置的列还有左对角线，右对角线位置都不能有棋子。那么又该如何表示这些位置呢？我们采用一维数组来分别表示列，左对角线，右对角线。列很好表示就是b[j]，左对角线我们可以发现行减去列的绝对值是恒定的，即c[i-j+n],右对角线行加列是恒定的。即d[i+j]。

小伙伴们可以自己画画图看一看噢~

当某位置放置了棋子，那么就将和它同列同对角线的位置都取为1，即b[j]=1,c[i-j+n]=1,d[i+j]=1。

AC代码

#include <iostream>
using namespace std;

int a[100], b[100], c[100], d[100];//a[]储存解b列c左斜d右斜
int n;//棋盘大小
int ans;

bool check(int i, int j)//检查(i,j)是否合法
{
    if (!b[j] && !c[j - i + n] && !d[j + i]) return true;//b[j],c[i-j+n],d[i+j]为0说明该点可以放置棋子。
    return false;
}

void dfs(int i)//dfs第i行棋子
{   //边界条件
    if (i > n)//dfs完所有的棋子
    {
     	ans++;
        if (ans <= 3)//只要前三个解
        {
            for (int i = 1; i <= n; i++)//输出解
            {
                cout << a[i] << ' ';
                
            }
            cout << endl;  
        }
        return;     
    }
    
        for (int j = 1; j <= n; j++)//枚举一行的所有位置
        {	//(i,j)点满足放棋子的条件，我们就把棋子放在(i,j)点
            if (check(i, j))
            {
                a[i] = j;//把满足解的列号存在a[i]中
                b[j] = 1;//修改现场
                c[ j - i + n] = 1;
                d[j + i] = 1;
                dfs(i + 1);//处理下一行的棋子
                b[j] = 0;//回溯，恢复现场
                c[j - i + n] = 0;
                d[j + i] = 0;
            }
        }
}
int main()
{
    cin >> n;
    dfs(1);
    cout << ans << endl;
    return 0;
}

4.递归实现排列型枚举

题目链接

题目分析

DFS可以用来处理排列组合问题。

对于全排列问题我们可以这样想，第1个位置可以放1~n任意一个数，第2个位置可以放除了放在第1个位置的数以外的任何一个数，以此类推。因此我们可以画出一个递归搜索树，用map[]来表示储存当前排列。DFS函数要记住当前处理的是第index个位置，从1到n进行遍历，看看这个数是否可以放在第index个位置，需要有一个判重数组hashtable[x]来记录x是否在排列里面。

AC代码

#include <iostream>
using namespace std;

const int N = 11;
//map[N]储存当前的排列，hashtable[N]判断某个数是否在排列里
int map[N];
bool hashtable[N];面。
int n;

void dfs(int index)//当前填第index位置
{
    if (index == n + 1)//已经处理完1~n个位置
    {
        for (int i = 1; i <= n; i++)//输出当前排列
        {
            cout << map[i] << ' ';
        }
        cout << endl;
        return;
    }
    for (int i = 1; i <= n; i++)//枚举1~n
    {
        if (hashtable[i] == false)//当i这个数没有填在map中
        {
            map[index] = i;//第index位置填入i这个数
            hashtable[i] = true;//记i在当前排列
            dfs(index + 1);//处理第index+1位置
            //处理完map[index]=i的子问题，恢复现场
            hashtable[i] = false;
            map[index] = 0;
        }
    }
}
int main()
{
    cin >> n;
    dfs(1);//从1这个数开始搜索
    return 0;
}

5.递归实现组合型枚举

题目链接


题目分析
组合和排列的最大区别就是组合不需要考虑顺序，也就是说123和132是一样的。
由于题目要求同一行的数必须按升序排序，因此可以让DFS函数记录当前处理的第index个位置，可以选的最小数start。

虽然参数变成了两个，但是不需要判重数组了。

DFS的思路是这个样子的，假设当前处理的是第index个位置，这个位置可以放置start~n其中任意一个数。接着处理第index+1个位置，这个位置可以放置的最小数是前一位数的下一个数。即i+1~n。

AC代码

#include <iostream>
using namespace std;

const int N = 30;

int map[N];//存储解
int n, m;
//dfs记录当前处理的第index个位置，可以选的最小数start
void dfs(int index, int start)
{
    if (index > m)//m个位置都处理完了
    {
        for (int i = 1; i <= m; i++)//输出方案
        {
            cout << map[i] << " ";
        }
        cout << endl;
        return;
    }
    //第index个位置可以选择start~n里面的数
    for (int i = start; i <= n; i++)
    {
        map[index] = i;
        //处理index+1位置，能选择的最小数是前面选择的数+1
        dfs(index + 1, i + 1);
        //处理完第index位置放置i这个数的子问题后回溯。
        map[index] = 0;
      
    }
}

int main()
{
    cin >> n >> m;
    dfs(1, 1);
    return 0;
}

---

四、剪枝思想

前面也提到过剪枝的概念，现在详细说下剪枝这种东西。我们知道DFS时间复杂度是很高的，如果不进行一些优化的话，在数据很大的情况下很容易就爆TLE。这个时候我们就可以用剪枝这种东西来优化啦~
在进行DFS的过程中对某条可以确定不存在解的分支采用直接剪短的策略。这样会大大降低计算量。一个搜索树剪掉一些分支就形象的叫它剪枝了。
剪枝一般都是利用题目的限制条件来确定哪些分支是不可能存在解的。

---

五、剪枝思想在DFS中的应用

小伙伴们来回忆下01背包问题，我们是在选择完所有物品后才进行判断，看看背包总体积是否超过背包容量。是不是可以在选择的过程中就加入这一判断，这样就可以减少很多的计算量。当选第index件物品时，如果选上它那么背包的总体积就超出背包容量，我们一定不能选了。此时选第index件物品的分支就不可能存在解，直接剪掉。

//DFS维护三个参数，正在选第index个物品，当前的总体积，当前的总价值
void dfs(int index, int sumW, int sumC)
{
    if (index == n)//选择完所有的物品，最终的sumW一定不大于v
    {
        maxvalue = max(maxvalue, sumC);
        return;
    }
    dfs(index + 1, sumW, sumC);//不选第index个物品
    if (sum + w[index] <= v)//剪枝
    {   //选第index个物品
    	dfs(index + 1, sumW + w[index], sumC + c[index]);
    } 
}

小伙伴们再来回忆下前面的组合型枚举问题，我们也可以用到剪枝来优化。可以看出要是剩下的数全都用上也满足不了一共m个数的要求，那么我们直接可以结束这个分支了。即n - start + index < m。

void dfs(int index, int start)
{
	if (n - start + index < m) return;//剪枝
    if (index > m)//m个位置都处理完了
    {
        for (int i = 1; i <= m; i++)//输出方案
        {
            cout << map[i] << " ";
        }
        cout << endl;
        return;
    }
    //第index个位置可以选择start~n里面的数
    for (int i = start; i <= n; i++)
    {
        map[index] = i;
        //处理index+1位置，能选择的最小数是前面选择的数+1
        dfs(index + 1, i + 1);
        //处理完第index位置放置i这个数的子问题后回溯。
        map[index] = 0;
      
    }
}

通过下表我们能看出剪枝之后的运行速度确实快了不少。

---

写在后面

想到啥就说啥了，给备战蓝桥杯的小伙伴们提些建议。

我不推荐大家去leetcode上刷题，因为leetcode的形式和蓝桥杯是不太一样的。力扣只需要写函数，输入输出已经内置好了。蓝桥杯的输入输出是需要自己写的。另外呢力扣主要是面向找工作的，题目是面试用的，不是专门打比赛的。因此题目不太适合蓝桥杯竞赛。当然了里面的题目还是很经典的，专门学某一算法是可以刷力扣的。我给大家推荐几个适合的网站还有书籍。

ACwing网站
洛谷
C语言网蓝桥杯题库
蓝桥杯练习系统
蓝桥杯官网题库

这几个网站和书是我一直在用的，真心推荐给大家~

美好的时光总是短暂的，又到了说再见的时候啦~一键三连支持一下吧！

目录

蓝桥杯算法竞赛大纲
数论相关（Java）
枚举相关（Java）
对象排序（Java）
字符串相关（Java）
排序相关算法（Java）
记忆化搜索（Java）
树论相关（Java）
图论相关（Java）
堆（Java）
贪心（Java）

---

上面的目录是 blog主 整理的对应的 Java 组相关的代码

蓝桥杯算法竞赛大纲：

知识点对应如上，刷题的话可以到蓝桥杯官网刷往年真题。

欢迎回到：遇见蓝桥遇见你，不负代码不负卿！

目录

一、简单模拟

栗子：换酒问题

栗子：按奇偶排序数组

栗子：害死人不偿命的（3n+1）猜想

栗子：挖掘机技术哪家强

二、查找元素

栗子：找 x

三、图形输出

栗子：跟奥巴马一起编程

四、日期处理

栗子：日期差值

五、进制转换

栗子：D 进制的 A+B

六、字符串处理

栗子：回文串

栗子：说反话

七、蓝桥结语：遇见蓝桥遇见你，不负代码不负卿！

---

【前言】

之前有铁汁要求将入门部分也更新一下，比如简单模拟，简单数学部分，这两块在蓝桥杯中考的都不难，但是特别重要，就像我们高考的时候数学试题那前五道选择题，前两道填空题一样，属于送分题，但是对于马虎的同学是致命的，所以要上心哦，这部分内容没有涉及算法，完全只是根据题目描述来进行代码的编写，侧重考查的是代码能力，我们在做这种类型题目的时候一定要认真读题！读题！！题！！！对于模拟题，“题目怎么说，你就怎么做” 。这块内容最好别失分，将这部分的分拿到了，后面的题目就算不会用算法解决，暴力求解也能省三起步！毕竟蓝桥杯的别名就是“暴力杯”嘛！不过要想拿高分还是得把算法学好，求解问题时能事半功倍！！

【声明】 

简单模拟、简单数学这周就会更新结束，下周更新BFS部分，对于DFS、BFS要大量练习哦，蓝桥中涉及的比较多，后面我将贪心、动态规划等更新结束，会开启一个蓝桥冲刺专栏，系统性的刷题，包括历年的真题！笔者已经将路线安排好咯，只不过正在挤时间更新，一起加油鸭！

这部分内容比较简单，但是请铁汁们不要眼高手低哦，希望大家可以动动小手把例题全部自己实现一遍，这对基础代码能力的提升是很重要的！ 

 题型：

• 简单模拟
• 查找元素
• 图形输出
• 日期处理
• 进制转换
• 字符串处理

一、简单模拟

模拟题是一类“题目怎么说，你就怎么做” 的题目，如果实现起来不太麻烦，就可以称之为“简单模拟”这种题目不涉及算法，完全只是根据题目描述来进行代码的编写，所以考查的是代码能力，下面先举三个例子：

栗子：换酒问题

题目描述：

小区便利店正在促销，用 numExchange 个空酒瓶可以兑换一瓶新酒。你购入了 numBottles 瓶酒。

如果喝掉了酒瓶中的酒，那么酒瓶就会变成空的。

请你计算 最多 能喝到多少瓶酒。

示例1：

  

输入：numBottles = 9, numExchange = 3
输出：13
解释：你可以用 3 个空酒瓶兑换 1 瓶酒。
所以最多能喝到 9 + 3 + 1 = 13 瓶酒。

示例2：

输入：numBottles = 15, numExchange = 4
输出：19
解释：你可以用 4 个空酒瓶兑换 1 瓶酒。
所以最多能喝到 15 + 3 + 1 = 19 瓶酒。

思路：

如果有b 瓶酒，并且规定e 个空瓶换一瓶酒，首先我们一定可以喝到 b 瓶酒，剩下 b 个空瓶。接下来我们可以拿瓶子换酒，每次拿出 e 个瓶子换一瓶酒，然后再喝完这瓶酒，得到一个空瓶。以此类推，我们可以统计得到答案。

代码执行：

int numWaterBottles(int numBottles, int numExchange){
    int bottle = numBottles;//空瓶子的数量
    int ans = numBottles;//总共喝的酒
    while(bottle >= numExchange)//空瓶子只要大于numExchange,循环就要继续
    {
        bottle -= numExchange;
        ans++;
        bottle++;
    }
    return ans;
}

栗子：按奇偶排序数组

题目描述：

输入一个长度为 n 整数数组，数组里面不含有相同的元素，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前面部分，所有的偶数位于数组的后面部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

示例1：

输入：[1,2,3,4]
返回值：[1,3,2,4]

示例2：

输入：[2,4,6,5,7]
返回值：[5,7,2,4,6]

思路：

题目比较简单，只需要遍历两遍数组即可

代码执行：

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param array int整型一维数组 
 * @param arrayLen int array数组长度
 * @return int整型一维数组
 * @return int* returnSize 返回数组行数
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
int* reOrderArray(int* array, int arrayLen, int* returnSize ) {
    // write code here
    int* ans = (int*)malloc(sizeof(int) * arrayLen);
    *returnSize = arrayLen;
    int i = 0;
    int j = 0;
    for(i = 0; i < arrayLen; i++)
    {
        if(array[i] % 2)
        {
            ans[j++] = array[i];
        }
    }
    for(i = 0; i < arrayLen; i++)
    {
        if(!(array[i] % 2))
        {
            ans[j++] = array[i];
        }
    }
    return ans;
}

栗子：害死人不偿命的（3n+1）猜想

题目描述：

卡拉兹猜想：

对任意一个自然数n ,如果它是偶数，那么把它砍掉一半；如果它是奇数，那么把（3n+1）砍掉一半。这样一直反复砍下去，最后一定在某一步得到n = 1 。卡拉兹在1950年的世界数学家大会上公布了这个猜想，传说当时耶鲁大学师生齐动员，平明想证明这个貌似很荒唐......

此处并非要证明卡拉兹猜想，而是对给定的任一不超过1000的正整数n, 简单的数一下需要多少步才能得到 n = 1?这里就拿n = 1000举例。

思路：

用while循环语句反复判断n 是否为1：

• 如果 n == 1，则退出循环；
• 如果 n != 1，则判断n 是否为偶数，如果是偶数，则令n 除以2；否则令n 为(3*n+1)/2, 之后令计数器step++;

这样退出循环后，step的值就是需要的答案。

代码执行：

#include<stdio.h>

int main()
{
	int n = 1000;
	int step = 0;

	while (n != 1)
	{
		if (!(n % 2))//偶数
		{
			n /= 2;
		}
		else//奇数
		{
			n = (3 * n + 1) / 2;
		}
		step++;
	}

	printf("%d\n", step);//输出72
	return 0;
}

栗子：挖掘机技术哪家强

题目描述：

为了用事实说明挖掘机技术到底哪家强，组织了一场挖掘机技能大赛。请根据比赛结果统计出技能最强的哪个学校。

输入格式：

在第一行给出不超过10^5 的正整数N ，即参赛人数。随后N 行，每行给出一位参赛者的信息和成绩，包括其所代表的学校的编号及其比赛成绩，中间以空格分隔（注意，学校从1开始连续编号，比赛成绩百分制）

输出格式：

在一行中给出总得分最高的学校的编号及其总分，中间以空格分隔。题目保证答案唯一，没有并列。

输入样例：

6

3 65

2 80

1 100

2 70

3 40

3 0

输出样例：

2 150

思路：

• 令数组school[MAXN]记录每个学校的总分，初值为0，对每一个读入的学校schID与其对应的分数score，令school[schID] += score;
• 令变量k 纪录最高总分的学校编号，变量max纪录最高总分，初值为-1，由于学校是连续编号的，因此枚举编号1~N，不断更新k 和max 即可。

代码执行：

#include<stdio.h>
 
#define MAXN 100010
int school[MAXN] = { 0 };//记录每个学校的总分
 
int main()
{
	int n = 0;
	int schID = 0;//学校编号
	int score = 0;//分数
	scanf("%d", &n);//参赛人数
	for (int i = 0; i < n; i++)//读入每一位参赛人员信息
	{
		scanf("%d %d", &schID, &score);
		school[schID] += score;//学校schID的总分增加score
	}
	int k = 0;//用于记录最高总分的学校编号
	int max = -1;//用于记录最高总分
	for (int i = 1; i <= n; i++)//由于学校是从1开始连续编号的，所以范围是1~N,其中包括N
	{
		if (school[i] > max)
		{
			max = school[i];
			k = i;
		}
	}
	printf("%d %d\n", k, max);
	return 0;
}

二、查找元素

有时候我们会遇到这样一种情况：给定一些元素，然后查找某个满足条件的元素。这就是查找操作需要做的事情。查找是学习写代码的一项基本功，是肯定需要掌握的。一般来说，如果需要在一个比较小范围的数据集里进行查找，那么直接遍历每一个数据即可；如果需要查找的范围比较大，那么可以用二分查找等算法进行更加快速的查找。这里就讲一下在小范围的数据集里查找指定元素。

二分查找算法之前已经更新咯，还没康的铁汁快点去康康吧。

蓝桥杯算法竞赛系列第四章——二分算法_安然无虞的博客-CSDN博客

栗子：找 x

题目描述：

输入一个数n (n >> 1 && n << 200)，然后输入n 个数值各不相同的数，再输入一个值x，输出这个值在这个数组中的下标（下标从0开始，若不在数组中则输出-1）

输入格式：

测试数据有多组，输入n（n>=1 && n<=200）,接着输入n 个数，然后输入x

【敲黑板】：对于这种输入格式中说明或者要求测试数据有多组时，要写成循环，直到读取到EOF停止。

输出格式：

对于每组输入，请输出结果。

样例输入：

4
1 2 3 4
3

样例输出：

2

思路：

题目给定了n 个互不相同的数，然后需要从中寻找值为x 的数的下标，因此可以设定一个数组a ，用来存放这n 个数。然后遍历数组a ，寻找某个下标k ，使得a[k] == x 成立，如果找到，则输出k ，并退出查询；如果当遍历完数组之后还没有找到x ，那么输出-1。 

代码执行：

#include<stdio.h>

#define MAXN 210
int a[MAXN] = { 0 };

int main()
{
	int n = 0;
	int x = 0;
	while (scanf("%d", &n) != EOF)//考虑到多组输入，所以写成循环的形式
	{
		for (int i = 0; i < n; i++)
		{
			scanf("%d", &a[i]);//输入n 个数
		}
		scanf("%d", &x);//输入欲查询的数
		int k = 0;//下标
		for (k = 0; k < n; k++)
		{
			if (a[k] == x)//如果找到了x，输出对应的下标
			{
				printf("%d\n", k);
				break;//找到了之后记得退出查询
			}
		}
		if (k == n)//如果没有找到，输出-1
		{
			printf("-1\n");
		}
	}
	return 0;
}

三、图形输出

在有些题目中，题目会给定一些规则，需要考生根据规则来进行画图。所谓图形，其实是由若干字符组成的，因此只需要弄清楚规则就能编写代码。这种题目一般有两种做法：

1. 通过规律，直接进行输出；
2. 定义一个二维字符数组，通过规律填充之，然后输出整个二维数组   

栗子：跟奥巴马一起编程

题目描述：

美国总统奥巴马不仅呼吁所有人都学习编程，甚至亲自编写代码，成为美国历史上首位编写计算机代码的总统。2014年底，为庆祝“计算机科学教育周” 正式启动，奥巴马编写了一个简单的计算机程序——在屏幕上画一个正方形。 

输入格式：

在一行中给出正方形边长N（N >= 3 && N <= 20）和组成正方形边的某种字符C，间隔一个空格。 

输出格式：

由给定的字符C画出的正方形。当时注意到行间距比列间距大，所以为了让结果看上去更像正方形，所输出的行数实际上是列数的50%（四舍五入取整） 

样例输入：

10 7

 样例输出：

7777777777
7        7
7        7
7        7
7777777777

思路：

由于行数是列数的一半（四舍五入取整），因此当列数col 是奇数时，行数row 就是col / 2 + 1；当列数col 是偶数时，row 就是col / 2。 

代码执行：

#include<stdio.h>

int main()
{
	int row = 0;//行
	int col = 0;//列
	char ch = 0;//符号
	//输入列数、字符
	scanf("%d %c", &col, &ch);//注意哦，输入空格时%c也会读取的，所以中间要自动加上空格
	//判断col奇偶性，并且是奇数时要向上取整
	if (col % 2)
	{
		row = col / 2 + 1;
	}
	else
	{
		row = col / 2;
	}
	int i = 0;
	int j = 0;
	//第一行,col个字符
	for (i = 0; i < col; i++)
	{
		printf("%c", ch);
	}
	printf("\n");
	//第2~row-1行（注意这一层循环的思想）
	for (i = 2; i < row; i++)
	{
		printf("%c", ch);//每行的第一个指定的字符
		for (j = 0; j < col - 2; j++)//每行的第2~col-1列
		{
			printf(" ");//col-2个空格
		}
		printf("%c", ch);
		printf("\n");
	}
	//最后一行,col个字符
	for (i = 0; i < col; i++)
	{
		printf("%c", ch);
	}
	return 0;
}

四、日期处理

日期处理的问题总是会让很多人感到头疼，因为在这种问题中，总是需要处理平年和闰年时的情况（由此产生二月的天数区别）、大约和小月的问题，因此细节比较繁杂。但是只要细心处理细节，一般都能很好的解决这类问题。

栗子：日期差值

题目描述：

有两个日期，求这两个日期之间的天数，如果两个日期是连续的，则规定它们之间的天数为两天。

输入格式：

有多组数据，每组数据有两行，分别表示两个日期，形式为YYYYMMDD。

输出格式：

每组数据输出一行，即日期差值

样例输入：

20130101

20130105

样例输出：

5

思路：

不妨假设第一个日期早于第二个日期（否则进行交换）。

这种求日期之间相差天数的题目有一个很直接的思路，即令日期不断加一天，直到第一个日期等于第二个日期为止，即可统计出答案。

具体处理时，如果当加上一天之后天数d 等于当前月份m 所拥有的的天数加1，那么就令月份m 加1、同时置天数d 为1号（即把日期变为下个月的1号）；如果此时月份m 变成了13，那么就令年份y 加1、同时置月份m 为1月（即把日期变成下一年的1月）

为了方便直接取出每个月的天数不妨给定一个二维数组 int month[13][2]，用来存放每个月的天数，其中第二维用0表示平年，1表示闰年，然后，再想想为什么把一维赋为13？

其实还有一种比较快的方法，在这里笔者就不给出咯，有兴趣的铁汁可以了解一下，欢迎留言交流哦，有时间笔者都会回的。

代码执行：

#include<stdio.h>
//#include<stdbool.h>
//平年和闰年每个月的天数
//之所以将一维写成13，是因为保证二维数组的下标与我们生活中的月份相对应，方便处理
int month[13][2] = { {0,0},{31,31},{28,29},{31,31},{30,30},{31,31},{30,30},{31,31},{31,31},{30,30},{31,31},{30,30},{31,31} };

bool isLeap(int year)
{
	return ((year % 4 == 0 && year % 100 != 0) || (year % 400 == 0));
}

int main()
{
	int time1, y1, m1, d1;
	int time2, y2, m2, d2;
	scanf("%d %d", &time1, &time2);
	if (time1 > time2)//设定time1早于time2，也就是说数字也它小，否则交换它们的值
	{
		int temp = time1;
		time1 = time2;
		time2 = temp;
	}
	y1 = time1 / 10000, m1 = time1 % 10000 / 100, d1 = time1 % 100;
	y2 = time2 / 10000, m2 = time2 % 10000 / 100, d2 = time2 % 100;
	int ans = 1;//记录结果,之所以初始值为1，为了满足“当两个日期是连续的，规定它们之间的天数是2天”这个条件
	//第一个日期没有达到第二个日期时进行循环
	//即!((y1 == y2)&&(m1 == m2)&&(d1 == d2))
	while (y1 < y2 || m1 < m2 || d1 < d2)
	{
		d1++;//天数加1
		if (d1 == month[m1][isLeap(y1)] + 1)//满当月天数
		{
			m1++;//日期变成下个月的1号
			d1 = 1;
		}
		if (m1 == 13)//月份满12个月
		{
			y1++;//日期变成下一年的1月
			m1 = 1;
		}
		ans++;//累计
	}
	printf("%d\n", ans);//输出结果
}

其实逻辑很简单，现在看看去年蓝桥杯看的一道分值五分的真题： 

纪念日（5分）

题目描述：
2020 年 7 月 1 日是中国 共 产 党 成立 99 周年纪念日。
中国 共 产 党 成立于 1921 年 7 月 23 日。
请问从 1921 年 7 月 23 日中午 12 时到 2020 年 7 月 1 日中午 12 时一共包含多少分钟？

其实历年来这样的题目比比皆是，所以说，送分题，铁汁们一定要好好拿下！ 

  

五、进制转换

日常生活中人们使用的数字一般都是十进制，而计算机使用的进制是二进制，另外还有八进制、十六进制以及各种数字的进制，那么这就会产生一个问题：对两个不同进制，应该如何进行相互转换呢？下面请听笔者慢慢道来... 

对于一个P进制的数，如果要转换成Q进制，需要分为两步：

1. 将P进制数x 转换为十进制数y
2. 将十进制数y 转换为Q进制数z

第一步：将P进制数x 转换为十进制数y

对一个十进制数 a = d1d2...dn，它可以写成这个形式：

a = d1 * 10^(n-1) + d2 * 10^(n-2) + ... + dn * 10^0

同样的，如果P进制数x 为a1a2...an，用下面这种方法即可转换为十进制数 y:

y = a1 * P^(n-1) + a2 * P^(n-2) + ... an * P^0

上面的公式用循环实现：

int y = 0;
int pro = 1;//pro在循环中会不断乘以P，得到P^0(1),P^1,P^2,...
while (x != 0)
{
	y = y + (x % 10) * pro;//x % 10 是为了每次获取x 的个位数
	x = x / 10;//去掉x 的个位
	pro = pro * P;
}

第二步：将十进制数y 转换为Q进制数 z

采用“除基取余法”。所谓“基”，是指将要转换成的进制Q，因此除基取余法的意思就是每次将待转换数除以Q，然后将得到的余数作为低位存储，而商则继续除以Q并进行上面的操作，最后当商为0时，将所有位从高到低输出就可以得到z 。 

 举一个例子，现在将十进制数11转换为二进制数：

11 除以2，得商为5，余数为1；

5 除以2，得商为2，余数为1；

2 除以2，得商为1，余数为0；

1 除以2，得商为0，余数为1，算法终止；

将余数从后往前输出，得1011即为11 的二进制数。

由此可以得到实现的代码（将十进制数y 转换为Q进制，结果存放于数组中），想想为什么存放在数组中？

int z[40] = { 0 };//数组z 存放Q进制数y 的每一位，num 为位数
int num = 0;

do
{
	z[num] = y % Q;//除基取余
	num++;
	y = y / Q;

} while (y != 0);//当商不为0进行循环

这样z 数组从高位z[num - 1]到低位 z[0]即为Q进制z，进制转换完成。值得注意的是，代码中使用do...while()语句而不是while语句的原因是：如果十进制数y 恰好等于0，那么使用while语句将使循环直接跳出，导致结果出错（正确结果应该是数组z 中存放了z[0] = 0） 

栗子：D 进制的 A+B

题目描述：

输入两个非负十进制整数A和B（<= 2^30 - 1）以及D（进制数），输出A+B的D(2~10)进制数

输入格式：

在一行中依次给出三个整数A、B和D（进制数）

输出格式：

A+B的D进制数

输入样例：

123 456 8

输出样例：

1103

思路：

先计算A+B（此时为十进制），然后把结果转化为D进制，而十进制转化为D进制的过程可以直接进行“除基取余法”

代码执行：

#include<stdio.h>

int main()
{
	int A = 0;
	int B = 0;
	int D = 0;
	int z[40] = { 0 };//存放D进制的每一位
	scanf("%d %d %d", &A, &B, &D);
	int y = A + B;
	int n = 0;
	do
	{
		z[n++] = y % D;
		y /= D;
	} while (y != 0);

	for (int i = n - 1; i >= 0; i--)//从高位到低位进行输出
	{
		printf("%d", z[i]);
	}
	return 0;
}

六、字符串处理

字符串处理题在考试中十分常见，也是能很好体现代码能力的一种题型。本来笔者想把它专门弄成一章的，但是考虑到进度的问题就没有这么做，等到后面再看看能不能挤出时间来全面总结一下字符串相关问题。对于这种题型，一般需要仔细分析清楚题目中的输入和输出格式才能顺利解决题目。在有些题目中，可能实现逻辑会非常麻烦，而且可能会有许多细节和边界情况，因此对代码能力较弱的考生是很不利的。此类题目需要多做多想，积累经验。 

栗子：回文串

题目描述：

读入一串字符，判断是否是“回文串”。“回文串” 是一个正读和反读都一样的字符串，比如“level” 或者 “noon” 就是回文串。  

输入格式：

一行字符串，长度不超过255 

输出格式：

如果是回文串，输出“YES”，否则输出“NO” 

样例输入：

12321

样例输出：

YES

思路：

假设字符串str 的下标是从0 开始的，由于“回文串” 是正读和反读都一样的字符串，因此只需要遍历字符串的前一半（注意：不需要取到 i == len / 2），如果出现字符str[i]不等于其对称位置str[len - 1 - i]，就说明这个字符串不是回文串；如果前一半的所有字符str[i] 都等于对称位置的str[len - 1 - i]，那么就说明这个字符串是“回文串” 

代码执行：

#include<stdio.h>
#include<string.h>

#define MAXN 256

//判断字符串str是否是回文串
bool judge(char* str)
{
	int len = strlen(str);
	int i = 0;
	for (i = 0; i < len / 2; i++)
	{
		if (str[i] != str[len - 1 - i])
		{
			return false;
		}
	}
	return true;
}

int main()
{
	char str[MAXN] = { 0 };
	while (gets(str))//读入字符串
	{
		bool flag = judge(str);
		if (flag == true)
			printf("YES\n");
		else
			printf("NO\n")
	}
	return 0;
}

栗子：说反话

题目描述：

给定英文一个句子，要求编写程序，将句中所有单词按颠倒顺序输出 

输入格式：

测试输入包含一个测试用例，在一行给出总长度不超过80的字符串。字符串由若干单词和若干空格组成，其中单词是由英文字母（大小写有区分）组成的字符串，单词之间用一个空格分开 

输出格式：

每个测试用例的输出占一行，输出倒序后的句子 

样例输入：

Hello World Here I Come

样例输出：

Come I Here World Hello

思路：

使用gets函数读入一整行，（想想为什么不用scanf()？），从左至右枚举每一个字符，以空格为分隔符对单词进行划分，并按照顺序存放到二维字符数组中，最后按单词输入顺序的逆序来输出所有单词。 

【注意点】：

• 最后一个单词之后输出空格会导致“格式错误”；
• 由于PAT是单点测试，因此产生了下面这种更简洁的方法，即使用EOF来判断单词是否已经输入完毕。

#include<stdio.h>

int main()
{
	int num = 0;
	char ans[90][90] = { 0 };
	while (scanf("%s", ans[num]) != EOF)//想想为什么不要&
	{
		num++;
	}
	for (int i = num - 1; i >= 0; i--)//倒着输出单词
	{
		printf("%s\n", ans[i]);
		if (i > 0)//注意这个条件
		{
			printf(" ");
		}
	}
	return 0;
}

要注意的是，在黑框中手动输入时，系统并不知道什么时候到达了所谓的“文件末尾”，因此需要用<ctr + Z>组合键然后按<Enter>键的方式来告诉系统已经到了EOF，这样系统才会结束while。  

#include<stdio.h>
#include<string.h>

int main()
{
	char str[90] = { 0 };
	gets_s(str);
	int len = strlen(str);
	int r = 0;//行
	int h = 0;//列
	char ans[90][90] = { 0 };//ans[0]~ans[r]存放单词
	for (int i = 0; i < len; i++)
	{
		if (str[i] != ' ')//如果不是空格，则存放至ans[r][h],并令h++
		{
			ans[r][h] = str[i];
			h++;
		}
		else//如果是空格，说明一个单词结束，行r++,列h 恢复至0
		{
			ans[r][h] = '\0';//末尾是结束标志\0
			r++;
			h = 0;
		}	
	}
	for (int i = r; i >= 0; i--)//倒着输出单词即可
	{
		printf("%s", ans[i]);
		if (i > 0)
			printf(" ");
	}

	return 0;
}

七、蓝桥结语：遇见蓝桥遇见你，不负代码不负卿！

上面的题目都很简单，所以铁汁们都自己实现一遍哈，不能懒惰哦，这部分的分数是必须要拿到的，冲冲冲鸭！

最后的最后，请求老铁给笔者来个三连吧，万字博文，码字不易，求求啦。