Blue Bridge Cup: national software and information technology professionals competition [1] is a national IT discipline competition organized by the talent exchange center of the Ministry of industry and information technology. More than 1200 colleges and universities across the country, including Peking University, Tsinghua University and Shanghai Jiaotong University, participated in the competition, with a total number of more than 400000 participants. [2]
In 2020, Blue Bridge Cup The competition was included in the "ranking list of national discipline competitions in Colleges and universities" issued by the Chinese society of higher education. It is an important competition item for the reform of education and teaching and the cultivation of innovative talents in Colleges and universities. [3]
Background: preparations for the 13th Blue Bridge Cup Java provincial competition
Blue Bridge Cup Official Website: https://dasai.lanqiao.cn/pages/dasai/index.html
catalogue
Answer requirements
Title Description
Note: to answer the question, please click the "submit this question" button at the top of the page. The page will jump to the page of submitting the code. Select your compilation language, paste your written code into the code box, and then click "submit answer".
After your answer is submitted to the system, the system will automatically score your code and jump to the list of results. You can directly see the status of your submitted code from the list. Generally, you can see the score result after a few seconds.
As the first question, the code of C + + and Java has been given in the prompt. You can directly copy this code and submit it as your own code.
Note in particular that the Main class name of Java must be Main.
Topic 1
Xiaolan's IP address is 192.168. * 21, where * is a number. What is the maximum possible number?
Answer: 255
Solution: it is composed of 32-bit binary numbers. The IP address is a 4-byte binary number, which is divided into 4 segments. Each segment has 8-bit binary numbers, a total of 32-bit binary numbers. An IP address is divided into two parts, i.e. network address and host address. From the numerical range, it can be judged that the maximum value is 255 (2 ^ 8-1 = 255), that is, common sense.
Topic 2
If an integer g can divide integers A and B at the same time, g is said to be the common divisor of A and B. For example, 43 is the common divisor of 86 and 2021.
How many common numbers (including 2021) are greater than 2021.
Please note that 2021 and 2021 have a common divisor greater than 1, so we need to calculate one when calculating.
Answer: 89
Solution: gcd function is a function for finding the common divisor in Java. It is searched one by one from 1 to 2021. When its common divisor with itself is greater than 1, that is, greater than or equal to 2, it indicates that it has a common divisor and count s
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int count = 0;
for (int i = 1; i <= 2021; i++) {
if (gcd(i, 2021) > 1) {
count++;
}
}
System.out.println(count);
}
static int gcd(int a, int b) {
return b > 0 ? gcd(b, a % b) : a;
}
}Topic 3
2021 is a very special number, which can be expressed as the square difference of two non negative integers, 2021 = 45 * 45 - 2 * 2.
2025 is also a special number, which can be expressed as 2025 = 45 * 45 - 0 * 0. How many such numbers are there from 1 to 2021?
Please note that some numbers can be expressed in many ways, such as 9 = 3 * 3 - 0 * 0 = 5 * 5 - 4 * 4, which is calculated only once when calculating the answer.
Answer: 1516
Solution: the purpose of full matching can be achieved by iterating through nested loops. This involves a mathematical problem, sum= a*a - b*b, that is, sum = (a+b)(a-b). When sum is a positive number, B < A, B is an inner loop. Since the value of sum is (1 < = sum < = 2021), in order to obtain the minimum positive number, there is a+b=1 or a-b=1. Obviously, if a-b=1 is true, there is b=a-1, Substitute the expression sum = (a+a-1)(a-a+1), then 2021 = 2a-1, a=1011. If the conditions are met, it is recorded as 1. Count statistics, so there are the following codes:
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int count = 0;
int[] arr = new int[2022];
for (int i = 1; i <= 1011; i++) {
for (int j = 0; j < i; j++) {
int sum = i * i - j * j;
if (sum <= 2021) {
arr[sum] = 1;
}
}
}
for (int j = 1; j <= 2021; j++) {
if (arr[j] == 1)
count++;
}
System.out.println(count);
}
}Topic 4
Xiaolan wants to use the 01 string to express a paragraph of text, which contains 6 letters of a, b, c, d, e and f. the number of occurrences of each letter is as follows: 10 times for a, 20 times for b, 3 times for c, 4 times for d, 18 times for E and 50 times for f.
Xiaolan is going to use the determined 01 string for each letter. The 01 string length of different letters can be different.
When representing text, the 01 string corresponding to each letter is directly connected to form the final 01 string. In order to restore the text normally, the code of Xiaolan must be a prefix code, that is, the 01 string corresponding to any character cannot be the prefix of the 01 string corresponding to another character.
For example, the following is a valid encoding:
a: 000
b: 111
c: 01
d: 001
e: 110
f: 100
Where the length of c is 2 and the coding length of other letters is 3. In this way, the total length required for this text is: 103 + 203 + 32 + 43 + 183 + 503 = 312.
The above coding is obviously not optimal. Changing the coding of f to 10 still meets the conditions, but the total length is 262, which is 50 shorter.
In order to minimize the total length after encoding, the encoding corresponding to the characters with more occurrences should be shorter and the encoding corresponding to the characters with less occurrences should be longer.
In the best case, what is the minimum total length after coding?
Answer: 219
Solution: Huffman code. I suggest you know it. Here are two links
13 minutes to learn Huffman coding
Topic 5
The following matrix contains six characters of ABCDEF. How many times did the most characters appear?
FFEEFEAAECFFBDBFBCDA
DACDEEDCCFFAFADEFBBA
FDCDDCDBFEFCEDDBFDBE
EFCAAEECEECDCDECADDC
DFAEACECFEADCBFECADF
DFBAAADCFAFFCEADFDDA
EAFAFFDEFECEDEEEDFBD
BFDDFFBCFACECEDCAFAF
EFAFCDBDCCBCCEADADAE
BAFBACACBFCBABFDAFBE
FCFDCFBCEDCEAFBCDBDD
BDEFCAAAACCFFCBBAAEE
CFEFCFDEEDCACDACECFF
BAAAFACDBFFAEFFCCCDB
FADDDBEBCBEEDDECFAFF
CDEAFBCBBCBAEDFDBEBB
BBABBFDECBCEFAABCBCF
FBDBACCFFABEAEBEACBB
DCBCCFADDCACFDEDECCC
BFAFCBFECAACAFBCFBAF
Answer: 78
Solution: HashMap is very efficient for this problem. At the beginning, when it is judged that there are no characters, set the mapping value to 1. Then, when it is judged that there are characters, add 1 to the value, cycle all characters, and finally get to output the value corresponding to each key
import java.util.HashMap;
import java.util.Map;
public class Main {
static String chars =
"FFEEFEAAECFFBDBFBCDA" +
"DACDEEDCCFFAFADEFBBA" +
"FDCDDCDBFEFCEDDBFDBE" +
"EFCAAEECEECDCDECADDC" +
"DFAEACECFEADCBFECADF" +
"DFBAAADCFAFFCEADFDDA" +
"EAFAFFDEFECEDEEEDFBD" +
"BFDDFFBCFACECEDCAFAF" +
"EFAFCDBDCCBCCEADADAE" +
"BAFBACACBFCBABFDAFBE" +
"FCFDCFBCEDCEAFBCDBDD" +
"BDEFCAAAACCFFCBBAAEE" +
"CFEFCFDEEDCACDACECFF" +
"BAAAFACDBFFAEFFCCCDB" +
"FADDDBEBCBEEDDECFAFF" +
"CDEAFBCBBCBAEDFDBEBB" +
"BBABBFDECBCEFAABCBCF" +
"FBDBACCFFABEAEBEACBB" +
"DCBCCFADDCACFDEDECCC" +
"BFAFCBFECAACAFBCFBAF";
public static void main(String[] args) {
Map<Character, Integer> map = new HashMap<>();
for(int i = 0; i < chars.length(); i++) {
char ch = chars.charAt(i);
if(ch == 'A' || ch == 'B' || ch == 'C' || ch == 'D' || ch == 'E' || ch == 'F') {
if(!map.containsKey(ch)) {
map.put(ch, 1);
} else {
map.put(ch, map.get(ch) + 1);
}
}
}
System.out.println(map.get('A'));
System.out.println(map.get('B'));
System.out.println(map.get('C'));
System.out.println(map.get('D'));
System.out.println(map.get('E'));
System.out.println(map.get('F'));
}
}Topic 6
Problem description
Xiao Lan is going to the store to buy a pencil.
Pencils must be bought in a whole box, with 12 pencils in a whole box. The price is p yuan.
Xiaolan needs to buy at least t pencils. How much does it cost him at least?
Input format
The input line contains two integers p and t, separated by a space.
Output format an output line contains an integer representing the answer.
sample input
5 30
sample output
15
Example description
Xiaolan needs to buy at least 3 boxes to buy 30 pencils, which costs a total of 15 yuan.
Scale and agreement of evaluation cases
For all evaluation cases, 1 < = P < = 100, 1 < = T < = 10000.
Solution: less than 12 into 1 direct calculation
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int p = input.nextInt();
int t = input.nextInt();
int num = t / 12;
int rem = t % 12;
if (rem > 0) {
num = num + 1;
}
System.out.println(num * p);
}
}
Title VII
Problem description
Given the lengths a, B and C of the three sides of a triangle, is this triangle a right triangle.
Input format
The input line contains three integers a, B and C, which represent the length of the three sides of the triangle, and the adjacent integers are separated by a space.
Output format
If it is a right triangle, output "YES" (all uppercase), otherwise output "NO" (all uppercase).
sample input
3 4 5
sample output
YES
sample input
4 5 4
sample output
NO
Scale and agreement of evaluation cases
For all evaluation cases, 1 < = a, B, C < = 1000.
The composition condition of a triangle is: among the three sides of a triangle, any side is greater than the difference between the other two sides, and any side is less than the sum of the other two sides.
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int a = input.nextInt();
int b = input.nextInt();
int c = input.nextInt();
if ((a + b > c || a + c > b || b + c > a) && (a - b < c || a - c < b || b - c < a)) {
if (a * a + b * b == c * c || a * a + c * c == b * b || b * b + c * c == a * a) {
System.out.println("YES");
} else {
System.out.println("NO");
}
} else {
System.out.println("NO");
}
}
}Topic 8
Problem description
n children are playing a game. Everyone should share their own little secret.
Each child has a number from 1 to n, and the number is not repeated.
In order to make the game more interesting, the teacher sent each child a card with a number from 1 to n, and each number appeared exactly once.
Each child writes his secret on paper, and then passes the secret to the children with the corresponding number according to the number on the card sent by the teacher. If the number given by the teacher is exactly his own number, the secret will remain in his own hands.
After the children get the secret of others, they will write down the secret. The teacher will command all children to continue to pass the secret in their hands, and still pass the secret to the children with the corresponding number according to the number on the card issued by the teacher.
This is repeated n times.
Now, every child has written down many secrets.
Now the teacher wants to find some children who can tell all the secrets. How many children should the teacher find at least?
Input format
The first line of input contains an integer n.
The second line contains n integers a[1], a[2],..., a[n]. The adjacent integers are separated by spaces, representing the numbers received by children numbered 1 to n respectively.
Output format
The output line contains an integer representing the answer.
sample input
6
2 1 3 5 6 4
sample output
3
Example description
Finally, children 1 and 2 know each other's secrets, children 3 only know their own secrets, and children 4, 5 and 6 know each other's secrets.
It takes at least three children to tell all the secrets.
Scale and agreement of evaluation cases
For 30% of the evaluation cases, 2 < = n < = 30.
For 60% of the evaluation cases, 2 < = n < = 1000.
For all evaluation cases, 2 < = n < = 100000.
Problem solution: the parallel search algorithm is like a linked list. The contents of this linked list will be known by everyone in the linked list. In the final analysis, it is to search the chain. Here are two links
And collect basic | rookie tutorial
And search the collection to quickly find the rookie tutorial
import java.util.Scanner;
public class Main {
static int n;
static int[] a;
static int num = 0;
static int find(int k) {
if (a[k] == k)
return k;
return a[k] = find(a[k]);
}
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
n = input.nextInt();
int[] friends = new int[n + 1];
a = new int[n + 1];
for (int i = 1; i <= n; i++) {
a[i] = i;
friends[i] = input.nextInt();
}
for (int i = 1; i <= n; i++) {
if (find(i) != find(friends[i]))
a[find(i)] = find(friends[i]);
}
for (int i = 1; i <= n; i++) {
if (a[i] == i)
num++;
}
System.out.println(num);
}
}
Topic 9
Problem description
A permutation from 1 to n is called a semi increasing sequence, which means that the value at the odd position in the permutation increases monotonically, and the value at the even position also increases monotonically.
For example: (1, 2, 4, 3, 5, 7, 6, 8, 9) is a semi incremental sequence, because its values at odd positions are 1, 4, 5, 6, 9, monotonically increasing, and the values at even positions are 2, 3, 7, 8, monotonically increasing.
How many of the increasing sequences are from 1 to half?
Input format
The input line contains a positive integer n.
Output format
The output line contains an integer indicating the answer. The answer may be large. Please output the remainder of the answer divided by 1000000007.
sample input
5
sample output
10
Example description
There are the following semi incremental sequences:
(1, 2, 3, 4, 5)
(1, 2, 3, 5, 4)
(1, 2, 4, 3, 5)
(1, 3, 2, 4, 5)
(1, 3, 2, 5, 4)
(1, 4, 2, 5, 3)
(2, 1, 3, 4, 5)
(2, 1, 3, 5, 4)
(2, 1, 4, 3, 5)
(3, 1, 4, 2, 5)
Scale and agreement of evaluation cases
For 50% of the evaluation cases, 2 < = n < = 20.
For all evaluation cases, 2 < = n < = 1000.
Solution: for the problem of permutation and combination, suppose 100 numbers, 50 odd numbers increase, and the other 50 even numbers must increase and be unique, because there are only 50 numbers left and need to meet the increase. The same number and even number are introduced into different parameters for remainder calculation
import java.util.Scanner;
public class Main {
public static long group(long a, long b) {
long ans = 1;
int rem = (int) 1e9 + 7;
for (long i = 1, j = a; i <= b; i++, j--) {
ans = ans * (j / i) % rem;
}
return ans;
}
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
long n = input.nextLong();
if (n % 2 == 0) {
System.out.println(group(n, n / 2));
} else
System.out.println(group(n, (n + 1) / 2));
}
}Topic 10
Problem description
Xiao Lan lives in LQ city. Today he is going to Xiao Qiao's house. LQ city can be regarded as a square graph with n rows and m columns. Xiao Lan's family lives in row 1, column 1, and Xiao Qiao's family lives in row n, column M. Xiao Lan can walk inside the grid. He doesn't want to go outside the grid. Some places in the city are scenic parks and some places are bustling streets. Xiao Lan likes the park very much and doesn't like the street. He marked each grid with an attribute, either the park he liked or the street he didn't like as 1 or 2. The places where Xiao Lan and Xiao Qiao live are marked as 1. Xiaolan can only go from one square to the adjacent square in the same row or column at a time. He wants to find a way to make him walk the street marked 2 twice in a row. How many times does he have to go through the street at least on this premise?
Input format
The first line of input contains two integers n, m, separated by a space. The next N lines, each with an m-th digital string, represent the annotation of the city.
Output format
The output line contains an integer representing the answer. If there is no scheme that meets the conditions, output - 1.
sample input
3 4 1121 1211 2211
sample output
1
sample input
3 4 1122 1221 2211
sample output
-1
sample input
5 6 112121 122221 221212 211122 111121
sample output
5
Scale and agreement of evaluation cases
For 50% of the evaluation cases, 2 < = n, m < = 20. For all evaluation cases, 2 < = n, m < = 300.
Answer: it seems that this problem is not for me. There is no idea. Learn from the idea of the great God and search it with dfs
reference resources:
Algorithm basis: visual interpretation of BFS and DFS
BFS and DFS algorithms - short book
import java.util.Scanner;
public class Main {
private static final int INF = 0x3f3f3f3f;
private static int n, m, res = INF;
private static int[][] map = new int[305][305];
private static boolean[][] st = new boolean[305][305];
private final static int[][] next = {
{-1, 0}, {0, 1}, {1, 0}, {0, -1}
};
private static void dfs(int x, int y, int count) { //count records the number of streets that have been passed
if(x == n - 1 && y == m - 1) {
// It's the end
res = Math.min(res, count);
return;
}
st[x][y] = true;
for(int i = 0; i < 4; i++) {
int tx = x + next[i][0];
int ty = y + next[i][1];
if(tx < 0 || tx >= n || ty < 0 || ty >= m) continue;
if(st[tx][ty]) continue;
if(map[tx][ty] == 2 && map[x][y] == 2) continue;
dfs(tx, ty, map[x][y] == 2 ? count + 1 : count);
}
st[x][y] = false;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
for(int i = 0; i < n; i++) {
String line = sc.next();
for(int j = 0; j < m; j++) {
int ch = line.charAt(j);
int cur = ch - '0';
map[i][j] = cur;
}
}
dfs(0, 0, 0);
if(res == INF) res = -1;
System.out.println(res);
}
}
summary
Intuitive summary: the nine courses before the simulation game still have the power of the first war. It generally needs some computer common sense, built-in functions in Java, violent solution of for, conversion of characters, strings, shaping, some set frameworks, and set search, arrangement and combination problems. Review and summarize more. I believe it will not be difficult to save the game
Algorithm practice
59. Preparing for the Blue Bridge Cup - Java algorithm (basic exercise 1)_ Thomas kutao's blog - CSDN blog practice directory topic 1
https://blog.csdn.net/m0_54925305/article/details/122367512?spm=1001.2014.3001.550160. Preparing for the Blue Bridge Cup - Java algorithm (basic exercise 2)_ Thomas kutao's blog CSDN blog Blue Bridge Cup: national software and information technology professionals competition [1] is a national IT discipline competition organized by the talent exchange center of the Ministry of industry and information technology. More than 1200 colleges and universities across the country, including Peking University, Tsinghua University and Shanghai Jiaotong University, participated in the competition, with a total number of more than 400000 participants. [2] In 2020, the Blue Bridge Cup competition was included in the "ranking list of national discipline competitions in Colleges and universities" issued by the Chinese society of higher education. It is an important competition project for the reform of education and teaching and the cultivation of innovative talents in Colleges and universities. [3] Background: the 13th Blue Bridge Cup Java group provincial competition preparation practice directory answer requirements note: to answer questionshttps://blog.csdn.net/m0_54925305/article/details/122505817?spm=1001.2014.3001.5501
Daily enlightenment:
Everything urges me to grow, and there is no reason to stop
-- Thomas