锐客网

  1. 首页 > it技术 > >

蓝桥杯|【蓝桥杯】每日一题冲刺国赛

职场和发展蓝桥杯

?今日学习?

1、纯质数的求解问题
2、BFS暴力求解问题
3、最少砝码规律问题
1、纯质数的求解问题
题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
如果一个正整数只有 11 和它本身两个约数，则称为一个质数（又称素数）。前几个质数是：2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, · · ·2,3,5,7,11,13,17,19,23,29,31,37,??? 。如果一个质数的所有十进制数位都是质数，我们称它为纯质数。例如：2,3, 5, 7, 23, 372,3,5,7,23,37 都是纯质数，而 11, 13, 17, 19, 29, 3111,13,17,19,29,31 不是纯质数。当然 1, 4, 351,4,35 也不是纯质数。请问，在 11 到 2021060520210605 中，有多少个纯质数？
运行限制
  • 最大运行时间：1s
  • 最大运行内存: 256M
package Day_Day_work; public class 纯质数 { public static void main(String[] args) { int ans = 0; int n = 20210605; for(int i=2; i<=n; i++) { if (A(i)) { if (B(i)) { ans++; } } } System.out.println(ans); } /* 暴力循环遍历 */ public static boolean A(int n) { if (n == 0 || n == 1) return false; for (int i = 2; i * i <= n; i++) { if (n % i == 0) return false; } return true; }public static boolean B(int n) { int t=0; while(n>0){ t=n%10; if(!A(t))return false; n=n/10; } return true; } }

题解分析：
主要将题目拆分成两个部分：
（1）求解该数是否为质数
（2）求解该数中的每一个十进制位是否为质数
（3）无脑暴力解，因为该题是填空题，所以忽略超时的问题
难点分析：
（1）容易眼高手低，暴力求解的问题很容易漏掉一些细节，比如说0不是质数等等

2、BFS暴力求解问题
题目描述
小蓝负责花园的灌溉工作。花园可以看成一个 nn 行 mm 列的方格图形。中间有一部分位置上安装有出水管。小蓝可以控制一个按钮同时打开所有的出水管，打开时，有出水管的位置可以被认为已经灌溉好。每经过一分钟，水就会向四面扩展一个方格，被扩展到的方格可以被认为已经灌溉好。即如果前一分钟某一个方格被灌溉好，则下一分钟它上下左右的四个方格也被灌溉好。给定花园水管的位置，请问 kk 分钟后，有多少个方格被灌溉好？
输入描述
输入的第一行包含两个整数 n, mn,m。
第二行包含一个整数 tt，表示出水管的数量。
接下来 tt 行描述出水管的位置，其中第 ii 行包含两个数 r, cr,c 表示第 rr 行第 cc 列有一个排水管。
接下来一行包含一个整数 kk。
其中，1≤n,m≤100,1≤t≤10,1≤k≤100。
输出描述
输出一个整数，表示答案。
输入输出样例
示例 1
输入：
3 6 2 2 2 3 4 1

输出：
9

运行限制
  • 最大运行时间：1s
  • 最大运行内存: 128M
package Day_Day_work; import java.util.Scanner; /** * @author yx * @date 2022-03-08 19:30 */ public class 花园浇水问题__BFS { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n=scanner.nextInt(); int m=scanner.nextInt(); int [][] A=new int[n+2][m+2]; int [][] B=new int[n+2][m+2]; int t=scanner.nextInt(); for(int i=1; i<=t; i++){ int x=scanner.nextInt(); int y=scanner.nextInt(); A[x][y]=1; B[x][y]=1; } int k=scanner.nextInt(); for (int i=1; i<=k; i++){ for (int q=1; q<=n; q++){ for (int p=1; p<=m; p++){ if(A[q][p]==1){ B[q-1][p]=1; B[q+1][p]=1; B[q][p+1]=1; B[q][p-1]=1; } } } A=B.clone(); } int ans=0; for (int i = 1; i <=n ; i++) { for (int j=1; j<=m; j++){ if(A[i][j]==1)ans++; } } System.out.println(ans); } }

题解分析：
（1）循环更新灌水的方格数
难点分析：
（1）创建两个数组，一个数组用来更新，一个数组用来存储
（2）每次更新完后，用来存储的数组都要克隆那个用来更新的数组
（3）增加数组的空间大小，起始位置从下标为1开始，避免数组越界等一系列问题
3、最少砝码规律问题
问题描述
你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意 小于等于 NN 的正整数重量。那么这套砝码最少需要包含多少个砝码？注意砝码可以放在天平两边。
输入格式
输入包含一个正整数 N。
输出格式
输出一个整数代表答案。
样例输入
7

样例输出
3

样例说明
33 个砝码重量是 1、4、61、4、6，可以称出 11 至 77的所有重量。
1 = 1；1=1；
2 = 6 ? 42=6?4(天平一边放 66，另一边放 44)；
3 = 4 ? 1；3=4?1；
4 = 4；4=4；
5 = 6 ? 1；5=6?1；
6 = 6；6=6；
7 = 1 + 6；7=1+6；
少于 33 个砝码不可能称出 11 至 77? 的所有重量。
评测用例规模与约定
对于所有评测用例，1 ≤ N ≤ 10000000001≤N≤1000000000。
运行限制
  • 最大运行时间：1s
  • 最大运行内存: 512M
package Day_Day_work; import java.util.Scanner; /** * @author yx * @date 2022-03-08 18:55 */ //找规律题1，3，5，7，9 public class 最少砝码 { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n=scanner.nextInt(); int i=1; int sum=0; int ans=0; while (sum


题解分析：
（1）刚开始看题目的时候会有一些蒙蔽，似曾相识但又无从下手的感觉
（2）这个时候我们不妨动笔去举一些样例，来发现其中的规律
难点分析：
（1）很难从中去发现一些规律，需要多枚举几个样例
（2）1、3、9砝码可以确定最大值13；1、3、9、27可以确定最大值40....找到其中的规律
蓝桥杯|【蓝桥杯】每日一题冲刺国赛
文章图片

【蓝桥杯|【蓝桥杯】每日一题冲刺国赛】

    推荐阅读


    上一篇：蓝桥杯每日一刷|蓝桥杯每日一刷（第四天2016）

    下一篇：webpack--性能优化之打包构建速度和代码调试优化