??引言??
大家好，我是执梗，蓝桥杯的省赛已经确定在4月9日，报名的兄弟们一定要好好练习，我最近也在认真研究往年真题，如果对蓝桥杯的赛制和题型等不太了解的兄弟，可以去看看我的这篇——【蓝桥杯】双非本科？大一大二不敢参加？这篇蓝桥全决议帮你打消疑虑轻松获奖，如果想了解真题的可以看这篇——【蓝桥真题1】这道用了7个for回圈的蓝桥真题，让舍友哭着跑出考场，缺少真题的兄弟可以私信我，近八年相关的蓝桥真题我都准备好了资源，也带有详细的视频决议，需要的私信我或者评论都行，具体在结尾可看，后续也会继续更新蓝桥真题专栏，和大家一起进步，
本次蓝桥真题章节，选取的主要是全排列列举问题，主要利用的是回溯算法来实作全排列，旨在让大家了解回溯算法和全排列对于征战蓝桥杯来说有多重要，因为蓝桥杯的列举的量非常大，大家学习了本章的题目就能感觉到，
2.征战蓝桥，力进国赛
1.饮料换购
小明被劫持到X赌城，被迫与其他3人玩牌，
一副扑克牌（去掉大小王，共52张），均匀发给4个人，每个人13张
这时，小明脑子里突然想到一个问题：
如果不考虑花色，只考虑点数，也不考虑自己得到的牌的先后顺序，自己手里能拿到的初始牌型组合一共有多少种呢？
这种题只能去穷举暴力遍历所有情况，想完成这个任务，只能使用回溯的方法去搜索所有的方法，而且因为是不分花色，每张牌都有相同的四张，所以我们还需要去重，因为有可能模拟到的情况有重复的，这题的计算量比较大，放在编译器上跑都需要十多秒才能出结果，不会回溯的同学一定要先去学习回溯，对于蓝桥杯来说非常的重要，因为需要列举的情况可能性太多，只能通过回溯去搜索，
public class 牌型种数 {
//用来存盘52张牌
static int[] nums=new int[52];
//用来存盘13张牌
static List<Integer> list=new ArrayList<>();
//统计所有的情况
static long ans=0L;
public static void main(String[] args) {
int p=0;
for (int i = 1; i <= 13; i++) {
nums[p++]=i;
nums[p++]=i;
nums[p++]=i;
nums[p++]=i;
}
dfs(0);
System.out.println(ans);//输出答案为3598180
}
public static void dfs(int start){
if (list.size()==13){
ans++;
}
for (int i = start; i < nums.length; i++) {
//树层去重
if (i>start&&nums[i]==nums[i-1]){
continue;
}
list.add(nums[i]);
//递回
dfs(i+1);
//回溯
list.remove(list.size()-1);
}
}
}3.煤球数目
某君从某年开始每年都举办一次生日party，并且每次都要吹熄与年龄相同根数的蜡烛，
现在算起来，他一共吹熄了236根蜡烛，
请问，他从多少岁开始过生日party的？
这道题也是比较基础的题目，我们从1开始遍历，每次往后加即可，如果能恰好加到236，说明就是这个数，如果超过236说明就不是，继续下一个数的累加，直到找到答案，
public static void main(String[] args) {
for (int i=1;i<=100;i++){
int count=0;
int x=i;
while(true){
//找到答案，输出
if(count==236){
System.out.println(i);//输出26,答案26岁
break;
//说明不是这个数，跳出回圈
}else if (count>236){
break;
}else{
//继续累加
count+=x;
x++;
}
}
}
}5.凑算式（10个for回圈或全排列）
首先这个题目有个大坑，看它给的第一个例子，如果按代码中的除来算，8/3应该等于2,952/714等于1，这样最后的答案6+2+1=9，并不等于10，我们代码中在整数型别里的除号并不是严格意义的除号，而是取模，小数部分直接被舍去了的，题目里的要求其实需要我们进行通分，也就是B/C+DEF/GHI进行通分以后整除得到一个数加上A等于10，十个字母对应十种情况，那就是全排列考虑所有可能出现的情况，然后一个个判断是否符合，
方法1：全排列列举
用一个长度为9的阵列模拟从A到I的取值情况，在判断的时候一定要先通分确保能整除，在判断和A相加是否等于10，代码看不懂的话，说明就是不会回溯，其实我们这里也是利用的回溯来进行全排列，当然实作全排列不止这一种方法，问题是为了让大家清楚的知道回溯算法在蓝桥杯的重要性，
public class 凑算式2 {
static int[] a={1,2,3,4,5,6,7,8,9};
static int ans;
public static void main(String[] args) {
f(0);
System.out.println(ans);//输出为29
}
public static boolean 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) % (y * a[2]) == 0 && a[0] + (a[1] * y + a[2] * x) / (y * a[2]) == 10) {
return true ;
}
return false;
}
public static void f (int k){//全排列方法
if (k == 9) {
if (check()){
ans++;
}
}
//从k往后的每个数字都可以放在k位
for (int i = k; i < 9; i++) {
exch(a,i,k);
f(k+1);
exch(a,i,k);
}
}
public static void exch(int[] a,int x,int y){
int c=a[x];
a[x]=a[y];
a[y]=c;
}
}方法2:10个for回圈列举
由于只有十个变量，每个变量的取值只能是1到9，那么用最原始的办法，去10个for回圈遍历，但是每次要保证变量之间互相不相等，这样的代码非常长且容易出错，可见回溯的重要性，但是在蓝桥赛场上，能算出答案的方法就是好方法，就是代码看着有点吓人
public class 凑算式 {
public static void main(String[] args) {
int count = 0;
for (int i = 1; i < 10; i++) {
for (int j = 1; j < 10; j++) {
if (i != j) for (int k = 1; k < 10; k++) {
if (i != k && j != k) for (int l = 1; l < 10; l++) {
if (i != l && j != l && k != l) for (int m = 1; m < 10; m++) {
if (i != m && j != m && k != m && l != m) for (int n = 1; n < 10; n++) {
if (i != n && j != n && k != n && l != n && m != n) for (int o = 1; o < 10; o++) {
if (i != o && j != o && k != o && l != o && m != o && o != n)
for (int p = 1; p < 10; p++) {
if (i != p && j != p && k != p && l != p && m != p && p != n && p != o) {
for (int q = 1; q < 10; q++) {
if (i != q && j != q && k != q && l != q && m != q && q != n && q != o && q != p) {
//需要通分
int x1=l*100+m*10+n;
int x2=o*100+p*10+q;
//不能整除直接break
if ((j*x2+k*x1)%(k*x2)!=0){
break;
}
//符合条件
if (i+(j*x2+k*x1)/(k*x2)==10){
count++;
}
}
}
}
}
}
}
}
}
}
}
}
System.out.println(count);//输出为29
}
}6.纸牌三角形（全排列或9个for回圈列举） 
这道题目，又是典型的全排列问题，比较容易让人出错的地方就是一种情况经过旋转和镜像会产生多少种？答案是六种，如图这样的情况，经过镜像会产生另外一种，旋转以后可以得到两种，旋转再镜像又可以得到两种，加一起就是六种，所以我们直接算出的答案去重的话需要除以六才是标准的答案，回归问题，我们只要去列举每个位置的值即可，把这九个位置分别去对于到阵列的内的下标，
方法1：全排列
类似于上面的第五题，甚至答案整体都长得类似，只是判断的逻辑不同，
public class 纸牌三角屋 {
static int[] a={1,2,3,4,5,6,7,8,9};
static int ans;
public static void main(String[] args) {
dfs(0);
System.out.println(ans/6);//答案为144
}
public static boolean check(){
int x1=a[0]+a[1]+a[3]+a[5];
int x2=a[0]+a[2]+a[4]+a[8];
int x3=a[5]+a[6]+a[7]+a[8];
return x1 == x2 && x2 == x3;
}
public static void dfs(int k){
if(k==9&&check()){
ans++;
}
for (int i = k; i <9; i++) {
int t=a[k];
a[k]=a[i];
a[i]=t;
dfs(k+1);
t=a[k];
a[k]=a[i];
a[i]=t;
}
}
}方法2：9个for回圈列举
还是熟悉的配方，，，，代码我都是直接从上面复制下来的，大家自己同前面的题目理解一样，
public class 纸牌三角屋2 {
public static void main(String[] args) {
int count = 0;
for (int i = 1; i < 10; i++) {
for (int j = 1; j < 10; j++) {
if (i != j) for (int k = 1; k < 10; k++) {
if (i != k && j != k) for (int l = 1; l < 10; l++) {
if (i != l && j != l && k != l) for (int m = 1; m < 10; m++) {
if (i != m && j != m && k != m && l != m) for (int n = 1; n < 10; n++) {
if (i != n && j != n && k != n && l != n && m != n) for (int o = 1; o < 10; o++) {
if (i != o && j != o && k != o && l != o && m != o && o != n)
for (int p = 1; p < 10; p++) {
if (i != p && j != p && k != p && l != p && m != p && p != n && p != o) {
for (int q = 1; q < 10; q++) {
if (i != q && j != q && k != q && l != q && m != q && q != n && q != o && q != p) {
int x1=i+j+l+n;
int x2=i+k+m+q;
int x3=n+o+p+q;
if (x1==x2&&x2==x3){
count++;
}
}
}
}
}
}
}
}
}
}
}
}
System.out.println(count/6);//输出为29
}
}
3.刷题总结（资源图片）
这些题目做下来，很明显能感觉到全排列对于蓝桥杯而言的重要性，毕竟凑算式和纸牌三角形你可以用多个for回圈解决，可像纸牌总类这种题目你确是不可信的，但是如果在蓝桥杯的赛场上发现可以用多层for回圈解决，你又不会全排列或者不熟，别担心，大胆去尝试，毕竟能找到答案的方法就是好方法，我们的目的只是为了得到答案，
还没有资源的兄弟速度评论私信扣我，放假一起刷起来！！！
0 评论