Pure prime number

Title link: https://www.lanqiao.cn/problems/1561/learning/

Create an array to record whether each bit is a prime number or not

Traversing through each number, if it is a prime number, then all the numbers that are multiple of its integer are not prime numbers, set the filter directly in the array, and then judge if the prime number is pure, just need to judge if it is 2,3,5,7 bit by bit.

Why only judge integers of prime numbers?

Because for a nonprime number, its integer multiple must also be an integer multiple of a certain prime number, all must have been traversed, so there is no need to repeat the traversal

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];// Used to record whether each bit is a prime number or not

	public static void main(String[] args) {
		int ans = 0;
		Arrays.fill(nums, true);
		nums[0] = false;
		ArrayList<Integer> list = new ArrayList<>();// Save all pure prime numbers because you look at them yourself

		for (int i = 2; i < nums.length; i++) {
			if (nums[i] == true) {
				// Will be filtered out all times the prime number
				int j = i;
				while (j < nums.length) {
					nums[j] = false;
					j = j + i;
				}

				// Determine if the number is pure prime
				if (isPurePrime(i)) {
					list.add(i);
					ans++;
				}
			}

		}
		// System.out.println(list); This is just to see what numbers you need to comment out when submitting
		System.out.println(ans);
	}

	/**
	 * Determine if a number is pure prime, as long as you decide whether it is prime bit by bit
	 * 
	 * @param i
	 * @return
	 */
	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;
	}
}

Minimum weight

Title link: https://www.lanqiao.cn/problems/1461/learning/

When we add a weight, we are sure to want him to express more data range, so we use a little greedy idea here

If the range we can now represent is [ 1 , . . . , range ] [1,...,\text{range}] [1,...,range], so if we insert another weight, the maximum range he can represent is [ 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], based on the continuous relationship, we can get r a n g e + 1 = w − r a n g e range+1=w-range range+1=w_range, so there is w = 2 ∗ r a n g e + 1 w=2*range+1 w=2_range+1, the maximum representable range becomes when a weight is inserted 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; // range
		int res = 1; // Number of weights
		while (range < n) {
			range += (range + range + 1);
			res++;
		}
		System.out.println(res);
	}
}

irrigation

Title link: https://www.lanqiao.cn/problems/551/learning/

Using a queue to simulate the irrigation sequence, when irrigating a node, determine if the four surrounding nodes are within the farm range and join the queue if they are within the farm range and have not been irrigated

A Node class is created to represent each node with three attributes, its line number, column number, and the time it takes to irrigate it, making it easy to tell if the nodes around it need not be irrigated to

Another small trick is used in the code: using arrays to simulate the top, bottom, left, and right directions is equivalent to four if statements being reduced and the code looks a little more streamlined

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];// Farm size, indicating whether or not it has been irrigated

		Deque<Node> nodeDeque = new LinkedList<>();// Create a queue to simulate irrigation by time
		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));// The location of the book tube is irrigated by default

			farm[r][c] = true;// The marker has been irrigated
		}
		int k = sc.nextInt();
		sc.close();

		int ans = 0;

		// Four irrigation directions per plot, use this to avoid writing four if
		int[][] direction = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
		while (!nodeDeque.isEmpty()) {
			ans++;
			Node node = nodeDeque.removeFirst();
			// This means that when the time is over, you will no longer join its neighbors.
			if (node.k == k) {
				continue;
			}
			// Traverse it in four directions
			for (int i = 0; i < direction.length; i++) {
				int newR = node.r + direction[i][0];
				int newC = node.c + direction[i][1];

				// New nodes must be farm-wide and not irrigated
				if (newR >= 0 && newR < n && newC >= 0 && newC < m && farm[newR][newC] != true) {
					// Time is the current node's time+1
					nodeDeque.addLast(new Node(newR, newC, node.k + 1));
				}
			}
		}
		System.out.println(ans);
	}
}

class Node {
	int r;// That's ok
	int c;// column
	int k;// Time to Irrigate Here

	public Node(int r, int c, int k) {
		super();
		this.r = r;
		this.c = c;
		this.k = k;
	}
}