蓝桥杯——我该如何枚举
文章目录
一、枚举
?1.前言
距离蓝桥杯省赛的日子越来越近了???，不知道大家准备的怎么样？???不管如何，到现在这个时候都不能慌。硬实力是一方面，但是也不能只顾着埋头刷题，蓝桥杯还是有很多技巧的。
首先我们应该清楚，蓝桥杯十道题，前面五道都是填空题，填空题只需要填上答案就可以。
换句话说我们不管使用什么算法，哪怕是手算只要算出答案也行，当然手算是没有办法的办法???
那么有没有什么好的技巧呢？
我的答案是 暴力枚举，相信大家对暴力枚举都不陌生，也经常能在各大oj平台上看到诸如这个题暴力能不能解之类的讨论，许多题其实都可以暴力枚举，只是大部分题目都可能会超时，但是超时是超出了oj平台对改题目设置的限定时间，蓝桥杯的填空题可没有超时这个说法，只需要填写答案，而且许多编程
题暴力枚举也能拿不少分，那么我们为什么不选择更容易想到的暴力枚举呢？
大家都知道枚举简单，不就是把所有情况都列举出来吗，但是在实际写的时候，很多人并没有使用或者第一时间选择枚举，难道是害怕超时吗？经过了解几个小伙伴的想法后才知道原来大家不是不想用枚举，也不是不了解枚举，而是不知道该如何进行有效的枚举。
?2.枚举模板
我个人对可以枚举题目的理解结合oj平台上一些大佬的经验，总结出一个基本思想和一个大白话的模板
一个基本思想： 怎么简单怎么来，能for就for，不能for就while
一个白话模板：
1.找到要进行枚举的东西
2.要枚举东西的特性
3.枚举的上下边界
4.符合条件的判断
5.能否在枚举的基础上简单优化（视情况判断是否省略）
我们根据一个基本思想和一个白话模板结合往年蓝桥杯真题实践实践
二、例题分析
?1.四平方和
?1.题目描述
?2.题目分析
给定一个正整数，找四个数这四个数的平方相加 = 给定的正整数，且四个数从小到大排序。
1. 根据一个基本思想，能for就for，那我们就for，不是找四个数吗，那我就for四次
2. 要枚举的数有什么特性？都是正整数 大于0，而且我们也可以很容易等到最大不超
过这个正整数的平方根，这样我们同时也把枚举的上下边界解决了。
3. 符合条件的判断 就是四个数的平方相加看是否 等于 给定的数
根据以上思路我们很容易写出以下代码
import java.util.Scanner;
class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int num = (int) Math.sqrt(n);
for(int i = 0;i < num;i++ ) {
for(int j = 0; j < num; j++) {
for(int k = 0; k < num;k++) {
for(int l = 0; l < num;l++) {
if(i*i + j*j + k*k + l*l == n) {
System.out.println(i+" "+j+" "+k+" "+l);
return;
}
}
}
}
}
scanner.close();
}
}
这样就可以了吗？我们测试下发现只能得50分，为什么不能拿满分，不是说枚举可行吗？
大家先别着急，这个题是一道编程题，哈哈是不是很震惊，（注：蓝桥杯编程题测试数据
是分多个层次的，层次越高数据规模越大，分数越高）编程题竟然用枚举拿了一半的分。
但是我还是想拿满分，毕竟这个题看起来不难，这个时候就要考虑第五步了，能否进
行简单优化。
我们在小学都知道a+b = c，a、b、c三个数知道其中任意两个可以求第三个数，那么我们
代入本题，总共有五个数我们只要知道四个数就可求第五个数了，我们知道和（给定的
数），那么我们只需要枚举三个数，最后一个数就是和 减去 三个数的平方之和，我们
求出了第四个数的平方，这个时候还没有结束
因为我们只知道第四个数的平方，这个数的平方根是否符合题目条件是个正整数呢，
所以我们需要再判断一下是否是正整数，使用平方根相乘是否等于原来的数即可
?3.代码实现
import java.util.Scanner;
class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int num = (int) Math.sqrt(n);
for(int i = 0;i < num;i++ ) {
for(int j = 0; j < num; j++) {
for(int k = 0; k < num;k++) {
int temp = n - i*i -j*j-k*k;
//注意类型转化 因为Math.sqrt()的返回值是浮点数 而temp是整数
if(temp == ((int)Math.sqrt(temp)*(int)Math.sqrt(temp))) {
System.out.println(i+" "+j+" "+k+" "+(int)Math.sqrt(temp));
return;
}
}
}
}
scanner.close();
}
}
这样我们就可以轻松拿满分了！！！ ???
?2.纯质数
?1.题目描述
?2.题目分析
首先看到这是一个填空题， 二话不说直接上来就枚举，枚举正整数
1. 能for就for
2. 正整数必须是纯质数，也就是这个数每个十进制数位都是质数，本身也是质数
3. 枚举上下边界题目给了1到20210605，使用个变量记录个数，每次符合条件就+1
4. 由于是个填空题，暂时不想优化
?3.代码实现
public class Main {
public static void main(String[] args) {
int res = 0;
for(int i = 2; i <= 20210605;i++) {
//符合条件就 +1
if(isprime(i) && f(i)) res++;
}
System.out.println(res);
}
//判断质数
static boolean isprime(int n) {
//判断素数 从2开始只需要枚举到平方根即可（注意1不是素数）
int num = (int) Math.sqrt(n);
for(int i = 2; i<= num; i++) {
if(n % i==0) return false;
}
return true;
}
//判断是否是纯质数
static boolean f(int n) {
//不知道循环次数，不能for就while 如果不清楚while()中写什么就直接true死循环
//然后在循环体里面判断 n 如果等于0 就break
while(n != 0) {
int t = n%10;
//怎么简单怎么来, 0 - 9不是质数的直接判断 然后不符合条件直接结束本次循环
if(t == 0 || t == 1 || t == 4 || t == 6 || t == 8 || t == 9) return false;
n /= 10;
}
return true;
}
}
注意代码在蓝桥云科的练习系统中运行超时，但是在本地是没问题的。我们直接在本地
运行出结果，填上（直接输出）就可以
?3.回文日期
?1.题目描述
?2.题目分析
首先是道编程题，可能会优化， 但是我还是枚举
题目说给一个八位正整数，表示日期，枚举的东西就是日期
1. 日期有什么特性？ 月份不能超过12，每个月份的天数都是确定的，还要注意闰年的
情况
2. 枚举的上下边界 给定日期的下一天到89991231，（在蓝桥云课上的测试系统测试
数据到99999999，可能之后增加了数据规模。在实际比赛时，不会出现题目给定范围和
测试不符的情况，大家放心）
3. 符合条件的情况，一种是回文的，一种既是回文，又要满足ABABBABA
直接上代码，细节注释在代码中
?3.代码实现
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
//记录是否找到第一个回文日期
boolean flag = true;
//从给定日期的下一天开始
for(int i = n+1;i <= 99999999;i++) {
//先检查日期是否合法
if(!valid(i)) continue;
//判断是否日期回文
if(f(i)) {
//判断是否已经找到给定日期之后第一个回文的日期了
if(flag){
//如果没有, 这是第一个就输出
System.out.println(i);
//flag 置为false 表示找到 给定日期之后第一个回文的日期了
flag = false;
}
//在回文日期的基本上判断 是否是ABABBABA型
if(check(i)) {
//如果找到直接输出，退出循环，这个时候两个都找到了
System.out.println(i);
break;
}
}
}
scan.close();
}
//判断日期是否合法
static boolean valid(int i) {
int[] month = {0,31,28,31,30,31,30,31,31,30,31,30,31};
//求年份
int yyyy = i/10000;
//求月份
int mm = i / 100 % 100;
//如果月份大于12 或者等于0 不合法
if(mm > 12 || mm == 0) return false;
//如果是闰年 2月份有29天
if((yyyy % 4 == 0 && yyyy % 100 !=0) || yyyy % 400 == 0) month[2] = 29;
else month[2]=28;
//判断天数
int dd = i % 100;
//如果天数大于 该月的天数 或者 等于0 不合法
if(dd > month[mm] || dd == 0) return false;
return true;
}
//判断是否是ABABBABA型的回文日期
static boolean check(int i) {
int[] nums = new int[8];
int k = 0;
//不能for就while 怎么简单怎么来
while(true) {
nums[k++] = i % 10;
i/=10;
if(i == 0) break;
}
//判断是否是ABABBABA型
if(nums[0] == nums[2] && nums[1] == nums[3] && nums[0] != nums[1]) return true;
else return false;
}
//判断日期是否回文
static boolean f(int i) {
String string = i +"";
StringBuffer sBuffer = new StringBuffer(string);
sBuffer.reverse();
return string.equals(sBuffer.toString());
}
}
成功通过！！！
由此可见，暴力枚举在蓝桥杯中占比较大，而且能够轻松得分，小伙伴们学废了吗???
如果文章对你有所帮助，希望能够三连支持一下???