Tip: This article has 6000 words, rough reading takes about 5 minutes and intensive reading takes about 30 minutes
viewpoint
This year's provincial tournament is a little different from the past. It pays more attention to mathematics, algorithms and ideas, and is a little closer to ACM. I believe this is a trend, and the future Blue Bridge Cup will pay more attention to thinking
Tip: you can't look at the question without practicing. It's recommended to open the IDE and realize a wave by yourself!!!
A. Alphabet
Title: the Classl code value of letter A is 65, so what is the value of converting letter L into Classl code
Problem solving ideas
Method 1: count directly from A(65) to L(76)
Method 2: java program character L is forcibly converted to int
Output answer: 76
The code is as follows (example):
public class A letter {
public static void main(String[] args) {
System.out.println((int)'A');
System.out.println((int)'L');
}
}
B. Card
Problem solving ideas
Method 1: directly use hashmap simulation
Output answer: 3181
The code is as follows (example):
import java.util.HashMap;
public class B card {
/***
Use map to record the number of cards, and subtract 1 from each number
*/
public static void main(String[] args) {
HashMap<Integer,Integer> map = new HashMap<>();
map.put(0,2021);
map.put(1,2021);
map.put(2,2021);
map.put(3,2021);
map.put(4,2021);
map.put(5,2021);
map.put(6,2021);
map.put(7,2021);
map.put(8,2021);
map.put(9,2021);
int i=1;
for (;; i++) {
boolean flag = false;
int num = i;
while (true){
int temp = num%10;
if (map.get(temp)<=0){
flag = true;
break;
}
map.put(temp,map.get(temp)-1);
num = num/10;
if (num==0){
break;
}
}
if (flag)break;;
}
System.out.println(i-1);
}
}
C. Straight line
Problem solving ideas
Method 1: determine a straight line at two points, use the straight line to determine the general formula of the equation ax+by+c=0, calculate all triples (a,b,c), and then remove the duplication
Output answer: 40257
D. Cargo placement
Problem solving ideas
Method 1: arrange the combination questions, directly fix a number and find the combination of the other two digits
ps:
The amount of data is large, and the data type is long
Output answer: 2430
E. Path
Problem solving ideas
Method 1: use the least common multiple to create the weight of the graph, and then use floyd algorithm to calculate the shortest path
Output answer: 10266837
The code is as follows (example):
public class E route {
public static void main(String[] args) {
int gragh[][] = new int[2050][2050];
int n = 2021;
for (int i = 1; i <= n; i++) {
gragh[i][i] = 0;
for (int j = i + 1; j <= i + 21; j++) {
gragh[i][j] = gragh[j][i] = lcm(i, j);
}
}
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (gragh[i][k] + gragh[k][j] < gragh[i][j]) {
gragh[i][j] = gragh[i][k] + gragh[k][j];
}
}
}
}
System.out.println(gragh[1][n]);
}
private static int lcm(int i, int j) {
return i / gcd(i, j) * j;
}
private static int gcd(int i, int j) {
return j == 0 ? i : gcd(j, i % j);
}
}
F. Time display
Problem solving ideas
Method 1: simulation method, remove the days and take the remainder to calculate the hours, minutes and seconds
The code is as follows (example):
import java.util.Scanner;
public class F Time display {
/***
simulation
*/
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long n = sc.nextLong();
n/=1000;
int res = (int) (n % (24*60*60)); //The last day
int h = res/3600;
res %= 3600;
int m = res / 60;
res%=60;
System.out.println(h+":"+m+":"+res);//String. Just format it
}
}
G. Weight weighing
Problem solving ideas
Method 1: this question is the deformation of 01 backpack;
H. Yang Hui triangle
Problem solving ideas
Method 1: at that time, the idea and code of simulating Yang Hui triangle and then violent matching were relatively simple, but they could only cheat points
1. Bidirectional sorting
Problem solving ideas
Method 1: it's completely a violent trick. It's sorted directly with sort. There's a better way to comment and leave a message
J. Bracket sequence
Problem solving ideas
Method 1: dfs brute force cheat points, enumerate all possible results, and then judge whether it can be obtained by inserting the least number. If yes, count + +; The final count is the answer
The code is as follows (example):
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
public class J Bracket sequence {
/***
dfs Violent deception
()()()
This set container can count directly in dfs without the need, and count is set as a global variable
*/
static Set<String> set = new HashSet<>();
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.next();
int left = 0;
int right = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
left++;
} else {
right++;
}
}
//int count = Math.max(left, right);
int count;//Maximum number of parentheses
int sub;//The number of parentheses inserted cannot exceed sub, that is, the number of different parentheses
if (left > right) {
count = left;
sub = left - right;
} else {
count = right;
sub = right - left;
}
String temp = "";
for (int i = 0; i < count; i++) {
temp += "()";
}
dfs(temp);
System.out.println(set);
int resCount = 0;
for (String s1 : set) {
int i = 0;
int j = 0;
boolean isMatch = true;
while (i < s.length() && j < s1.length()) {
int tempCount = sub;
if (s.charAt(i) == s1.charAt(j)) {
i++;
j++;
} else {
j++;
tempCount--;
}
if (tempCount < 0) {
isMatch = false;
break;
}
}
if (isMatch) {
resCount++;
}
}
System.out.println(resCount);
}
private static void dfs(String temp) {
set.add(temp);
for (int i = 0; i < temp.length() - 1; i++) {
if (temp.charAt(i) == ')' && temp.charAt(i + 1) == '(') {
String temps = temp.substring(0, i) + "()" + temp.substring(i + 2, temp.length());
dfs(temps);
}
}
}
}
summary
In order to better improve the algorithm ability, we should brush more questions and classify them in the final analysis
If you have better ideas and solutions, I hope you can share a wave in the comment area