1. 凑算式（蓝桥真题）

题目：

注意：需要通分，有些时候除不尽需要通分。

源码：

方法一：递归回溯全排列

int ret = 0;
#define MAX 9
//多少个全排列
int a[MAX];//排列数组
bool flag[MAX];//标记数组int n = MAX; 
//全排列n个数void Init()
{//初始化标记为for (int i = 0; i < MAX; i++){flag[i] = true;}
}bool check()
{int x = a[3] * 100 + a[4] * 10 + a[5];int y = a[6] * 100 + a[7] * 10 + a[8];if (((a[1] * y + a[2] * x) % (a[2] * y)  == 0) && a[0] + (a[1] * y + a[2] * x) / (a[2] * y) == 10){return true;}return false;
}void dfs(int storey)
{if (storey == MAX)//如果深度达到MAX就返回{//检查if (check())ret++;return;}for (int i = 0; i < MAX; i++){if (flag[i] == true){//判断此位置是否被使用       flag[i] = false;//此数字被使用。a[storey] = i+1;//给该层赋值dfs( storey+ 1);//执行下一层flag[i] = true;//回溯//让此数字没有被使用。}}
}
int  main(){Init();dfs(0);//递归深度从0开始cout << ret;return 0;}

方法二：next_permutation全排列

#include<iostream>
#include<algorithm>
using namespace std;#define SIZE 9
int a[SIZE] = { 1,2,3,4,5,6,7,8,9};
int ret = 0;
bool check()
{int x = a[3] * 100 + a[4] * 10 + a[5];int y = a[6] * 100 + a[7] * 10 + a[8];//(a[1] * y + a[2] * x) % (y * a[2]) == 0 && a[0] + (a[1] * y + a[2] * x) / (y * a[2]) == 10if (((a[1] * y + a[2] * x) % ( y*a[2] )  == 0) && a[0] + (a[1] * y + a[2] * x) / (y*a[2]) == 10){return true;}return false;
}
void test1(){do {if (check() == true){ret++;}} while (next_permutation(a, a + 9));
}
int main()
{test1();cout << ret;return 0;
}

知识点：
1.next_permutation生成全排列得使用
2.理解递归回溯生成全排列

2. 三羊献瑞（蓝桥真题）

题目描述：

    祥 瑞 生 辉            a b c d 
+   三 羊 献 瑞            e f g b
--------------------------------------三 羊 生 瑞 气         e f c b h

还是可以看成全排列的问题。

代码实现：

#include<iostream>
#include<algorithm>
using namespace std;int a[10] = { 0,1,2,3,4,5,6,7,8,9 };bool check()
{int add1 = a[0] * 1000 + a[1] * 100 + a[2] * 10 + a[3];int add2 = a[4] * 1000 + a[5] * 100 + a[6] * 10 + a[1];int sum = a[4] * 10000 + a[5] * 1000 + a[2] * 100 + a[1] * 10 + a[7];if (add1 + add2 == sum  && a[0] != 0 && a[4]!= 0){cout << add2 << endl;return true;}return false;
}
int main()
{do {check();} while (next_permutation(a, a + 10));return 0;
}

知识点:
next_permutation,全排列。

3. 方格分割（蓝桥真题）

题目描述：

6x6的方格，沿着格子的边线剪开成两部分。要求这两部分的形状完全相同。

如图：就是可行的分割法。

试计算：包括这3种分法在内，一共有多少种不同的分割方法。注意：旋转对称的属于同一种分割法。

请提交该整数，不要填写任何多余的内容或说明文字。

说明：

如果把样例图案剪开，发现有且只有两个点在边界上，且一定经过 （3,3）点。
以（3,3）为起点进行深搜，深搜到一个边界上的点，那么他的中心对称点相当于也搜过了。
如果发现搜到了边界，那么它的中心对称点也到了边界 沿着已经搜过的点剪开，那么剪开的两个图形为中心对称图形。（要注意最终的结果要除以4）
例如 我们从（3,3）点出发一直向右到边界 ， 或一直向左，或一直向上，或一直向下剪出来的图形是同一个。

代码实现

#include<iostream>
#include<algorithm>
using namespace std;
bool vis[7][7];//标记数组
void init()
{//初始化标记数组for (int i = 0; i < 7; i++){for (int j = 0; j < 7; j++){vis[i][j] = true;}}
}int ret = 0;void dfs(int x, int y)
{//走到边线if (x == 0 || x == 6 || y == 0 || y == 6){ret++;return;}for (int i = 0; i < 4; ++i){//四个方向//(x+1,y)(x-1,y)(x,y+1)(x,y-1)int nx;int ny;if (i == 0){nx = x + 1;ny = y;}if (i == 1){nx = x - 1;ny = y;}if (i == 2){nx = x;ny = y + 1;}if (i == 3){nx = x;ny = y - 1;}if (vis[nx][ny]){vis[nx][ny] = false; vis[6 - nx][6 - ny] = false;dfs(nx, ny);vis[nx][ny] = true; vis[6 - nx][6 - ny] = true;}}
}
int main()
{init();vis[3][3] = false;dfs(3, 3);cout << ret/4 << endl;//509return 0;
}

知识点：
dfs的深度优先遍历。

4. 方格填数（蓝桥真题）

显然全排列也能搞定。

对每一种排列数进行判断。

代码实现：

#include<iostream>
#include<algorithm>
using namespace std;
int a[10] = { 0,1,2,3,4,5,6,7,8,9 };
int ret = 0;
int dis(int x, int y)
{if (a[x] - a[y] == 1 || a[x] - a[y] == -1){return 1;}return  0;
}
bool check()
{if (dis(0, 1) ==1||dis(0, 3) ==1||dis(0, 4) ==1||dis(0, 5) ==1||dis(1, 4) ==1||dis(1, 5) ==1||dis(1, 6) ==1||dis(1, 2) ==1||dis(2, 5) ==1||dis(2, 6) ==1||dis(3, 4) ==1||dis(3, 7) ==1||dis(3, 8) ==1||dis(4, 5) ==1||dis(4, 7) ==1||dis(4, 8) ==1||dis(4, 9) ==1||dis(5, 6) ==1||dis(5, 8) ==1||dis(5, 9) == 1 ||dis(6, 9) ==1||dis(7, 8) ==1||dis(9, 8)==1){return false;}return true;
}
int main()
{do {if (check()){ret++;}} while (next_permutation(a, a + 10));cout << ret << endl;//1580return 0;
}

以上是最简单的一种方式，也可以深度递归去一个一个填写，这样代码会不好理解

知识点：
只要还是用全排列，全部填入，然后判断每一个排列即可。

5. 加法变乘法（蓝桥真题）

其实这个题就说遍历，遍历两个*的位置，
加号变为乘号，前后sum的变化就是加上两者相乘的情况，然后再进去两者本身就可以了。

#include<iostream>
using namespace std;int main()
{for (int i = 1; i < 50; i++){for (int j = i + 1 ; j < 50; j++){int sum = 1225 - i - i - 1 + i * (i + 1) - j - j - 1 + j * (j + 1);if (sum == 2015){cout << i <<"  " << j << endl;}}}return 0;
}

很简单但是稍微带一点点小技巧。

6. 最大公共子串（蓝桥真题）

题目描述：

给定两个字符串，求出最大公共子串的长度：

分析：

这里要用到一个二位数组。且这个二维数组比两个串行列大一。

代码实现：

#include<iostream>
#include<string>
using namespace std;int fun(const char* str1, const char* str2)
{int max = 0;//记录最大值int len1 = strlen(str1);int len2 = strlen(str2);int a[256][256];memset(a, 0, sizeof(int) * 256 * 256);//首先全部初始化位0；for (int i = 0; i < len1; i++){for (int j = 0; j < len2; j++){if (str1[i] == str2[j]){a[i + 1][j + 1] = a[i][j] + 1;if (a[i + 1][j + 1] > max){max = a[i + 1][j + 1];}}}}return max;
}int main()
{cout << fun("zhangzxnsk", "axsk") << endl;return 0;
}

7. 最大黑区域的问题（DFS）

题目描述：

    {0,1,1,0,0,1},{1,1,0,1,0,1},{0,1,0,0,1,0},{0,0,0,1,1,1},{1,0,1,1,1,0}，
//假设1是黑块，0是白块，求出黑色的块最大联通块的面积。
//每个块面积是1，
//只有上下左右相邻的才算是联通。斜着链接不是联通。

源码：

//坐标移动的四个方向
int ll[4][2] = {{1,0},{-1,0},{0,1},{0,-1}
};//原始的二维数组。
int arr[5][6] = {{0,1,1,0,0,1},{1,1,0,1,0,1},{0,1,0,0,1,0},{0,0,0,1,1,1},{1,0,1,1,1,0}
};int _max = 0;//当前最大面积
int s = 0;//面积void dfs(int x, int y)
{s += 1;//面积+1arr[x][y] = 0;//记录这里统计过。for (int i = 0; i < 4; i++){int nx = x + ll[i][0];int ny = y + ll[i][1];if (ny>=0 && ny>=0 && nx <= 4&& ny <= 5 && arr[nx][ny] == 1) dfs(nx, ny);}
}int main()
{for (int i = 0; i < 5; i++){for (int j = 0; j < 6; j++){//先找到一个黑区域if (arr[i][j] == 1){//从i，j 开始dfs。s = 0;//注意每次dfs时候都要先把面积变为0dfs(i, j);if (s >_max){_max = s;}}}}cout << _max << endl;return 0;
}

8. 剪邮票（蓝桥真题）

#include<iostream>
#include<algorithm>
using namespace std;
int a[12] = { 0,0,0,0,0,0,0,1,1,1,1,1 };int  ll[4][2] = {{1,0},{-1,0},{0,1},{0,-1}
};
int flag[3][4] = { 0 };
int m = 0;//记录每一次查找的最大联通数void dfs(int x, int y)
{flag[x][y] = 0;//表示已经统计过m++;if (m == 5) return;for (int i = 0; i < 4; i++){int nx = x + ll[i][0];int ny = y + ll[i][1];if (nx >= 0 && ny >= 0 && nx < 3 && ny < 4 && flag[nx][ny] == 1) {dfs(nx, ny);//此题不需要回溯}}
}bool check()
{//在数组中填写标记位。int size = 0;for (int i = 0; i < 3; i++){for (int j = 0; j < 4; j++){flag[i][j] = a[size++];}}for (int i = 0; i < 3; i++){for (int j = 0; j < 4; j++){if (flag[i][j] == 1)//找到其中一个标记位置{m = 0;dfs(i, j);if (m == 5){return true;}}}}return false;
}int ret = 0;
int main()
{do {if (check()){ret++;}} while (next_permutation(a, a + 12));cout << ret << endl;return 0;
}

9. 日期问题（蓝桥真题）

题目描述：

讲解：

题目不难但是很考验细心程度，需要控制各种各样的不成立问题，
例如：考虑二月的问题，闰年，大小月份的问题。最后还要去重和排序。

实现代码：

#include<iostream>
#include<string>
#include<set>
using namespace std;
int day[13] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };bool isleap(int year)
{return (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
}
string check(int a, int b, int c)//a是年，b是月，c是日
{//处理年if (a >= 60 && a < 99) { a += 1900; }else if (a >= 0 && a < 59) { a += 2000; }else { return ""; }//处理月if (b < 0 || b>12)return "";//处理日if (isleap(a)) { day[2] = 28; }if (day[b] < c) { return "";}string _year = to_string(a);string _monch = to_string(b);if (b < 10) { _monch.insert(0, 1, '0'); }string _day = to_string(c);if (c < 10) { _day.insert(0, 1, '0'); }string ret = _year +"-"+ _monch + "-" + _day;return ret;
}int main()
{string strin;cin >> strin;//按顺序记录三个数字。int a = (strin[0] - '0') * 10 + (strin[1] - '0');int b = (strin[3] - '0') * 10 + (strin[4] - '0');int c = (strin[6] - '0') * 10 + (strin[7] - '0');string str1 = check(a, b, c);string str2 = check(c, a, b);string str3 = check(c, b, a);set<string> ret;if (str1 != "") ret.insert(str1);if (str2 != "") ret.insert(str2);if (str3 != "") ret.insert(str3);for (auto e : ret){cout << e << endl;}return 0;
}

10. 买不到的数目（蓝桥真题）

题目描述：

分析：

1.这是一个不定方程的问题。
2.“a*x+b*y = c“有解问题。
3.根据数学原理：
a和b互质，一定存在最大凑不出的数是：“a*b-a-b”。
a和b不互质，即gcd(a,b)>1时，任意的an+bm-1都无法实现，有无限个凑不出的数。

实现代码：

#include<iostream>
using namespace std;
int main()
{int n1, n2;while (cin >> n1 >> n2){cout << n1 * n2 - n1 - n2 << endl;}return 0;
}

11. 包子凑数（蓝桥真题）

题目描述：

分析：

1.这是一个不定方程的问题。
2.“a1*x1+a2*x2 ---- an*xn = c“ 有解问题。
3.根据数学原理：
a1,a2,a3---an互质，一定存在最大凑不出的数是：“a*b-a-b”。
a1,a2,a3---an不互质，即gcd(a,b)>1时，任意的an+bm-1都无法实现，有无限个凑不出的数。
4.首先根据n<100 & ai<100，可以得到无法组成的最大数就是10000。也可以根据 a,b无法组成的最大数为a*b-a-b确定是 9800。
5.先求出一组数的最小公倍数，当cgcd!=1时，答案就为INF,因为a*n+b*m-1总是无法组成
6.定义一个maxnumm == 10000长度的数组。
7.遍历1~maxnum，动态规划标记所有能访问的点，未标记的个数就是ans；

实现代码：

#include<iostream>
using  namespace std;int n = 0;//种类数
int arr[100];//存放包子数
bool flag[10000];
//下标对应的数字，可凑出来标记为true，凑不出来标记为false//互质是：公约数只有1的两个整数是互质
//最大公约数
int gcd(int a, int b)
{if (b == 0)return a;else return gcd(b, a % b);
}int g = 0;
int ret = 0;
int main()
{flag[0] = true;//0肯定是能凑出来的。for (int i = 1; i < 10000; i++){flag[i] = false;}cin >> n;for (int i = 0; i < n; i++){cin >> arr[i];//从小到大输入}//数据输入完成for (int i = 0; i < n ; i++){if (i == 0) { g = arr[i]; }else { g = gcd(arr[i], g); }for (int j = 0; j < 9900; j++){if (flag[j] == true) { flag[j + arr[i]] = true; }}}if (g != 1) {cout << "INF" << endl;return 0;}for (int j = 0; j < 9900; j++){if (!flag[j]) { ret++; cout << j << endl;}}cout << ret << endl;return 0;
}