文章目录

题目描述一、DFS暴搜一（枚举法）二、DFS暴搜二(交换法)三、C++库函数四、进阶题虫食算全排列 + 剪枝 蓝桥杯省赛题：寒假作业

题目描述

给定一个长度为 n 的可包含重复数字的序列，请你求出其所有不重复的全排列。 输入格式 第一行包含整数 n。 第二行包含 n 个整数。 输出格式 输出所有的不同排列，每种排列占一行。 在确定每种排列的输出顺序时，第一个数较小的先输出，第一个数相同时，第二个数较小的先输出，以此类推。 数据范围 1≤n≤9, 数组中包含的元素的取值范围 [1,9] 输入样例： 3 1 1 2 输出样例： 1 1 2 1 2 1 2 1 1

一、DFS暴搜一（枚举法）

1.搜索顺序：从前往后依次枚举每一个位置，每个位置上有多种选择。 2.回溯：因为要枚举所有可能的选择，在一次深搜出来后，要立即恢复成上一次的状态 3.剪枝：有重复元素，剪枝过程如下：

#include <iostream> #include <vector> #include <algorithm> using namespace std; const int N = 10; int a[N]; int n; bool st[N]; void dfs(int u, vector<int>& path) { if(u == n) { for(int i = 0; i < n; i++) cout << path[i] << " "; puts(""); return; } for(int i = 0; i < n; i++) { if(!st[i]) { if(i > 0 && a[i] == a[i - 1] && st[i - 1]) continue; st[i] = true; path.push_back(a[i]); dfs(u + 1, path); path.pop_back(); st[i] = false; } } } int main() { cin >> n; for(int i = 0; i < n; i ++) cin >> a[i]; vector<int> path; sort(a, a + n); dfs(0, path); return 0; }

二、DFS暴搜二(交换法)

#include <iostream> #include <algorithm> using namespace std; const int N = 10; int a[N]; int len; bool judge(int k, int m) { for(int i = k; i < m; i++) if(a[m] == a[i]) return false; return true; } void swap(int i, int n) { int t = a[i]; a[i] = a[n]; a[n] = t; } void permutation(int k) { if (k == len) { for (int i = 0; i < len; i++) { cout << a[i] << " "; } puts(" "); } else { for (int i = k; i < len; i++) { if (judge(k, i)) { swap(i, k); //此处可以剪枝 /*if(k == 3 && !check()) { //只确定了前3个数字 swap(i, k); continue; }*/ permutation(k + 1); swap(i, k); } } } } int main() { cin >> len; for(int i = 0; i < len; i++) cin >> a[i]; sort(a, a + len); //reverse(a, a + len); permutation(0); return 0; }

三、C++库函数

可以自动去重

do { check() { } }while(nextpermutation(a, a + n))

四、进阶题

虫食算

所谓虫食算，就是原先的算式中有一部分被虫子啃掉了，需要我们根据剩下的数字来判定被啃掉的字母。 来看一个简单的例子： 43#9865#045+ 8468#6633-------------- 44445506978 其中#号代表被虫子啃掉的数字。 根据算式，我们很容易判断：第一行的两个数字分别是5和3，第二行的数字是5。 现在，我们对问题做两个限制： 首先，我们只考虑加法的虫食算。这里的加法是N进制加法，算式中三个数都有N位，允许有前导的0。 其次，虫子把所有的数都啃光了，我们只知道哪些数字是相同的，我们将相同的数字用相同的字母表示，不同的数字用不同的字母表示。 如果这个算式是N进制的，我们就取英文字母表的前N个大写字母来表示这个算式中的0到N-1这N个不同的数字：但是这N个字母并不一定顺序地代表0到N-1。 输入数据保证N个字母分别至少出现一次。 BADC +CBDA =DCCC 上面的算式是一个4进制的算式。 很显然，我们只要让ABCD分别代表0123，便可以让这个式子成立了。 你的任务是，对于给定的N进制加法算式，求出N个不同的字母分别代表的数字，使得该加法算式成立。 输入数据保证有且仅有一组解。 输入格式 输入包含4行。 第一行有一个正整数N(N<=26)，后面的3行每行有一个由大写字母组成的字符串，分别代表两个加数以及和。 这3个字符串左右两端都没有空格，并且恰好有N位。 输出格式 输出包含一行。 在这一行中，应当包含唯一的那组解。 解是这样表示的：输出N个数字，分别表示A，B，C……所代表的数字，相邻的两个数字用一个空格隔开，不能有多余的空格。 输入样例： 5 ABCED BDACE EBBAA 输出样例： 1 0 3 4 2 难度：简单 时/空限制：1s / 64MB 总通过数：414 总尝试数：935 来源：《算法竞赛进阶指南》, NOIP2004提高组 算法标签

全排列 + 剪枝

#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 30; char eq[3][N]; int q[N], path[N]; bool st[N]; int n; bool check() { for(int i = n - 1, t = 0; i >= 0; i--) { int a = path[eq[0][i] - 'A'], b = path[eq[1][i] - 'A'], c = path[eq[2][i] - 'A']; if(a != -1&&b != -1 && c != -1) { if(t == -1) { if((a + b) % n != c && (a + b + 1) % n != c) return false; if(!i&&a + b >= n) return false; } else { if((a + b + t)% n != c) return false; if (!i && a + b + t >= n) return false; t = (a + b + t) / n; } } else { t = -1; } } return true; } bool dfs(int u) { if(u == n) return true; for(int i = 0; i < n; i++) { if(!st[i]) { st[i] = true; path[q[u]] = i; if(check()&&dfs(u + 1)) return true; st[i] = false; path[q[u]] = -1; } } return false; } int main() { cin >> n >> eq[0] >> eq[1] >> eq[2]; for(int i = n - 1, k = 0; i >= 0; i--) { for(int j = 0; j < 3; j++) { int c = eq[j][i] - 'A'; if(!st[c]) { st[c] = true; q[k++] = c; } } } memset(st, 0, sizeof st); memset(path, -1, sizeof path); dfs(0); for(int i = 0; i < n; i++) cout << path[i] << " "; return 0; }

蓝桥杯省赛题：寒假作业

寒假作业: 现在小学的数学题目也不是那么好玩的。 看看这个寒假作业： □ + □ = □ □ - □ = □ □ × □ = □ □ ÷ □ = □ 每个方块代表1~13中的某一个数字，但不能重复。 比如： 6 + 7 = 13 9 - 8 = 1 3 * 4 = 12 10 / 2 = 5 以及： 7 + 6 = 13 9 - 8 = 1 3 * 4 = 12 10 / 2 = 5 就算两种解法。（加法，乘法交换律后算不同的方案） 你一共找到了多少种方案？ 请填写表示方案数目的整数。 注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。

#include<iostream> #include<algorithm> #include<cmath> using namespace std; int res=0; int a[]={1,2,3,4,5,6,7,8,9,10,11,12,13}; void dfs(int start) { if(start>=3 ) if(a[0]+a[1]!=a[2]) return ;//对确定的前面三个数字进行等式判断，不符合，就不继续往下搜索 if(start>=6) if(a[3]-a[4]!=a[5]) return ;//同理进行第二个等式的判断，进行剪枝 if(start>=9) if(a[6]*a[7]!=a[8]) return ; if(start>=12) if(a[11]*a[10]==a[9]) { for(int i=0;i<12;i++) cout<<a[i]<<" "; cout<<endl; res++; return ; } for(int i=start;i<=12;i++) { int temp=a[start]; a[start]=a[i]; a[i]=temp; dfs(start+1); temp=a[start]; a[start]=a[i]; a[i]=temp; } } int main() { dfs(0); cout<<res<<endl; return 0; }