# 2018 Blue Bridge Cup group B national competition

2013 Blue Bridge Cup group B national competition

2014 Blue Bridge Cup group B national competition

2015 Blue Bridge Cup group B national competition

2016 Blue Bridge Cup group B national competition

2017 Blue Bridge Cup group B national competition

## (1) Triangle area

It is known that the coordinates of the three vertices of the triangle in the rectangular coordinate system are:
(2.3, 2.5)
(6.4, 3.1)
(5.1, 7.2)

Find the area of the triangle.

Note that you are submitting a floating-point number in decimal form.
It is required to be accurate to 3 decimal places. If it is less than 3 decimal places, zero shall be added.

```public class Main {
public static void main(String[] args) {
double x1 = 2.3;
double y1 = 2.5;
double x2 = 6.4;
double y2 = 3.1;
double x3 = 5.1;
double y3 = 7.2;

double a = Math.sqrt(Math.pow(x2 - x1, 2) + Math.pow(y2 - y1, 2));
double b = Math.sqrt(Math.pow(x3 - x1, 2) + Math.pow(y3 - y1, 2));
double c = Math.sqrt(Math.pow(x3 - x2, 2) + Math.pow(y3 - y2, 2));

double p = (a + b + c) / 2;
double s = Math.sqrt(p * (p - a) * (p - b) * (p - c));
System.out.println(s);
}
}
```

## (2) Maximum product

Divide the 9 numbers from 1 to 9 into two groups, and insert the multiplication sign in the middle,
Sometimes, their product only contains 9 numbers from 1 to 9, and each number appears only once.

For example:
984672 * 351 = 345619872
98751 * 3462 = 341875962
9 * 87146325 = 784316925
...

There are many formulas that conform to this law. Please calculate the maximum product of all these formulas?

Note that what needs to be submitted is an integer indicating the maximum product. Do not fill in any redundant content.
(submit only the product, not the whole formula)

```public class _02 {
static char[] a = {'9', '8', '7', '6', '5', '4', '3', '2', '1', 'A'};
static long ans = 0;
public static void main(String[] args) {
f(0);
System.out.println(ans);
}

public static void f(int k) {

if (k == a.length) {
check();
return;
}

for (int i = k; i < a.length; i++) {
char temp = a[k];
a[k] = a[i];
a[i] = temp;

f(k + 1);

temp = a[k];
a[k] = a[i];
a[i] = temp;
}
}

public static void check() {
if (a[0] == 'A' || a[9] == 'A') return;

String s = new String(a);
String[] str = s.split("A");

long num1 = Long.parseLong(str[0]);
long num2 = Long.parseLong(str[1]);
long num = num1 * num2;

String numS = num + "";
boolean flag = false;
for (int i = 1; i <= 9; i++) {
if (numS.indexOf(i + "") == -1) flag = true;
}
if (!flag) ans = Math.max(ans, num);
}
}
```

## (3) Full arrangement

For a string, such as "1234", find all its permutations.
And these full permutations must be arranged in ascending alphabetical order.
For "1234", it should output (4! = 24 lines in total):
1234
1243
1324
1342
1423
1432
2134
2143
2314
2341
2413
2431
3124
3142
3214
3241
3412
3421
4123
4132
4213
4231
4312
4321

The following is the implementation program. Please carefully analyze the program logic and fill in the missing code in the underlined part.

//The first k of rotation are processed recursively

```import java.util.*;
public class A
{
static void permu(char[] data, int cur){
if(cur==data.length-1){
System.out.println(new String(data));
return;
}

for(int i=cur; i<data.length; i++){
char tmp = data[i];
for(int j=i-1; j>=cur; j--) data[j+1] = data[j];
data[cur] = tmp;

permu(data, cur+1);

tmp = data[cur];
__________________________________________ ;
data[i] = tmp;
}
}

static void permu(String x){
permu(x.toCharArray(),0);
}

public static void main(String[] args){
permu("1234");
}

}
```

Please note: only fill in the missing contents in the underlined part, and do not copy the existing codes or symbols.

Answer: for (int j = cur; J < = I - 1; j + +) data [J] = data [J + 1]

```public class Main {
public static void main(String[] args){
permu("1234".toCharArray(), 0);
}

public static void permu(char[] data, int cur) {
if (cur == data.length - 1) {
System.out.println(new String(data));
return;
}

for (int i = cur; i < data.length; i++) {

char tmp = data[i];
for (int j = i - 1; j >= cur; j--) data[j + 1] = data[j];
data[cur] = tmp;

permu(data, cur + 1);

tmp = data[cur];
for (int j = cur; j <= i - 1; j++) data[j] = data[j + 1];
data[i] = tmp;
}
}
}
```

## (4) Tidy toys

Xiao Ming has a set of toys, including NxM parts in total. These parts are placed in a toy box containing NxM small squares, and exactly one part is placed in each small lattice.

Each part is marked with an integer from 0 to 9, and multiple parts may be marked with the same integer.

Xiao Ming has special requirements for the placement of toys: parts marked with the same integer must be placed together to form a rectangular shape.

If the following placement meets the requirements:

00022
00033
44444

12244
12244
12233

01234
56789

The following placement does not meet the requirements:

11122
11122
33311

111111
122221
122221
111111

11122
11113
33333

Please judge whether it meets Xiaoming's requirements.

input

The input contains multiple sets of data.
The first row contains an integer t representing the number of data groups. (1 <= T <= 10)
The following contains group T data.
The first row of each set of data contains two integers n and m. (1 <= N, M <= 10)
The following matrix contains N rows and M columns, representing the placement mode.

output

For each group of data, the output of YES or NO represents whether it meets Xiaoming's requirements.

[sample input]
3
3 5
00022
00033
44444
3 5
11122
11122
33311
2 5
01234
56789

[sample output]
YES
NO
YES

Resource agreement:
Peak memory consumption (including virtual machine) < 256M
CPU consumption < 1000ms

Please output in strict accordance with the requirements, and do not print superfluous contents like "please input...".

All codes are placed in the same source file. After debugging, copy and submit the source code.
Do not use package statements. Do not use jdk1 7 and above.
The name of the Main class must be: Main, otherwise it will be treated as an invalid code.

So we have to change the way. In fact, when counting connected blocks, we can calculate the area of each connected block. Finally, the sum is equal to n * m, which indicates that it meets the meaning of the question. In the above example, it must be greater than n * M. So it doesn't accord with the meaning of the title.

That is, calculate the starting and final coordinates of each matrix, calculate the area of the current matrix through the two coordinates, and accumulate the area of all matrices

If the sum of the final areas is equal to n*m, it indicates that it is consistent with the meaning of the question, otherwise it is not

The second idea is

Find where i first and last appeared

Then go through all the numbers between the two coordinates

If there is a difference, return false directly and output it finally

```			char op = a[p[i].first.x][p[i].first.y];
for(int j = p[i].first.x; j <= p[i].second.x; j++){
for(int k = p[i].first.y; k <= p[i].second.y; k++){
if(a[j][k] != op) ans = false;
}
}
```
```public class Main {

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);

int t = sc.nextInt();
while(t-- > 0) {
int n, m;
n = sc.nextInt();
m = sc.nextInt();

// isFirst is used to determine whether i appears for the first time
int[] isFirst = new int[10];
int[][] a = new int[n][m];
Node[] p = new Node[10];
for (int i = 0; i < 10; i++) {
p[i] = new Node();
}

for (int i = 0; i < n; i++) {
String s = sc.next();
for (int j = 0; j < m; j++) {
a[i][j] = s.charAt(j) - '0';
int temp = a[i][j];
//System.out.println(temp);

if (isFirst[temp] == 0) {
p[temp].first_x = i;
p[temp].first_y = j;
p[temp].second_x = i;
p[temp].second_y = j;
isFirst[temp]++;
} else {
if (i > p[temp].second_x) p[temp].second_x = i;
if (j > p[temp].second_y) p[temp].second_y = j;
}
}
}

int sum = 0;
for (int i = 0; i <= 9; i++) {
// If i doesn't happen, skip this case
if (isFirst[i] == 0) continue;
int len = p[i].second_x + 1 - p[i].first_x;
int width = p[i].second_y + 1 - p[i].first_y;
sum += len * width;
}

if (sum == n * m) {
System.out.println("YES");
} else {
System.out.println("NO");
}
}
}
}

class Node {
int first_x;
int first_y;
int second_x;
int second_y;

Node() {
this.first_y = 0;
this.first_x = 0;
this.second_x = 0;
this.second_y = 0;
}
}
```

## (5) Version branch

Xiao Ming is responsible for maintaining a strange project of the company. The code of this project has been branching, but never merging.
At present, the code of this project has N versions, numbered 1~N, of which version 1 is the original version.
All versions except the direct version 1 have a parent version number; That is, these N versions form a tree structure with 1 as the root.

The following figure shows a possible version tree:

​ 1

/
2 3
| /
5 4 6

Now Xiao Ming needs to often check whether version x is the ancestor of version y. Can you help Xiao Ming?

## input

The first line contains two integers N and Q, representing the total number of versions and the total number of queries.
The following N-1 lines contain two integers u and V, representing version u and the direct parent version of version v.
Then line Q, each line containing two integers x and y, represents asking whether version x is the ancestor of version y.

For 30% of data, 1 < = n < = 1000 1 < = q < = 1000
For 100% data, 1 < = n < = 100000 1 < = q < = 100000

## output

For each query, the output YES or NO represents whether x is the ancestor of y.

[sample input]
6 5
1 2
1 3
2 5
3 6
3 4
1 1
1 4
2 6
5 2
6 4

[sample output]
YES
YES
NO
NO
NO

Resource agreement:
Peak memory consumption (including virtual machine) < 256M
CPU consumption < 1000ms

Please output in strict accordance with the requirements, and do not print superfluous contents like "please input...".

All codes are placed in the same source file. After debugging, copy and submit the source code.
Do not use package statements. Do not use jdk1 7 and above.
The name of the Main class must be: Main, otherwise it will be treated as an invalid code.

## (6) Defensive power

Xiao Ming is playing a game recently. Interested in defense in the game.
We believe that the parameter that directly affects the defense is "defense performance", which is recorded as d, and there are two defense values A and B on the panel, which are logarithmically related to d, A=2d and B=3d (note that the above formula is true at any time).
During the game, some props may increase defense value A by one value, while others increase defense value B by one value.
Now Xiao Ming has n1 props to increase the value of A and n2 props to increase the value of B. the increase is known.

It is now known whether the item used for the i time increases the value of A or B, but the specific use of the item is uncertain. Please find A way to use the item with the smallest dictionary order to maximize the final defense performance.

Initially, the defense performance is 0, that is, d=0, so A=B=1.

[input format]
The first line of input contains two numbers n1,n2, separated by spaces.
The number of n1 in the second line represents the increase of those props that increase the A value.
The number of n2 in the third line indicates the increase of those props that increase the B value.
The fourth line is A string with A length of n1+n2, which is composed of 0 and 1, indicating the use order of props. 0 means to use the item with increased A value, and 1 means to use the item with increased B value. The input data is guaranteed to have exactly n1 zeros and n2 ones.

[output format]
For each group of data, output line n1+n2+1, and the first line n1+n2 will output the use of props in order. If props with increased A value are used, output Ax, x is the number of props in such props (starting from 1). If A prop with increased B value is used, Bx will be output. The last line outputs A capital letter E.

[example input 1]
1 2
4
2 8
101

[sample output 1]
B2
A1
B1
E

Example [input 2]
3 0
7 11 13

000

[sample output 2]
A1
A2
A3
E

[example description]
For the first set of test data, the operation process is as follows:
Operation d A B
Initial 0 1
B2 2 4 9
A1 3 8 27
B1 log3(29) 2^(log3(29)) 29

It can be proved that this value is the largest.
For the second set of test data, it can be seen that no matter what order is used, A is always 32 at the end, that is, d is always 5 and B is always 243.

[data scale]
For 20% of data, string length < = 10000;
For 70% of data, string length < = 200000;
For 100% data, the string length is < = 2000000, and each added value entered shall not exceed 2 ^ 30.

Resource agreement:
Peak memory consumption (including virtual machine) < 256M
CPU consumption < 1000ms

Please output in strict accordance with the requirements, and do not print superfluous contents like "please input...".

All codes are placed in the same source file. After debugging, copy and submit the source code.
Do not use package statements. Do not use jdk1 7 and above.
The name of the Main class must be: Main, otherwise it will be treated as an invalid code.

Tags: Java Algorithm

Posted by jesse_james on Sun, 08 May 2022 04:38:20 +0300