蓝桥杯第七届：剪邮票 枚举or排列组合
文章目录
题目
如【图1.jpg】, 有12张连在一块儿的12生肖的邮票。
如今你要从中剪下5张来，要求必须是连着的。
（仅仅链接一个角不算相连）好比，【图2.jpg】，【图3.jpg】中，粉红色所示部分就是合格的剪取。
请你计算，一共有多少种不一样的剪取方法。
答案：116ios
解题思路
（1）枚举
思路：首先咱们设x[5]：x[0],x[1],x[2],x[3],x[4]五个解向量，观察图咱们不难发现
1 <= x[0] < x[1] < x[2] < x[3] < x[4] <= 12
即：
1 <= x[0] <= 8
x[0] < x[1] <= 9
x[1] < x[2] <= 10
x[2] < x[3] <= 11
x[3] < x[4] <= 12
就能够根据这个范围进行枚举，每枚举完一次判断其是否连成一片，为方便判断因此个人x[0]是从0开始。web
int ans = 0; for(x[0] = 0; x[0] < 8 ; x[0]++) { for(x[1] = x[0] + 1; x[1] < 9 ; x[1]++) { for(x[2] = x[1] + 1; x[2] < 10; x[2]++) { for(x[3] = x[2] + 1; x[3] < 11; x[3]++) { for(x[4] = x[3] + 1; x[4] < 12; x[4]++) { if(check()) { ans++; } } } } } }
那么又该如何判断连通性呢？数组
连通性断定1：邻接矩阵
首先就是要了解一个概念，什么是邻接矩阵和度。
什么是邻接矩阵：
邻接矩阵既然是矩阵，咱们就要使用一个二维数组来表示矩阵，那么就须要一个12行12列的矩阵来分别表示每一个“点”之间的关系。好比表示第i行第j列表示i和j这两个点是否相邻，若是相邻那么cc[i][j] = 1,不然等于0，咱们来看看这个图：
1和2,5相邻，2和1,3,6相邻，7和3,6,8,11相邻，那么就将与其相邻的点置为1，若是不相邻就置为0svg
int cc[12][12] = {0,1,0,0,1,0,0,0,0,0,0,0, 1,0,1,0,0,1,0,0,0,0,0,0, 0,1,0,1,0,0,1,0,0,0,0,0, 0,0,1,0,0,0,0,1,0,0,0,0, 1,0,0,0,0,1,0,0,1,0,0,0, 0,1,0,0,1,0,1,0,0,1,0,0, 0,0,1,0,0,1,0,1,0,0,1,0, 0,0,0,1,0,0,1,0,0,0,0,1, 0,0,0,0,1,0,0,0,0,1,0,0, 0,0,0,0,0,1,0,0,1,0,1,0, 0,0,0,0,0,0,1,0,0,1,0,1, 0,0,0,0,0,0,0,1,0,0,1,0};
有了邻接矩阵咱们就能够判断两个点是否相邻，接着咱们要判断这五个点的度是否大于等于8，由于咱们有5个点因此至少有4条边相连好比这个图，2和6相连2有一条相邻边因此度为1,6和2,7相连因此度为1 + 2 = 3 依次累加下去算出来度最少为8，因此这道题就变成了每次枚举完一种状况就判断是否连成一片，而是否连成一片的依据就是每一个点是否有相邻的点以及最后度是否大于等于8spa
bool check() { bool flag = true; int s = 0; for(int i = 0 ;(flag && i < 5); i++) { int d = 0; for(int j = 0; j < 5; j++) { if(cc[x[i]][x[j]] == 1)/*若是两点相邻*/ { d++; } } if( d == 0 ) { flag = false;/*若是找不到一个和i这一点相邻的点那么必定不连通*/ } s += d; } if( s < 8) { flag = false;/*若是度小于8就不连通*/ } return flag; }
完整代码1
#include <iostream> using namespace std; int x[5]; int cc[12][12] = {0,1,0,0,1,0,0,0,0,0,0,0, 1,0,1,0,0,1,0,0,0,0,0,0, 0,1,0,1,0,0,1,0,0,0,0,0, 0,0,1,0,0,0,0,1,0,0,0,0, 1,0,0,0,0,1,0,0,1,0,0,0, 0,1,0,0,1,0,1,0,0,1,0,0, 0,0,1,0,0,1,0,1,0,0,1,0, 0,0,0,1,0,0,1,0,0,0,0,1, 0,0,0,0,1,0,0,0,0,1,0,0, 0,0,0,0,0,1,0,0,1,0,1,0, 0,0,0,0,0,0,1,0,0,1,0,1, 0,0,0,0,0,0,0,1,0,0,1,0}; bool check() { bool flag = true; int s = 0; for(int i = 0 ;(flag && i < 5); i++) { int d = 0; for(int j = 0; j < 5; j++) { if(cc[x[i]][x[j]] == 1)/*若是两点相邻*/ { d++; } } if( d == 0 ) { flag = false;/*若是找不到一个和i这一点相邻的点那么必定不连通*/ } s += d; } if( s < 8) { flag = false;/*若是度小于8就不连通*/ } return flag; } int main() { int ans = 0; for(x[0] = 0; x[0] < 8 ; x[0]++) { for(x[1] = x[0] + 1; x[1] < 9 ; x[1]++) { for(x[2] = x[1] + 1; x[2] < 10; x[2]++) { for(x[3] = x[2] + 1; x[3] < 11; x[3]++) { for(x[4] = x[3] + 1; x[4] < 12; x[4]++) { if(check()) { ans++; } } } } } } cout << ans << endl; return 0; }
连通性断定2：行列之差
根据这个图咱们能够看到同一行两个相邻的点之差的绝对值为1，可是存在4,5之间不相邻但差的绝对值仍是为1的状况，咱们就将第二行每个点加1，第三行每个点加2变成以下图所示
这里同一行每一个点差的绝对值仍是1，可是就不存在不一样行之间差为1，相反第一行和第二行，第二行和第三行每一个元素之差的绝对值为5，所以咱们就能够定义一个一维数组来存放这些值：int c[12] = {1,2,3,4,6,7,8,9,11,12,13,14};，那么连通性判断就能够变成这样3d
bool check() { bool flag = true; int s = 0; for(int i = 0 ;(flag && i < 5); i++) { int d = 0; for(int j = 0; j < 5; j++) { if(abs(c[x[i]] - c[x[j]]) == 1 || abs(c[x[i]] - c[x[j]]) == 5)/*若是两点相邻*/ { d++; } } if( d == 0 ) { flag = false;/*若是找不到一个和i这一点相邻的点那么必定不连通*/ } s += d; } if( s < 8) { flag = false;/*若是度小于8就不连通*/ } return flag; }
完整代码2
#include <iostream> #include <cmath> using namespace std; int x[5]; int c[12] = {1,2,3,4,6,7,8,9,11,12,13,14}; bool check() { bool flag = true; int s = 0; for(int i = 0 ;(flag && i < 5); i++) { int d = 0; for(int j = 0; j < 5; j++) { if(abs(c[x[i]] - c[x[j]]) == 1 || abs(c[x[i]] - c[x[j]]) == 5)/*若是两点相邻*/ { d++; } } if( d == 0 ) { flag = false;/*若是找不到一个和i这一点相邻的点那么必定不连通*/ } s += d; } if( s < 8) { flag = false;/*若是度小于8就不连通*/ } return flag; } int main() { int ans = 0; for(x[0] = 0; x[0] < 8 ; x[0]++) { for(x[1] = x[0] + 1; x[1] < 9 ; x[1]++) { for(x[2] = x[1] + 1; x[2] < 10; x[2]++) { for(x[3] = x[2] + 1; x[3] < 11; x[3]++) { for(x[4] = x[3] + 1; x[4] < 12; x[4]++) { if(check()) { ans++; } } } } } } cout << ans << endl; return 0; }
（2）排列组合
方法1：普通排列组合
和枚举的思想差很少，都是找到一种状况而后判断连通性，不过是采用排列组合的方式，从12个里面选5个而且连通的组合，这个连通性的判断也与以前的不一样，也用了度为8这个条件，但同时也不能存在孤立点，即度为8可是存在一个与谁都不相邻的点这也是不符合要求的
判断连通性code
bool link_check(int a[5]) { set<int>a_set(a,a + 5); int s = 0; for(int i = 0 ; i < 5; i++) { int d = 0; if(a[i] - 4 >= 1 && a_set.count(a[i] - 4)) { d++; } if(a[i] + 4 <= 12 && a_set.count(a[i] + 4)) { d++; } if(a[i] != 1 && a[i] != 5 && a[i] != 9 && a_set.count(a[i] - 1)) {/*1,5,9左边没有元素*/ d++; } if(a[i] != 4 && a[i] != 8 && a[i] != 12 && a_set.count(a[i] + 1)) {/*4,8,12右边没有元素*/ d++; } if(d == 0)/*存在孤立点*/ { return false; } s += d; } return s >= 8;
完整代码3
#include <iostream> #include <cmath> #include <set> using namespace std; int a[5]; int b[12] = {1,2,3,4,5,6,7,8,9,10,11,12};/*邮票*/ int ans = 0;/*最终答案*/ bool link_check(int a[5]) { set<int>a_set(a,a + 5); int s = 0; for(int i = 0 ; i < 5; i++) { int d = 0; if(a[i] - 4 >= 1 && a_set.count(a[i] - 4)) { d++; } if(a[i] + 4 <= 12 && a_set.count(a[i] + 4)) { d++; } if(a[i] != 1 && a[i] != 5 && a[i] != 9 && a_set.count(a[i] - 1)) { d++; } if(a[i] != 4 && a[i] != 8 && a[i] != 12 && a_set.count(a[i] + 1)) { d++; } if(d == 0)/*存在孤立点*/ { return false; } s += d; } return s >= 8; } void f(int ind,int len) { if( len >= 5 ) { if(link_check(a))/*若是五个点连成一片*/ { ans++; } return; } for(int i = ind ; i < 12; i++) { a[len] = b[i]; f(i + 1,len + 1);/*不一样的组合状况*/ } } int main() { f(0,0); cout << ans << endl; return 0; }
方法2：STL——next_permutation实现排列组合
连通性判断：判断一个图里有多少个连通区域xml
void mark(int a[][4],int i,int j) { int tag = a[i][j]; a[i][j] = 0; if(i - 1 >= 0 && a[i - 1][j] == tag) mark(a,i - 1,j); if(i + 1 < 3 && a[i + 1][j] == tag) mark(a,i + 1,j); if(j - 1 >= 0 && a[i][j - 1] == tag) mark(a,i,j - 1); if(j + 1 < 4 && a[i][j + 1] == tag) mark(a,i,j +1); } bool link_check(int b[5]) { set<int>b_set(b,b + 5); int a[3][4] = {0}; for(int i = 0 ; i < 3; i++) { for(int j = 0 ; j < 4; j++) { if(b_set.count(i * 4 + j + 1)) { a[i][j] = 1; } } } int link_num = 0; for(int i = 0 ; i < 3 ; i++) { for(int j = 0 ; j < 4; j++) { if(a[i][j] == 1) { link_num++; mark(a,i,j); } } } return (link_num == 1);/*若是只有一个连通区域就符合*/ }
使用next_permutation来实现排列组合blog
int ans = 0; int num[12] = {0,0,0,0,0,0,0,1,1,1,1,1}; do { int a[5] = {0};/*每次都初始化数组a*/ for(int i = 0,j = 0 ; i < 12; i++) { if(num[i] == 1) { a[j++] = i + 1; } } if(link_check(a)) ans++; }while(next_permutation(num,num + 12)); cout << ans <<endl;
完整代码4
#include <iostream> #include <cmath> #include <set> #include <algorithm> using namespace std; int a[5]; int b[12] = {1,2,3,4,5,6,7,8,9,10,11,12};/*邮票*/ int ans = 0;/*最终答案*/ void mark(int a[][4],int i,int j) { int tag = a[i][j]; a[i][j] = 0; if(i - 1 >= 0 && a[i - 1][j] == tag) mark(a,i - 1,j); if(i + 1 < 3 && a[i + 1][j] == tag) mark(a,i + 1,j); if(j - 1 >= 0 && a[i][j - 1] == tag) mark(a,i,j - 1); if(j + 1 < 4 && a[i][j + 1] == tag) mark(a,i,j +1); } bool link_check(int b[5]) { set<int>b_set(b,b + 5); int a[3][4] = {0}; for(int i = 0 ; i < 3; i++) { for(int j = 0 ; j < 4; j++) { if(b_set.count(i * 4 + j + 1)) { a[i][j] = 1; } } } int link_num = 0; for(int i = 0 ; i < 3 ; i++) { for(int j = 0 ; j < 4; j++) { if(a[i][j] == 1) { link_num++; mark(a,i,j); } } } return (link_num == 1);/*若是只有一个连通区域就符合*/ } int main() { int ans = 0; int num[12] = {0,0,0,0,0,0,0,1,1,1,1,1}; do { int a[5] = {0};/*每次都初始化数组a*/ for(int i = 0,j = 0 ; i < 12; i++) { if(num[i] == 1) { a[j++] = i + 1; } } if(link_check(a)) ans++; }while(next_permutation(num,num + 12)); cout << ans <<endl; return 0; }