2020 Blue Bridge Cup Java group A

osc_l8yszczz 2020-11-08 09:40:06
blue bridge cup java group


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 .

1 2 6 7 15
3 5 8 14
4 9 13
10 12
11

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 :

1
2 3
4 5 6
7 8 9 10

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
     Insert picture description here

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
     Insert picture description here

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 ;

 Insert picture description here

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
版权声明
本文为[osc_l8yszczz]所创,转载请带上原文链接,感谢

  1. 【计算机网络 12(1),尚学堂马士兵Java视频教程
  2. 【程序猿历程,史上最全的Java面试题集锦在这里
  3. 【程序猿历程(1),Javaweb视频教程百度云
  4. Notes on MySQL 45 lectures (1-7)
  5. [computer network 12 (1), Shang Xuetang Ma soldier java video tutorial
  6. The most complete collection of Java interview questions in history is here
  7. [process of program ape (1), JavaWeb video tutorial, baidu cloud
  8. Notes on MySQL 45 lectures (1-7)
  9. 精进 Spring Boot 03:Spring Boot 的配置文件和配置管理,以及用三种方式读取配置文件
  10. Refined spring boot 03: spring boot configuration files and configuration management, and reading configuration files in three ways
  11. 精进 Spring Boot 03:Spring Boot 的配置文件和配置管理,以及用三种方式读取配置文件
  12. Refined spring boot 03: spring boot configuration files and configuration management, and reading configuration files in three ways
  13. 【递归,Java传智播客笔记
  14. [recursion, Java intelligence podcast notes
  15. [adhere to painting for 386 days] the beginning of spring of 24 solar terms
  16. K8S系列第八篇(Service、EndPoints以及高可用kubeadm部署)
  17. K8s Series Part 8 (service, endpoints and high availability kubeadm deployment)
  18. 【重识 HTML (3),350道Java面试真题分享
  19. 【重识 HTML (2),Java并发编程必会的多线程你竟然还不会
  20. 【重识 HTML (1),二本Java小菜鸟4面字节跳动被秒成渣渣
  21. [re recognize HTML (3) and share 350 real Java interview questions
  22. [re recognize HTML (2). Multithreading is a must for Java Concurrent Programming. How dare you not
  23. [re recognize HTML (1), two Java rookies' 4-sided bytes beat and become slag in seconds
  24. 造轮子系列之RPC 1:如何从零开始开发RPC框架
  25. RPC 1: how to develop RPC framework from scratch
  26. 造轮子系列之RPC 1:如何从零开始开发RPC框架
  27. RPC 1: how to develop RPC framework from scratch
  28. 一次性捋清楚吧,对乱糟糟的,Spring事务扩展机制
  29. 一文彻底弄懂如何选择抽象类还是接口,连续四年百度Java岗必问面试题
  30. Redis常用命令
  31. 一双拖鞋引发的血案,狂神说Java系列笔记
  32. 一、mysql基础安装
  33. 一位程序员的独白:尽管我一生坎坷,Java框架面试基础
  34. Clear it all at once. For the messy, spring transaction extension mechanism
  35. A thorough understanding of how to choose abstract classes or interfaces, baidu Java post must ask interview questions for four consecutive years
  36. Redis common commands
  37. A pair of slippers triggered the murder, crazy God said java series notes
  38. 1、 MySQL basic installation
  39. Monologue of a programmer: despite my ups and downs in my life, Java framework is the foundation of interview
  40. 【大厂面试】三面三问Spring循环依赖,请一定要把这篇看完(建议收藏)
  41. 一线互联网企业中,springboot入门项目
  42. 一篇文带你入门SSM框架Spring开发,帮你快速拿Offer
  43. 【面试资料】Java全集、微服务、大数据、数据结构与算法、机器学习知识最全总结,283页pdf
  44. 【leetcode刷题】24.数组中重复的数字——Java版
  45. 【leetcode刷题】23.对称二叉树——Java版
  46. 【leetcode刷题】22.二叉树的中序遍历——Java版
  47. 【leetcode刷题】21.三数之和——Java版
  48. 【leetcode刷题】20.最长回文子串——Java版
  49. 【leetcode刷题】19.回文链表——Java版
  50. 【leetcode刷题】18.反转链表——Java版
  51. 【leetcode刷题】17.相交链表——Java&python版
  52. 【leetcode刷题】16.环形链表——Java版
  53. 【leetcode刷题】15.汉明距离——Java版
  54. 【leetcode刷题】14.找到所有数组中消失的数字——Java版
  55. 【leetcode刷题】13.比特位计数——Java版
  56. oracle控制用户权限命令
  57. 三年Java开发,继阿里,鲁班二期Java架构师
  58. Oracle必须要启动的服务
  59. 万字长文!深入剖析HashMap,Java基础笔试题大全带答案
  60. 一问Kafka就心慌?我却凭着这份,图灵学院vip课程百度云