2020藍橋杯JAVA A組填空題

參加了本屆藍橋杯JAVA A組，有幸進入國賽，于是回顧下省賽的填空題，大題到時再回憶下，下面思路僅供參考，

A 門牌制作

【問題】小藍要為一條街的住戶制作門牌號，這條街一共有2020 位住戶，門牌號從1 到2020 編號，小藍制作門牌的方法是先制作0 到9 這幾個數字字符，最后根據需要將字符粘貼到門牌上，例如門牌1017 需要依次粘貼字符1、0、1、7，即需要1 個字符0，2 個字符1，1 個字符7，請問要制作所有的1 到2020 號門牌，總共需要多少個字符2？
【思路】遍歷1到2020，數2的個數就好，

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);
	}

運行結果
624

B 既約分數

【問題】如果一個分數的分子和分母的最大公約數是1，這個分數稱為既約分數，例如，3/4 , 5/2 , 1/8 , 7/1都是既約分數，請問，有多少個既約分數，分子和分母都是1 到2020 之間的整數（包括1和2020）？
【思路】暴力列舉，每次判斷分子和分母是否互質就OK了

public class Two {
	//求兩數的最大公約數
	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);
	}
}

運行結果
2481215

C 蛇形填數

【問題】如下圖所示，小明用從1 開始的正整數“蛇形”填充無限大的矩陣，

容易看出矩陣第二行第二列中的數是5，請你計算矩陣中第20 行第20 列的數是多少？
【思路】一個思路是可以老老實實按著要求斜著走，下面提供了這種思路代碼；另一種可以觀察題目問的是20行20列，即對角線中間位置，可以發現，對角線中間位置無論怎么繞，都是不變的，因此可以順序輸出金字塔形，如下圖：

第20行20列對應金字塔的39行中間的數，

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){//斜向下走
	            if (x - 1!=0){ 
	            	x--; 
	            	y++;
	            }
	            else {//到左邊界時，直接下走
	            	y++; 
	            	flag = false;
	            }
	        }
	        else {//斜向上走
	            if (y - 1!=0) {
	            	x++; 
	            	y--;
	            }
	            else {
	            	x++; //到上邊界時，直接橫走
	            	flag = true;
	            }
	        }  
	    }
	}
}

運行結果
761

D 七段碼

【問題】小藍要用七段碼數碼管來表示一種特殊的文字，
七段碼上圖給出了七段碼數碼管的一個圖示，數碼管中一共有7 段可以發光的二極管，分別標記為a, b, c, d, e, f, g，小藍要選擇一部分二極管（至少要有一個）發光來表達字符，在設計字符的表達時，要求所有發光的二極管是連成一片的，
例如：b 發光，其他二極管不發光可以用來表達一種字符，
例如：c 發光，其他二極管不發光可以用來表達一種字符，這種方案與上一行的方案可以用來表示不同的字符，盡管看上去比較相似，
例如：a, b, c, d, e 發光，f, g 不發光可以用來表達一種字符，
例如：b, f 發光，其他二極管不發光則不能用來表達一種字符，因為發光的二極管沒有連成一片，
請問，小藍可以用七段碼數碼管表達多少種不同的字符？
【思路】利用dfs選擇排列，列舉所有情況，再利用鄰接表判斷每種情況是否連成一片，是的話就計數，結果輸出了所有可行情況，

public class Four {
	static String s="abcdefg";
	static char[] c=s.toCharArray();
	static int vis[]=new int[7];
	static char[][]table={//建立鄰接表
		{'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){//判斷選擇的二極管能否連成一片
		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);
	}
}

運行結果
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 平面分割

【問題】20個圓和20 條直線最多能把平面分成多少個部分？
【思路】下面是我自己畫圖找規律的分析，似乎是這樣子，不確保答案對不對，如有問題，歡迎指正，

1.先考慮只有圓的情況

• 一個圓最多能把平面分成2個部分，
• 2個圓最多能把平面分成4個部分；
• 3個圓最多能把平面分成8個部分；
• 現在加入第4個圓，為了使分成的部分最多，第4個圓必須與前面3個圓都有兩個交點，因此得6個交點將第4個圓的圓周分成6段圓弧，而每一段圓弧將原來的部分一分為二，即平面增加了一個部分，于是4個圓最多將平面分成8+6=14個部分，
• 同理，5個圓最多將平面分成14+8=22個部分
• 最終可推算出n個圓最多把平面分成2+1x2+2x2+…+(n-1)x2部分
  

2.再考慮引入1條直線的情況

• 假設只有一個圓，其把平面分成2部分
• 引入一條直線，一條直線最多和此圓有2個交點，此直線被分成3段，中間一段把原來部分一分為2，首尾共同把原來部分一分為2，因此平面增加1+1=2部分，得2+2=4
• 如果有兩個圓，兩個圓最多把平面分成4部分，那么一條直線最多和兩個圓有4個交點，直線被分成5段有中間三段把原來部分一分為二，首尾共同把原來部分一分為2，因此平面增加3+1=4
• 如果有三個圓，三個圓最多把平面分成8部分，那么一條直線最多和三個圓有6個交點，直線被分成7段，中間5段段把原來部分一分為二，首尾共同把原來部分一分為2，因此平面增加5+1=6
• 可總結出，引入一條直線，原來的n個圓會把直線最多分成2n+1段，平面增加2n部分
  

3.最后考慮引入m條直線的情況

首先每條直線都會最多與原來的圓有2n個交點，平面增加2n部分，再此基礎上，我們再考慮直線與直線相交的情況，為方便畫圖找規律，設n=1，

• 引入1條直線，其和圓最多2個交點，此直線被分成3段，中間一段把原來部分一分為2，首尾共同把所在區域一分為2，因此平面增加2x1=2部分
• 引入第2條直線，其和圓與之前直線最多產生2x1+1=3個交點，此直線被分成2x1+2=4段，每段把其所在區域一分為二，因此平面增加4部分
• 引入第3條直線，其和圓與之前直線最多產生2x1+2=4個交點，此直線被分成2x1+3=5段，每段把其所在區域一分為二，因此平面增加5部分；
• 引入第4條直線，其和圓與之前直線最多產生2x1+3=5個交點，此直線被分成2x1+4=6段，每段把其所在區域一分為二，因此平面增加6部分；

由此總結一般規律，引入第m條直線，其和n個圓與之前m-1直線最多產生2n+m-1個交點，此直線被分成2n+m段，每段把其所在區域一分為二，因此平面增加2n+m部分（m>=2，當m=1時，增加2n部分）；

public class Five {
	public static void main(String[] args) {
		int ans=2;//第一個圓把平面分成2部分
		for (int i = 1; i <= 20; i++) {
			ans+=(i-1)*2;//第i個圓依次和前面(i-1)個圓產生(i-1)*2個交點，即被分成(i-1)*2段，亦即產生(i-1)*2個部分
		}
		System.out.println(ans);
		int n=20;
		ans+=n*2;//第一條直線和20個圓相交，平面增加2*n部分
		for (int i = 2; i <=20 ; i++) {
			ans+=(2*n+i);//第i條直線和前面20個圓和i-1條線最多產生40+i-1個焦點，被分成40+i段，亦即增加40+i個部分
		}
		System.out.println(ans);
	}
}

運行結果
1391