蓝桥杯刷题

  蓝桥杯刷题思路解析：

目录

数字三角形：题目描述

思路解析：

代码示例：

冒泡排序逆推导：题目描述

  思路解析：

代码示例：

  跑步锻炼：题目描述

  思路解析：

代码示例：

货品的摆放问题：题目描述

  思路解析：

代码示例：

牌型种类：题目描述

  思路解析：

    一：暴力计算

代码示例：

    二：递归

代码示例：

---

数字三角形：题目描述

思路解析：

   这道题的主要思想就是发现一个规律。由于题目中要求：向左走的步数和向右走的步数相差不大于1。根据多次测试可以得出：每一次最后的落点都会到达最中间的位置上，所以我们只需要进行前面三角形的累加计算，最后求出最后一行的中间较大的数据即可。

  我们可以创建一个新的数组用于保存计算产生的结果，测试一组数据的值可以发现最左边和最右边的一列数据为前面的数据之和。但是其他的位置需要进行判断，我们需要选择较大的数据和我们的数据进行相加才可以得到最长的路径。

代码示例：

#include
#include
using namespace std;
int main()
{
	//创建两个vector对象用于数据的处理
	int n = 0;
	cin >> n;
	vector<int> tmp(n, 0);
	vectorint>> ret(n, tmp);
	//向数组当中传入数据
	int i = 0, j = 0;
	for (i = 0; i < n; i++)
	{
		for (j = 0; j <= i; j++)
		{
			cin >> ret[i][j];
		}
	}
	//输入完成数据之后，只需要将数组当中的数据进行处理即可得到目标的结果
	vectorint>> rest(n, tmp);
	//最左边和最右边的数据都是上一个数组相加，其余的需要选择左右较大的数据进行计算
	rest[0][0] = ret[0][0];
	for (i = 1; i < n; i++)
	{
		for (j = 0; j <= i; j++)
		{
			if (j == 0 )
			{
				rest[i][j] = rest[i - 1][j] + ret[i][j];
			}
			else if (j == i)
			{
				rest[i][j] = rest[i - 1][j - 1] + ret[i][j];
			}
			else
			{
				rest[i][j] = max(rest[i - 1][j], rest[i - 1][j - 1]) + ret[i][j];
			}
		}
	}
	//求完和之后，只需要找最后一排最中间的数据即可。如果n是偶数就找中间的那个较大的数
	if (n % 2 == 0)
		cout << max(rest[n - 1][n / 2], rest[n - 1][(n - 1) / 2]);
	else
		cout << rest[n - 1][n / 2];
	return 0;
}

冒泡排序逆推导：题目描述

  思路解析：

  根据完成冒泡排序所需要进行的操作进行逆推导，一个无序的数组想要经过冒泡排序将一个数据排到应处的位置最多（要求字符串为逆序状态）需要进行n-1次交换，一直到最后两个数据只进行1次交换。所以总次数就为一个数列根据公式可以得到总次数为：(n-1+1) * (n-1) / 2 = n * (n-1) / 2

  我们可以带入数据求得想要进行100次交换最少需要有15个数据。15*14 / 2=105。所以我们想要经过100次交换就的到目标的有序字符串需要提前进行5次交换操作。

  由于我们要求字典序最小。所谓的字典序最小也就是平常我们比较字符串比较所进行的操作，第一个字母比较大小，返回最小的。第一个字符相等就继续比较后面的，以此类推。

  所以我们只需要将第六个数据（第六个数据需要经过五次交换才到达应有的位置）提到最前面的位置即可。

代码示例：

#include
using namespace std;
int main()
{
	//由冒泡排序的基本原理可以得出对于一个无序数组最多需要进行n(n-1)/2次交换，所以可以
	//推得想要进行100次交换最少需要15个字符15*14/2=105
	//所以我们只需要将十五个字符逆序输出并调整第六个字符到第一位即可。
	cout << "jonmlkihgfedcba" << endl;
	return 0;
}

  跑步锻炼：题目描述

  思路解析：

  主要思路就是将每天的跑步数量泛化，也就是将每一天跑步的米数都看成1，等到符合一定的条件的时候将米数再加1，这样可以简化对题目程序的编写。

代码示例：

#include
using namespace std;
 
bool isLeapYear(int year)
{
	if (year % 400 == 0 || (year % 100 != 0 && year % 4 == 0))
	{
		return true;
	}
	return false;
}
 
int main()
{
	int year = 2000;
	int week = 6;
	int miles = 0;
	int monthDay[13] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };
	int i = 0;
	while (year <= 2020)
	{
		if (isLeapYear(year))
		{
			monthDay[2] = 29;
		}
		else
		{
			monthDay[2] = 28;
		}
		for (i = 1; i <= 12; i++)
		{
			int j = 0;
			for (j = 1; j <= monthDay[i]; j++)
			{
				miles++;
				if (j==1|| week == 1)
					miles++;
				week++;
				if (week == 8)
					week = 1;
				if (year == 2020 && i == 10 && j == 1)
				{
					cout << miles << endl;
					return 0;
				}
			}
		}
		year++;
	}
	return 0;
}

货品的摆放问题：题目描述

  思路解析：

  这道题虽然看起来很简单，但是蕴含着一些关于蓝桥杯题目的重要的思想：想要解决蓝桥杯的题目，不能完全像我们平时写程序那样采用看起来很神奇，但是实现起来很复杂的算法。针对于蓝桥杯的题目来说，我们最重要的是再指定的时间和空间的范围内得到指定的答案。

  所以我们最主要用到的就是暴力计算，再加上一些些的代码的优化。就像我们这道题目当中的：我们先将数字分解成一个个质数，分解质数的时候需要使用一点优化，完全暴算会超过时间。但是后面的选择匹配的数据上面我们要是再想优化的话，不是不可以但是会很复杂，所以我们通常情况下会直接暴力匹配。查找三遍数组当中的内容，选出一组符合条件的即可。

代码示例：

#include
#include
#include
using namespace std;
 
int main()
{
	long long number = 2021041820210418;
	//number的质数有哪些
	vector<long long> ret;
	for (int i = 1; i <= sqrt(number); i++)
	{
		if (number % i == 0)
		{
			ret.push_back(i);
			ret.push_back(number / i);
		}
	}
	int count = 0;
	for (auto e : ret)     //尽量不要绕着来，能暴力就尝试暴力计算
	{
		for (auto x : ret)
		{
			for (auto n : ret)
			{
				if (e * x * n == number)
				{
					count++;
				}
			}
		}
	}
	cout << count;
	return 0;
}

牌型种类：题目描述

  思路解析：

  这道题目的思路有两个，但是本质上没有什么区别，但是递归写起来会更简短一点，暴力计算写起来虽然会多一点，但是思路简单不需要思考，只需要想到这种解法即可。

    一：暴力计算

 因为每一种牌都有四张，所以我们拿到这一种牌的张数只可能是 0 - 4 这五种情况。所以我们可以使用循环的方式表示每一种牌，例如 for(int i=0;i<=4;i++) 之后再通过嵌套，一共有十三层。表示十三种牌。之后将每一种的牌的张数加起来等于13，就代表这是一种牌的组合。由于每一次都有牌不一样所以也不用担心重复的情况发生。

代码示例：

#include
using namespace std;
 
int count = 0;
void cobin(int number,int cards)
{
	if (number > 13 || cards > 13)
		return;
	if (cards == 13)
	{
		::count++;
	}
	else
	{
		for (int i = 0; i <= 4; i++)
		{
			cobin(number + 1, cards + i);
		}
	}
	return;
}
int main()
{
	cobin(0, 0);
	cout << ::count << endl;
	return 0;
}

    二：递归

  之后就是我们的递归的写法，本质上的思路和我们的暴力计算很像，也是将每一种牌看成从 0 - 4 五种情况。如果手牌的数量等于13就将组合数量加一，如果手牌的数量大于13就直接抛弃。我们可以将13种牌分为从1-13十三个数字。如果数字超过13同样直接返回,（需要注意的是我们在传参的时候由于第一次传参的值无法进行四次循环，进行四次循环的是传参的值加一，所以我们需要传入0作为参数，实质上表示牌的点数的数字为 1-13）如果是普通的情况就进行从0-4五次遍历，表示这一种牌总共可能会那几张牌。之后将参数修改为牌的数字加一，以及张数加 i 即可。 

代码示例：

#include
using namespace std;
 
int main()
{
	int count = 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)
															count++;
													}
	cout << count;
	return 0;
}