2020 Blue Bridge Cup National Championship Java University Group B Problem Solving Report

2020 Blue Bridge Cup National Championship Java University Group B Problem Solving Report

Question A: Beautiful 2

Problem Description


Xiaolan likes 2 very much. This year is 2020 AD. He is very happy. He is very curious. From 1 to 2020 (inclusive), how many years contain the number 2 in the digits?

Answer submission


This is a fill-in-the-blank question, you only need to calculate the result and submit it. The result of this question is an integer. Only fill in this integer when submitting the answer. If you fill in the extra content, you will not be able to score.
import java.io.*; import java.util.*; //Two packages, io and util, are needed in the custom Read class. The asterisk * (wildcard) means all classes in the package import java.math.* ; //BigInteger with large numbers import java.util.Comparator; import java.util.PriorityQueue; import java.util.Queue; import java.util.Scanner; import java.util.StringTokenizer; public class Main { static int INF = 0x3f3f3f3f ; public static void main (String[] args) { int cnt = 0 ; for ( int i = 1 ;i <= 2020 ;i++) if (( "" + i).contains ( "2" ))cnt++; System.out.println(cnt); } } Copy code

Answer: 563

Question B: Diffusion

Problem Description


Xiaolan paints on an infinitely large special canvas. This canvas can be seen as a grid graph, and each grid can be represented by a two-dimensional integer coordinate. Xiao Lan first clicked a few points on the canvas: (0, 0), (2020, 11), (11, 14), (2000, 2000). Only these grids are black, and the other positions are white. Every minute, the black will spread a little. Specifically, if a grid is black, it will spread to the four adjacent grids on the top, bottom, left, and right, making these four grids also become black (if it was originally black, then it will still be black). Excuse me, after 2020 minutes, how many squares on the canvas are black.

Answer submission


This is a fill-in-the-blank question, you only need to calculate the result and submit it. The result of this question is an integer. Only fill in this integer when submitting the answer. If you fill in the extra content, you will not be able to score.

Ideas


Expand the capacity, and then divide it into 2020 layers to use BFS simulation.
import java.io.*; import java.util.*; //Two packages, io and util, are needed in the custom Read class. The asterisk * (wildcard) means all classes in the package import java.math.* ; //BigInteger with large numbers import java.util.Comparator; import java.util.PriorityQueue; import java.util.Queue; import java.util.Scanner; import java.util.StringTokenizer; public class Main { static int INF = 0x3f3f3f3f ; static class Node { int x, y, dp; Node( int x, int y, int dp){ this .x = x; this .y = y; this .dp = dp; vis[x][y] = 1 ; //You can use markers in the constructor } } static int vis[][] = new int [ 7500 ][ 7500 ]; static Queue<Node>q = new LinkedList<Node>(); public static void main (String[] args) { int cnt = 4 ; //The initial 4 black dots q.add( new Node( 0 + 2050 , 0 + 2050 , 0 )); q.add( new Node( 2020 + 2050 , 11 + 2050 , 0 )); q.add( new Node( 11 + 2050 , 14 + 2050 , 0 )); q.add( new Node( 2000 + 2050 , 2000 + 2050 , 0 )); while (!q.isEmpty()) { Node nd = q.poll(); if (nd.dp == 2020 ) break ; if (vis[nd.x + 1 ][nd.y] == 0 ) { q.add( new Node(nd.x + 1 , nd.y, nd.dp + 1 )); cnt++; } if (vis[nd.x- 1 ][nd.y] == 0 ) { q.add( new Node(nd.x- 1 , nd.y, nd.dp + 1 )); cnt++; } if (vis[nd.x][nd.y + 1 ] == 0 ) { q.add( new Node(nd.x, nd.y + 1 , nd.dp + 1 )); cnt++; } if (vis[nd.x][nd.y- 1 ] == 0 ) { q.add( new Node(nd.x, nd.y- 1 , nd.dp + 1 )); cnt++; } } System.out.println(cnt); } } Copy code

Answer: 20312088

Question C: Factorial Divisor

Problem Description


Define the factorial n! = 1 2 3 n. May I ask how many divisors are there in 100! (the factorial of 100).

Answer submission


This is a fill-in-the-blank question, you only need to calculate the result and submit it. The result of this question is an integer. Only fill in this integer when submitting the answer. If you fill in the extra content, you will not be able to score.

Ideas


Basic theorem of arithmetic decompose prime factors + theorem of divisors to find the number of divisors
import java.io.*; import java.util.*; //Two packages, io and util, are needed in the custom Read class. The asterisk * (wildcard) means all classes in the package import java.math.* ; //BigInteger with large numbers import java.util.Comparator; import java.util.PriorityQueue; import java.util.Queue; import java.util.Scanner; import java.util.StringTokenizer; public class Main { static int INF = 0x3f3f3f3f ; public static void main (String[] args) { int p[] = new int [ 200 ]; for ( int i = 2 ;i <= 100 ;i++) { int t = i; for ( int j = 2 ;j <= t;j++) { while (t% j == 0 ) { p[j]++; t/= j; } } } long ans = 1 ; for ( int i = 2 ;i <= 100 ;i++) if (p[i] != 0 ) ans *= (p[i] + 1 ); System.out.println(ans); } } Copy code

Answer: 39001250856960000

Question D: Essential Ascending Sequence

Problem Description


Xiaolan likes things that are monotonously increasing. In a character string, if several characters are taken out, and these characters are monotonically increasing after arranging them in the order in the character string, it becomes a monotonically increasing subsequence in the character string. For example, in the string lanqiao, if the characters n and q are taken out, nq forms a monotonically increasing subsequence. Similar monotonically increasing subsequences include lnq, i, ano and so on. Xiaolan found that although some subsequences have different positions, the character sequence is the same. For example, taking the second character and the last character can get ao, and taking the last two characters can also get ao. Xiaolan believes that they are not fundamentally different. For a string, Xiaolan wants to know how many essentially different incremental subsequences are there? For example, for the string lanqiao, there are 21 essentially different increasing subsequences. They are l, a, n, q, i, o, ln, an, lq, aq, nq, ai, lo, ao, no, io, lnq, anq, lno, ano, aio. For the following string (a total of 200 lowercase English letters, displayed in four lines): (If you copy the following text to a text file, please be sure to check whether the copied content is consistent with the document. There is one in the test directory File inc.txt, the content is the same as the text below)

Answer submission


This is a fill-in-the-blank question, you only need to calculate the result and submit it. The result of this question is an integer. Only fill in this integer when submitting the answer. If you fill in the extra content, you will not be able to score.

Ideas


Pruning searches for all cases. If the prefix of a case has already appeared, then there is no need to search down.
import java.io.*; import java.util.*; //Two packages, io and util, are needed in the custom Read class. The asterisk * (wildcard) means all classes in the package import java.math.* ; //BigInteger with large numbers import java.util.Comparator; import java.util.PriorityQueue; import java.util.Queue; import java.util.Scanner; import java.util.StringTokenizer; public class Main { static int INF = 0x3f3f3f3f ; static Set<String> s = new HashSet<>(); static String SS = "tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhfiadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqijgihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmadvrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl" ; static void dfs ( int st, String cur) { if (s.contains(cur)) return ; s.add(cur); for ( int i = st + 1 ; i <ss.length(); i++) { if (( int ) ss.charAt(st) <( int ) ss.charAt(i)) dfs(i, cur + ss.charAt(i)); } return ; } public static void main (String[] args) { for ( int i = 0 ; i <ss.length(); i++) dfs(i, "" + ss.charAt(i)); System.out.println(s.size()); } } Copy code

Answer: 3616159

Question E: Toy Snake

Problem Description


Toy snake

Answer submission


This is a fill-in-the-blank question, you only need to calculate the result and submit it. The result of this question is an integer. Only fill in this integer when submitting the answer. If you fill in the extra content, you will not be able to score.


Ideas


Search for every possible starting point and pay attention to pruning.

answer


552
public class Main { static int map[][] = new int [ 20 ][ 20 ]; static int cnt; static void dfs ( int x, int y, int num) { if (x < 1 || y < 1 | | x> 4 || y> 4 ) return ; if (map[x][y] != 0 ) return ; map[x][y] = num; if (num == 16 ) { cnt++; for ( int i = 1 ;i <= 4 ;i++) { for ( int j = 1 ;j <= 4 ;j++) System.out.print(map[i][j] + "" ); System.out.println(); } System.out.println(); map[x][y] = 0 ; return ; } dfs(x + 1 , y, num + 1 ); dfs(x- 1 , y, num + 1 ); dfs(x, y + 1 , num + 1 ); dfs(x, y- 1 , num + 1 ); map[x][y] = 0 ; } public static void main (String[] args) { for ( int i = 1 ;i <= 4 ;i++) for ( int j = 1 ;j <= 4 ;j++) dfs(i, j, 1 ); System.out.println(cnt); } } Copy code

Question F: Blue Peptide Subsequence

Problem Description


The living things on planet L are composed of egg blue substances. Each type of egg blue substance is folded end to end into a long chain of materials called blue peptides.
Biologist Xiao Qiao is studying the egg blue quality on planet L.
She got the blue peptide sequences of two blue cyanins and wanted to analyze the similarity of the two blue peptides based on the common characteristics of the two blue peptide sequences.
Specifically, a blue peptide can be represented by 1 to 5 English letters, where the first letter is capitalized and the subsequent letters are lowercase.
An egg blue peptide sequence can be spliced by the sequence of blue peptides.
In a blue peptide sequence, if some positions are selected, the blue peptides at these positions are taken out and placed according to their positions in the original sequence, it is called a subsequence of this blue peptide.
The subsequence of the blue peptide is not necessarily continuous in the original sequence, and there may be some blue peptides that have not been taken out in the middle.
If a subsequence that can be extracted from the first blue peptide sequence is equal to a certain subsequence extracted from the second blue peptide sequence, it is called a common blue peptide subsequence.
Given two blue peptide sequences, find out the length of their longest common blue peptide subsequence.

Input format


Enter two lines, each line contains a string representing a blue peptide sequence. There are no delimiters such as spaces in the string.

Output format


Output an integer that represents the length of the longest common blue peptide subsequence.

Sample input


LanQiaoBei
LanTaiXiaoQiao

Sample output


2

Sample description


The longest common blue peptide subsequence is LanQiao, with two blue peptides in total.

Evaluation use case scale and conventions


For 20% of the evaluation cases, the length of the two strings does not exceed 20.
For 50% of the evaluation cases, the length of the two strings does not exceed 100.
For all evaluation cases, the length of the two strings does not exceed 1000.

Ideas


Convert the string according to the conditions, and then calculate the longest common subsequence.
import java.io.*; import java.util.*; //Two packages, io and util, are needed in the custom Read class. The asterisk * (wildcard) means all classes in the package import java.math.* ; //BigInteger with large numbers import java.util.Comparator; import java.util.PriorityQueue; import java.util.Queue; import java.util.Scanner; import java.util.StringTokenizer; public class Main { static String ss1[] = new String[ 1005 ]; static String ss2[] = new String[ 1005 ]; static int dp[][] = new int [ 1005 ][ 1005 ]; public static void main (String[] args) { Scanner cin = new Scanner(System.in); String s1 = cin.next(); String s2 = cin.next(); int cnt1 = 1 ;ss1[ 1 ] = "" ;ss2[ 1 ] = "" ; int f = 0 ; for ( int i = 0 ; i <s1.length(); i++) { if (s1.charAt( i) >= 'A' && s1.charAt(i) <= 'Z' ) { if (f == 1 ) { f = 0 ; i--; cnt1++; ss1[cnt1] = "" ; continue ; } else f = 1 ; } ss1[cnt1] += s1.charAt(i); } int cnt2 = 1 ; f = 0 ; for ( int i = 0 ; i <s2.length(); i++) { if (s2.charAt(i) >= 'A' && s2.charAt(i) <= 'Z' ) { if (f == 1 ) { f = 0 ; i--; cnt2++; ss2[cnt2] = "" ; continue ; } else f = 1 ; } ss2[cnt2] += "" + s2.charAt(i); } for ( int i = 1 ;i <= cnt1;i++) for ( int j = 1 ;j <= cnt2;j++) { if (ss1[i].equals(ss2[j])) { dp[i][j] = dp[i- 1 ][j- 1 ] + 1 ; } else { dp[i][j] = Math.max(dp[i- 1 ][j], dp[i][j- 1 ]); } } System.out.println(dp[cnt1][cnt2]); } } Copy code

Question H: Gallery

Problem Description


Xiaolan organized a painting exhibition and displayed his own works on the left and right sides of a gallery. In order to make the exhibition more interesting, Xiaolan did not display her works equidistantly, but displayed them in a more artistic way. L works are displayed on the left of the gallery, R works are displayed on the right of the gallery, the works on the left are u1, u2, , uL in order from the starting point of the gallery, and the works on the right are v1, v2 from the starting point of the gallery in order , ,VR. Every week, Xiaolan organizes each of his works. The time for organizing a work is fixed, but with heavy tools. The distance from one work to another is the length of the straight line. Xiaolan starts from the very center of the starting point of the gallery (the midpoint on the left and right sides), arranges each painting, and finally reaches the very center of the end of the gallery. The width of the gallery is known to be w. What is the minimum distance Xiaolan walks with tools?

Input format


The first line of input contains four integers L, R, d, w, indicating the number of works on the left and right of the gallery, as well as the length and width of the gallery. The second line contains L positive integers u 1, u 2, , u L, indicating the position of the works on the left side of the gallery. The third line contains R positive integers v 1, v 2, , v R, indicating the position of the work on the right side of the gallery.

Output format


Output a real number, rounded to the nearest two decimal places, which means that the distance that Xiaolan walks with the tool is the least.

Sample input


3 3 10 2
1 3 8
2 4 6

Sample output


14.71

Sample description


Xiaolan starts from the starting point, first reaches the first work on the left (walking distance 2), then reaches the second work on the left (walking distance 2), then reaches the first work on the right (walking distance 5), and then reaches the right The second and third works (walking distance 2 and 2), then the third work on the left (walking distance 2 2), and finally the end of the gallery (walking distance 5). The total distance is 2 + 2 + 5 + 2 + 2 + 2 2 + 5 14.71.

Evaluation use case scale and conventions


For 40% of the evaluation cases, 1 L, R 10, 1 d 100, 1 w 100.
For 70% of the evaluation cases, 1 L, R 100, 1 d 1000, 1 w 1000.
For all evaluation cases, 1 L, R 500, 1 d 100000, 1 w 100000, 0 u 1 <u 2 < <u L d, 0 v 1 <v 2 < <V R d.

Ideas


The analysis shows that it is a dense graph, and the final must be the minimum spanning tree. Create a graph according to the intent of the question. Create a graph with the starting point and end point and another drawing, convert the distance from the starting point into coordinates, and use the prime algorithm to find the minimum spanning tree.
import java.io.*; import java.util.*; //Two packages, io and util, are needed in the custom Read class. The asterisk * (wildcard) means all classes in the package import java.math.* ; //Biglongeger with large numbers import java.util.Comparator; import java.util.PriorityQueue; import java.util.Queue; import java.util.Scanner; import java.util.StringTokenizer; public class Main { static double a[] = new double [ 100005 ]; static int MAX = 1005 ; //Maximum number of nodes static long GIGANTIC = 0x3f3f3f3f ; //Defined as infinity static double [][] graph = new double [MAX][ MAX]; static double [] lowCost = new double [MAX]; //the lowest cost to reach node j static long [] previousNode = new long [MAX]; //the previous node of node j static long [] D = new long [MAX]; //the last node of node j static double minCost = 0 ; //minimum cost static long n; //number of nodes static int middleNode; //middle node static double sum = 0 ; //Record the total weight of the minimum spanning tree static int L, R, d, w; static class PrimMST { /** * Prim algorithm, returns the total weight of the minimum spanning tree. * * @param graph * @param n * @return sum */ public double prim ( double [][] graph, long n) { //Adjacency matrix, weighted (directly adjacent) assignment. Without weight (not directly adjacent), assign infinity for ( int i = 0 ; i <= n; i++) { for ( int j = 0 ; j <= n; j++) { if (graph[i] [j] == 0 ) { graph[i][j] = GIGANTIC; } } } //The default starting point for all points is A for ( int i = 1 ; i <= n; i++) { lowCost[i] = graph[ 0 ][i]; previousNode[i] = 0 ; } previousNode[ 0 ] = -1 ; //Perform n-1 loop operations for ( long i = 1 ; i <= n; i++) { minCost = GIGANTIC; middleNode = 0 ; //Find the smallest lowCost for ( int j = 1 ; j <= n; j++) { if (lowCost[j] != 0 && lowCost[j] <minCost) { minCost = lowCost[j]; middleNode = j; } } //Convert to English character output in ASCII code sum += minCost; //lowCost[middleNode] = 0; previousNode[middleNode] = 0; indicates that middleNode is selected into the minimum spanning tree lowCost[middleNode] = 0 ; previousNode[middleNode] = 0 ; //middleNode joins the minimum spanning tree, updates lowCost and previousNode for ( int j = 1 ; j <= n; j++) { if (graph[middleNode][j] <lowCost[j]) { lowCost[j] = graph[middleNode][j]; previousNode[j] = middleNode; } } } return sum; } } static double doEdge ( long y1, long y2, long i1, long i2) { double x1 = 0 ; double x2 = 0 ; if (i1 == 0 )x1 = w/ 2.0 ; if (i1> L) x1 = w; if (i2> L) x2 = w; return Math.sqrt( 1.0 * (x1-x2) * (x1-x2) + 1.0 * (y1-y2) * (y1-y2)); } public static void main (String[] args) { Scanner cin = new Scanner(System.in); L = cin.nextInt(); R = cin.nextInt(); d = cin.nextInt(); w = cin.nextInt(); for ( int i = 1 ; i <= L + R; i++) { D[i] = cin.nextLong(); } for ( int i = 1 ; i <= L + R; i++) { double e = doEdge( 0 , D[i], 0 , i); graph[ 0 ][i] = e; graph[i][ 0 ] = e; } for ( int i = 1 ; i <= L + R; i++) { for ( int j = i + 1 ; j <= L + R; j++) { double e = doEdge(D[i], D[j] , i, j); graph[i][j] = e; graph[j][i] = e; } } for ( int i = 1 ; i <= L + R; i++) { //end point double e = doEdge(d, D[i], 0 , i); graph[L + R + 1 ][i] = e; graph[i][L + R + 1 ] = e; } PrimMST primMST = new PrimMST(); double mstCost = primMST.prim(graph, L + R + 1 ); System.out.printf( "%.2f" ,mstCost); } } Copy code