![三月八日蓝桥杯训练 [java]](http://www.mshxw.com/aiimages/31/759174.png "三月八日蓝桥杯训练 [java]")
纯质数最少砝码灌溉
纯质数题目链接：https://www.lanqiao.cn/problems/1561/learning/
创建一个数组，用于记录每一位是不是质数
遍历每一个数字，如果他是质数，那么其整数倍的所有数字都不是质数，直接在数组中设置过滤掉，然后再去判断这个质数是不是纯质数，只需要逐位判断是不是在2,3,5,7中即可
为什么只判断质数的整数倍？
因为对于非质数来说，它的整数倍肯定也是某个质数的整数倍，所有肯定已经遍历过了，因此就不用重复遍历了
package daily;
import java.util.ArrayList;
import java.util.Arrays;
public class day3_8_1 {
static int N = 20210605;
public static boolean[] nums = new boolean[N + 1];// 用来记录每一位是不是质数
public static void main(String[] args) {
int ans = 0;
Arrays.fill(nums, true);
nums[0] = false;
ArrayList list = new ArrayList<>();// 存下所有的纯质数，由于自己查看
for (int i = 2; i < nums.length; i++) {
if (nums[i] == true) {
// 将是该质数正数倍的全部过滤掉
int j = i;
while (j < nums.length) {
nums[j] = false;
j = j + i;
}
// 判断该数是不是纯质数
if (isPurePrime(i)) {
list.add(i);
ans++;
}
}
}
// System.out.println(list); 这里只是为了看有哪些数，提交时候需要注释掉
System.out.println(ans);
}
private static boolean isPurePrime(int i) {
while (i > 0) {
int rightBit = i % 10;
if (!(rightBit == 2 || rightBit == 3 || rightBit == 5 || rightBit == 7)) {
return false;
}
i = i / 10;
}
return true;
}
}
最少砝码
题目链接：https://www.lanqiao.cn/problems/1461/learning/
我们每加一个砝码，肯定是想让他表示更多的数据范围，这里就用到了一点贪心的思想
假如我们现在可以表示的范围为 [ 1 , . . . , range ] [1,...,text{range}] [1,...,range] ，那么如果我们再插入一个砝码，他可以表示的最大范围是 [ 1 , . . . , range , w − r a n g e , . . . , w , . . . r a n g e + w ] [1,...,text{range},w-range,...,w,...range+w] [1,...,range,w−range,...,w,...range+w] ，根据连续关系，我们可以得到 r a n g e + 1 = w − r a n g e range+1=w-range range+1=w−range，于是就有了 w = 2 ∗ r a n g e + 1 w=2*range+1 w=2∗range+1 ，插入一个砝码后最大可表示的范围就变成了 3 ∗ r a n g e + 1 3*range+1 3∗range+1
package daily;
import java.util.Scanner;
public class day3_8_2 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
sc.close();
int range = 1; // 量程
int res = 1; // 砝码数
while (range < n) {
range += (range + range + 1);
res++;
}
System.out.println(res);
}
}
灌溉
题目链接：https://www.lanqiao.cn/problems/551/learning/
使用队列模拟灌溉顺序，灌溉到一个节点的时候，判断其周围的四个节点是不是在农场范围内，如果在农场范围内并且没有被灌溉过就加入队列中
创建了Node类来表示每个节点，包含三个属性，其行号，列号，和灌溉到它所用的时间，方便判断其周围节点需不需要被灌溉到
另外在代码中使用了一个小trick：使用数组来模拟上下左右四个方向，相当于是减少了4个if语句，代码看起来更精简一点
package daily;
import java.util.Deque;
import java.util.linkedList;
import java.util.Scanner;
public class day3_8_3 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
boolean[][] farm = new boolean[n][m];// 农场大小，表示是否被灌溉过了
Deque nodeDeque = new linkedList<>();// 创建队列用于模拟灌按照时间灌溉
int t = sc.nextInt();
while (t > 0) {
t--;
int r = sc.nextInt() - 1;
int c = sc.nextInt() - 1;
nodeDeque.addLast(new Node(r, c, 0));// 出书管的位置默认已经灌溉好了
farm[r][c] = true;// 标记已经被灌溉过了
}
int k = sc.nextInt();
sc.close();
int ans = 0;
// 每块地的四个灌溉方向，使用这个可以避免写四个if
int[][] direction = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
while (!nodeDeque.isEmpty()) {
ans++;
Node node = nodeDeque.removeFirst();
// 这里说明时间结束了，就不继续加入其临近节点了
if (node.k == k) {
continue;
}
// 遍历它的四个方向
for (int i = 0; i < direction.length; i++) {
int newR = node.r + direction[i][0];
int newC = node.c + direction[i][1];
// 新节点必须在农场范围内并且没有被灌溉过
if (newR >= 0 && newR < n && newC >= 0 && newC < m && farm[newR][newC] != true) {
// 时间是当前节点的时间+1
nodeDeque.addLast(new Node(newR, newC, node.k + 1));
}
}
}
System.out.println(ans);
}
}
class Node {
int r;// 行
int c;// 列
int k;// 灌溉到这里用的时间
public Node(int r, int c, int k) {
super();
this.r = r;
this.c = c;
this.k = k;
}
}
