# 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?

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```

# 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.

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```

# 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).

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```

# 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)

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  void  dfs ( int st, String cur)  {
if (s.contains(cur)) return ;

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```

# Question E: Toy Snake

Problem Description

Toy snake

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.

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)  {
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```