# Real topic of the 11th Java group B Blue Bridge Cup

### Write in front

Time flies, time flies, in a trance, the start of the Blue Bridge Cup is close at hand.. Why is it so official... Cough, the game will start tomorrow. As the saying goes, whet your gun when you are ready, you will be unhappy! Adhering to the excellent expertise of the Chinese nation, I came to brush the real problem of last year. From the overall difficulty of last year, if I went to the competition last year, saving three should not be a problem, but I don't know if it will become difficult this year. If he comes up with advanced mathematical formulas and finds various rules, DP, greed and backpack, I will simply abandon the competition. Advanced algorithms are not suitable for me. It's too difficult ~ ~, I only solved the first eight questions in this article. The last two questions really don't match my current paragraph, so I have the chance to continue in the future~~

Here's the real question - > > https://blog.csdn.net/kiwi_berrys/article/details/111600074

### Question 1: decryption (simple)

This water problem can give the result directly without programming.

```public class Main {

public static void main(String[] args) {
// EaFnjISplhFviDhwFbEjRjfIBBkRyY
// YeRikGSunlRzgDlvRwYkXkrGWWhXaA
// YeRikGSunlRzgDlvRwYkXkrGWWhXaA
System.out.println("YeRikGSunlRzgDlvRwYkXkrGWWhXaA");
}

}
```

### Question 2: Anniversary (OK)

For this type of questions, it is the operation time, so we use Java APILocalDate to do it. There are rich methods, so we can get the answer quickly.

```import java.time.LocalDate;

public class Main {

public static void main(String[] args) {
//52038720
//52,038,720
//The number of days between two days does not include the start date. If you want the result to include the start date, you need to add + 1 to the result
LocalDate d1 = LocalDate.of(2020, 7, 1);
LocalDate d2 = LocalDate.of(1921, 7, 23);
System.out.println((d1.toEpochDay() - d2.toEpochDay()) * 1440);
//System.out.println("52038720");
}

}
```

### Question 3: merge detection (medium)

Thinking question, but I didn't see the answer. It's really unexpected. The description of the question is a little vague, so this question has something

Let's put a question: https://www.cnblogs.com/liyexin/p/13810872.html

### Question 4: distribution of masks (medium)

At first glance, I can't do this problem, and then at first glance, I still can't, but I know that this problem is done by search. On the Internet, some people even use DP and knapsack problems.... Here I use the multi-path search of netizens: https://www.icode9.com/content-1-771621.html

• This problem is a typical recursive problem (multipath problem)
• The three parameters of dfs function are k, sum1 and sum2 respectively
k represents the subscript of the number being processed
sum1 is the number of masks in hospital 1
sum2 number of masks in No. 2 hospital
• When k=15, it means that all masks have been allocated. At this time, it is necessary to determine the difference between the minimum value and the current number of two hospitals
• Different paths are handled in the body of the function
The first one is for hospital 1
The second is for hospital 2
• After repeated recursive backtracking, the accountant calculates the minimum value of all distributions
```public class Main {
public static long res=Long.MAX_VALUE;
public static long num[]={9090400, 8499400, 5926800, 8547000, 4958200,
4422600, 5751200, 4175600, 6309600, 5865200,
6604400, 4635000, 10663400, 8087200, 4554000
};
public static void main(String[] args){
dfs(0, 0, 0);
System.out.println(res);
}
public static void dfs(int k,long sum1,long sum2 ) {
if(k==15) {
res=res<Math.abs(sum1-sum2)?res:Math.abs(sum1-sum2);
return;
}
dfs(k+1, sum1+num[k], sum2);
dfs(k+1, sum1, sum2+num[k]);
}
}//2400
```

### Question 5: maximum common divisor of Fibonacci sequence (medium)

This topic is to investigate the operation of large numbers, and then solve a maximum common divisor. The difficulty lies in the operation of large numbers

```//Method 1: this can be done. It's logically correct, but it must have timed out. My idea has been running for five minutes and still has no results, so I resolutely give it up and just provide an idea reference

import java.math.BigInteger;

/**
* The maximum common divisor of Fibonacci sequence is the maximum common divisor of 2020 and 520 items
*/
public class Main {

public static void main(String[] args) {
BigInteger b1 = fun(520);
BigInteger b2 = fun(2020);
BigInteger b = b1.gcd(b2);
System.out.println(b);
}

// Find the value of the nth term of Fibonacci sequence
public static BigInteger fun(int n) {
if (n == 1) {
return BigInteger.ONE;
}
if (n == 0) {
return BigInteger.ZERO;
}
return fun(n - 1).add(fun(n - 2));

}
}

//Can use array access method 2 very quickly

import java.math.BigInteger;

/**
* The maximum common divisor of Fibonacci sequence is the maximum common divisor of 2020 and 520 items
*/
public class Main {

public static void main(String[] args) {
BigInteger a = BigInteger.ONE;
BigInteger b = BigInteger.ONE;

BigInteger[] arr = new BigInteger;
arr = a;
arr = b;

for (int i = 3; i < arr.length; i++) {
arr[i] = arr[i - 1].add(arr[i - 2]);
}
System.out.println(arr.gcd(arr));
}

}
//6765
```

### Question 6: classified counting (simple)

This question.... Calling the API is still very simple. I can use character isDigit(),Character. isLOWerCase(),Character. Isuppercase().

```import java.util.Scanner;

public class Main {

public static void main(String[] args) {
Scanner input = new Scanner(System.in);
String s = input.next();
int c1 = 0, c2 = 0, c3 = 0;
for (int i = 0; i < s.length(); i++) {
// System.out.println(s.charAt(i));
if (Character.isDigit(s.charAt(i))) {
c1++;
} else if (Character.isLowerCase(s.charAt(i))) {
c2++;
} else if (Character.isUpperCase(s.charAt(i))) {
c3++;
}
}

System.out.println(c3);
System.out.println(c2);
System.out.println(c1);

}
}
```

### Question 7: sum eight times (simple)

This topic is also relatively simple. Just follow the idea of simulation. It is also to investigate the operation of large numbers, and then take the module.

```//Netizen answer
import java.math.BigInteger;
import java.util.Scanner;

public class Main {

public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n = input.nextInt();
// 1000000
BigInteger sum = BigInteger.ZERO;
for (int i = 1; i <= n; i++) {
BigInteger bi = BigInteger.ONE;
sum = sum.add(new BigInteger(i + "").pow(8));

}
System.out.println(sum.mod(new BigInteger("123456789")));

}
}

//I think so
import java.math.BigInteger;
import java.util.Scanner;

public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n = input.nextInt();
BigInteger sum = BigInteger.ZERO;

for (int i = 1; i <= n; i++) {
String s = Integer.toString(i);
BigInteger b = new BigInteger(s);
BigInteger m = b.pow(8);
sum = sum.add(m);// One thing to note here is that BIgInteger is immutable, so we must assign it to a variable
// System.out.println(sum);
}
System.out.println(sum.mod(new BigInteger("123456789")));
}
}
```

### Question 8: string encoding (difficult)

emmm, on the whole, this problem is still troublesome. The most important thing is how to judge that the largest letter is obtained. Therefore, we first convert the string into a string array. Using the array to operate is much more convenient than directly operating on the string. Then we traverse the string, and then combine the two character arrays to see whether it is less than 27, If it is less than, the whole is output, and if it is greater than, the first character is output. And so on.

```import java.util.HashMap;
import java.util.Scanner;

public class Main {

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String str = in.nextLine();
char[] c = str.toCharArray();
int i;
for (i = 0; i < str.length() - 1; i++) {
int a = c[i] - '0';
int b = c[i + 1] - '0';
int ans = a * 10 + b;
if (ans < 27) {
char ch = (char) (ans + 64);
System.out.print(ch);
i++;
} else {
char ch = (char) (a + 64);
System.out.print(ch);
}
}
if (i < str.length()) {
char ch = (char) (c[i] - '0' + 64);
System.out.print(ch);
}
}
}
```

### Question 9: BST insertion node problem (extreme, no)

I can't understand the title. Blind guess examines the insertion of tree nodes, but I can't... Cheat points and slip away...

### Question 10: network analysis (extreme, no)

I can't understand this question... Ha ha ha

Cheat points and slip away...

Note: the last two questions are a little difficult. I'll kill them when I improve my skills in the future!!

### Write at the end

The difficulty of this year's questions is indeed lower than that of previous years. I don't know whether it is psychological reasons or the reasons for reading the answers. I always feel that it is a little simpler than that of the 8th, 9th and 10th sessions. I haven't been as thorough as this session after reading the answers in the previous sessions. This year is basically a year with more large number of exercises. I remember that one year I took more exams in full arrangement. My mother, That's really laborious. Thanks to the APIBiginteger of Java, it's really difficult to operate. I don't know if tomorrow's problem will be more difficult than this year's problem. If I can't investigate the algorithms, then gg it. Let's take it as it comes. In a word, maybe I haven't worked hard enough, but I can't brush the questions. Some people always say that a person's potential is unlimited, but the premise of stimulating potential is always a touch stimulation stage. Maybe losing the game tomorrow is the best stimulation for me. This blue bridge cup may be the last algorithm competition I participated in, because I have to work, We need to work hard to expand the technology stack and prepare for the interview, so there will be no time to participate in the algorithm competition. Anyway, just keep working hard. Post a paragraph of my favorite words to cheer me up for tomorrow's game. hh~

If life is like an ant, it should be ambitious. Life is as thin as paper, but it has an unyielding heart. The world is uncertain. You and I are all dark horses. One day, it will soar!!

Keywords: Java Algorithm string

Added by kingman65 on Sat, 05 Mar 2022 00:55:05 +0200