Want to make APP Same thing as WeChat , Can run small programs smoothly ？ | Experience will send you to Xinjiang 、 Huawei 、 Cherry keyboard ！>>>

Participated in this blue bridge Cup JAVA A Group , I'm lucky to be in the national competition , So I look back on the blank filling questions of the provincial contest , The big question will come back later , The following ideas are for reference only .

A House number making

【 problem 】 Xiaolan wants to make house numbers for the residents in a street . This street has 2020 Residents , House number from 1 To 2020 Number . Xiaolan's method of making house number is to make it first 0 To 9 These numeric characters , Finally, paste the characters on the doorplate as needed , For example, the house number 1017 You need to paste the characters in turn 1、0、1、7, That is to say 1 Characters 0,2 Characters 1,1 Characters 7. Please make all the 1 To 2020 House number , How many characters are needed in total 2？
【 Ideas 】 Traverse 1 To 2020, Count 2 That's good .

public static void main(String[] args) {

int ans=0;
for (int i = 1; i <= 2020; i++) {

char[] c=Integer.toString(i).toCharArray();
for (int j = 0; j < c.length; j++) {

if (c[j]=='2') {

ans++;
}
}
}
System.out.println(ans);
}

 Running results 
624

B reduced fraction

【 problem 】 If the greatest common divisor of the numerator and denominator of a fraction is 1, This fraction is called a reduced fraction . for example ,3/4 , 5/2 , 1/8 , 7/1 It's all contract scores . Excuse me, , How many committed scores are there , The numerator and denominator are 1 To 2020 Integer between （ Include 1 and 2020）？
【 Ideas 】 Violence enumeration , Every time we judge whether the numerator and denominator are coprime OK 了

public class Two {

// Find the greatest common divisor of two numbers 
static int gcd(int a,int b){

int t;
if(a<b){

t=a;
a=b;
b=t;
}
while(a%b!=0){

t=b;
b=a%b;
a=t;
}
return b;
}
public static void main(String[] args) {

int ans=0;
for (int i = 1; i <= 2020; i++) {

for (int j = 1; j <= 2020; j++) {

if (gcd(i, j)==1)ans++;
}
}
System.out.println(ans);
}
}

 Running results 
2481215

C Snake fill in

【 problem 】 As shown in the figure below , Xiao Ming uses from 1 A positive integer at the beginning “ Serpentine ” Fill an infinite matrix .

It is easy to see that the number in the second row and second column of the matrix is 5. Please calculate the number... In the matrix 20 Xing di 20 What's the number of columns ？
【 Ideas 】 One way of thinking is to walk obliquely according to the requirements , The following code provides this idea ; Another observation question is 20 That's ok 20 Column , In the middle of the diagonal , You can find , In the middle of the diagonal, no matter how it goes around , It's all the same , So you can output pyramids in sequence , Here's the picture ：

The first 20 That's ok 20 Column corresponding to the pyramid 39 The number in the middle of the line .

public class Three {

public static void main(String[] args) {

boolean flag = true;
for (int x = 1, y = 1, k = 1; ; k++) {

if (x == 20 && y == 20) {

System.out.println(k);
break;
}
if (flag){
// Slant down 
if (x - 1!=0){

x--;
y++;
}
else {
// When we get to the left border , Go straight down 
y++;
flag = false;
}
}
else {
// Go up slant 
if (y - 1!=0) {

x++;
y--;
}
else {

x++; // When we get to the upper boundary , Go straight across 
flag = true;
}
}
}
}
}

 Running results 
761

D Seven segment code

【 problem 】 Xiaolan wants to use a seven segment digital tube to represent a special text .
The figure above shows a picture of the digital tube with seven segments , There is a total of 7 A diode that can emit light , They are marked as a, b, c, d, e, f, g. Xiaolan wants to choose some diodes （ At least one ） Light to express characters . When designing the expression of characters , All LED's must be connected together .
for example ：b Luminescence , Other diodes that do not emit light can be used to express a character .
for example ：c Luminescence , Other diodes that do not emit light can be used to express a character . This scheme can be used to represent different characters as in the previous line , Although it looks similar .
for example ：a, b, c, d, e Luminescence ,f, g Non luminous can be used to express a character .
for example ：b, f Luminescence , Other diodes that do not emit light cannot be used to express a character , Because the LEDs are not connected together .
Excuse me, , How many different characters can Xiaolan express with a seven segment digital tube ？
【 Ideas 】 utilize dfs Choose the arrangement , Enumerate all the situations , Then use the adjacency table to determine whether each situation is connected into a piece , If yes, count it , As a result, all possible scenarios are output .

public class Four {

static String s="abcdefg";
static char[] c=s.toCharArray();
static int vis[]=new int[7];
static char[][]table={
// Create adjacency list 
{
'b','f'},{
'a','g','c'},{
'b','g','d'},
{
'c','e'},{
'f','g','d'},{
'a','g','e'},
{
'f','b','c','e'}
};
static int ans=0;
static boolean check(String s){
// Determine whether the selected diodes can be connected together 
char[] num=s.toCharArray();
for (int i = 0; i < num.length; i++) {

boolean flag0=false;
for (int j = 0; j < num.length; j++) {

boolean flag=false;
for (int k = 0; k < table[num[i]-'a'].length; k++) {

if (num[j]==table[num[i]-'a'][k]) {

flag=true;
break;
}
}
if (flag) {

flag0=true;
break;
}
}
if (flag0==false) {

return false;
}
}
return true;
}
static void dfs(int step,int pos,int n,int k,String s){

if (step==k) {

if (k==1) {

System.out.println(s);
ans++;
}
else {

if (check(s)) {

System.out.println(s);
ans++;
}
}
return;
}
if (pos==n) {

return;
}
if (vis[pos]==0) {

vis[pos]=1;
dfs(step+1, pos, n, k, s+c[pos]);
vis[pos]=0;
}
dfs(step, pos+1, n, k, s);
}
public static void main(String[] args) {

for (int i = 1; i <= 7; i++) {

dfs(0, 0, 7, i, "");
}
System.out.println(ans);
}
}

 Running results
a
b
c
d
e
f
g
ab
af
bc
bg
cd
cg
de
ef
eg
fg
abc
abf
abg
aef
afg
bcd
bcg
beg
bfg
cde
cdg
ceg
cfg
def
deg
efg
abcd
abcf
abcg
abde
abef
abeg
abfg
acdf
acfg
adef
aefg
bcde
bcdg
bcef
bceg
bcfg
bdeg
befg
cdef
cdeg
cdfg
cefg
defg
abcde
abcdf
abcdg
abcef
abceg
abcfg
abdef
abdeg
abefg
acdef
acdfg
acefg
adefg
bcdef
bcdeg
bcdfg
bcefg
bdefg
cdefg
abcdef
abcdeg
abcdfg
abcefg
abdefg
acdefg
bcdefg
abcdefg
83

E Plane segmentation

【 problem 】20 A circle and 20 How many parts of a plane can a straight line divide ？
【 Ideas 】 The following is the analysis of my own drawing to find the rules , It seems like this , Not sure the answer is right , If there is a problem , Welcome to correct .

1. First consider the case of only circles

• A circle can divide a plane into at most 2 Parts of ,
• 2 A circle can divide a plane into 4 Parts of ;
• 3 A circle can divide a plane into 8 Parts of ;
• Now join the 4 Circle , In order to make the most of the divided parts , The first 4 A circle must be in front of 3 Every circle has two intersections , So get 6 The point of intersection will be 4 The circumference of a circle is divided into 6 Arc , And each arc divides the original part in two , That is, a part of the plane is added , therefore 4 Circles divide the plane into at most 8+6=14 Parts of ,
• Empathy ,5 Circles divide the plane into at most 14+8=22 Parts of
• Finally, it can be inferred that n A circle divides a plane into at most 2+1x2+2x2+…+(n-1)x2 part
  
  

2. Consider introducing 1 In the case of a straight line

• Suppose there is only one circle , It divides the plane into 2 part
• Introduce a straight line , At most, a straight line and this circle have 2 A point of intersection , This line is divided into 3 paragraph , The middle paragraph divides the original part into 2, Divide the original part into 2, So the plane increases 1+1=2 part , have to 2+2=4
• If there are two circles , Two circles divide the plane into at most 4 part , So a line has at most two circles 4 A point of intersection , The line is divided into 5 There are three middle paragraphs that divide the original into two , Divide the original part into 2, So the plane increases 3+1=4
• If there are three circles , Three circles divide the plane into at most 8 part , So a line and at most three circles have 6 A point of intersection , The line is divided into 7 paragraph , middle 5 The paragraph divides the original part into two , Divide the original part into 2, So the plane increases 5+1=6
• It can be concluded that , Introduce a straight line , The original n A circle divides a line into at most 2n+1 paragraph , The plane increases 2n part
  
  

3. Finally, consider introducing m In the case of a straight line

First of all, each line will have at most the same as the original circle 2n A point of intersection , The plane increases 2n part . On this basis , Let's consider the intersection of lines , For the convenience of drawing and finding rules , set up n=1.

• introduce 1 A straight line , Its sum circle is the most 2 A point of intersection , This line is divided into 3 paragraph , The middle paragraph divides the original part into 2, The first and last parts of the area are divided into 2, So the plane increases 2x1=2 part
• Introduce the first 2 A straight line , The sum of the circle and the preceding line produces at most 2x1+1=3 A point of intersection , This line is divided into 2x1+2=4 paragraph , Each paragraph divides its area in two , So the plane increases 4 part
• Introduce the first 3 A straight line , The sum of the circle and the preceding line produces at most 2x1+2=4 A point of intersection , This line is divided into 2x1+3=5 paragraph , Each paragraph divides its area in two , So the plane increases 5 part ;
• Introduce the first 4 A straight line , The sum of the circle and the preceding line produces at most 2x1+3=5 A point of intersection , This line is divided into 2x1+4=6 paragraph , Each paragraph divides its area in two , So the plane increases 6 part ;

So we can sum up the general law , Introduce the first m A straight line , And n A circle and before m-1 Straight lines produce at most 2n+m-1 A point of intersection , This line is divided into 2n+m paragraph , Each paragraph divides its area in two , So the plane increases 2n+m part （m>=2, When m=1 when , increase 2n part ）;

public class Five {

public static void main(String[] args) {

int ans=2;// The first circle divides the plane into 2 part 
for (int i = 1; i <= 20; i++) {

ans+=(i-1)*2;// The first i The circles followed by the front (i-1) A circle produces (i-1)*2 A point of intersection , It's divided into (i-1)*2 paragraph , That is to say (i-1)*2 Parts of 
}
System.out.println(ans);
int n=20;
ans+=n*2;// The first line and 20 A circle intersects , The plane increases 2*n part 
for (int i = 2; i <=20 ; i++) {

ans+=(2*n+i);// The first i A straight line and the front 20 A circle and i-1 Lines produce at most 40+i-1 Focus , Is divided into 40+i paragraph , That is to say, increase 40+i Parts of 
}
System.out.println(ans);
}
}

 Running results 
1391