2018年 第09届 蓝桥杯 Java B组 决赛真题详解及小结
- 藍(lán)橋杯 Java B組 省賽決賽 真題詳解及小結(jié)匯總【2013年(第4屆)~2020年(第11屆)】
- 第11屆 藍(lán)橋杯-第1、2次模擬(軟件類)真題-(2020年3月、4月)-官方講解視頻
- 說明：大部分題解思路及程序代碼 源自?藍(lán)橋杯 官網(wǎng)視頻(Java B組歷年真題解析)?——?鄭未老師。
目? ?錄
一、三角形面積——答案：8.795
解法一：手工計(jì)算（大矩形-三角形）
解法二：海倫公式
二、最大乘積——答案：839542176
解法一
解法二
三、全排列——答案：for (int j = cur + 1; j <= i; j++) data[j-1] = data[j];
四、整理玩具
五、版本分支
六、防御力
小結(jié)
一、三角形面積——答案：8.795
標(biāo)題：三角形面積
已知三角形三個頂點(diǎn)在直角坐標(biāo)系下的坐標(biāo)分別為：
(2.3, 2.5)
(6.4, 3.1)
(5.1, 7.2)
求該三角形的面積。
注意，要提交的是一個小數(shù)形式表示的浮點(diǎn)數(shù)。
要求精確到小數(shù)后3位，如不足3位，需要補(bǔ)零。
解法一：手工計(jì)算（大矩形-三角形）
原文鏈接
???
解法二：海倫公式
原文鏈接——wyk
package national_09_2018;public class A01_三角形面積 {public static void main(String[] args) {double s1 = 4.7 * 2.8 / 2;double s2 = 1.3 * 4.1 / 2;double s3 = 4.1 * 0.6 / 2;double ss = 4.1 * 4.7;System.out.println(String.format("%.3f", s1));System.out.println(String.format("%.3f", s2));System.out.println(String.format("%.3f", s3));System.out.println(String.format("%.3f", ss));System.out.println(String.format("%.3f", ss - s1 - s2 - s3));System.out.println("---");double a = Math.sqrt((6.4 - 2.3) * (6.4 - 2.3) + (3.1 - 2.5) * (3.1 - 2.5)); // ac邊double b = Math.sqrt((6.4 - 5.1) * (6.4 - 5.1) + (3.1 - 7.2) * (3.1 - 7.2)); // bc邊double c = Math.sqrt((5.1 - 2.3) * (5.1 - 2.3) + (7.2 - 2.5) * (7.2 - 2.5)); // ab邊double p = (a + b + c) / 2;System.out.println(String.format("%.3f", a));System.out.println(String.format("%.3f", b));System.out.println(String.format("%.3f", c));System.out.println(String.format("%.3f", p));System.out.println(String.format("%.3f", Math.sqrt(p * (p - a) * (p - b) * (p - c))));}}二、最大乘積——答案：839542176
標(biāo)題：最大乘積
把 1~9 這9個數(shù)字分成兩組，中間插入乘號，
有的時候，它們的乘積也只包含1~9這9個數(shù)字，而且每個數(shù)字只出現(xiàn)1次。
比如：
984672 * 351 = 345619872
98751 * 3462 = 341875962
9 * 87146325 = 784316925
...
符合這種規(guī)律的算式還有很多，請你計(jì)算在所有這些算式中，乘積最大是多少？
注意，需要提交的是一個整數(shù)，表示那個最大的積，不要填寫任何多余的內(nèi)容。
（只提交乘積，不要提交整個算式）
解法一
前期乘積肯定有很多不符合條件的，這些信息不應(yīng)該return掉，應(yīng)該繼續(xù)循環(huán)下一次。
check()函數(shù)：將數(shù)組按位進(jìn)行分割。?
解法二
原文鏈接——wyk
【解析】：全排列出九個數(shù)字的所有排列順序，
對每一種排列進(jìn)行枚舉，分割成兩部分，
對兩部分的乘積取結(jié)果，
檢查乘積結(jié)果是否符合條件，
如果符合條件，即更新全局變量ans。
三、全排列——答案：for (int j = cur + 1; j <= i; j++) data[j-1] = data[j];
標(biāo)題：全排列
對于某個串，比如：“1234”，求它的所有全排列。
并且要求這些全排列一定要按照字母的升序排列。
對于“1234”，應(yīng)該輸出(一共4!=24行)：
1234
1243
1324
1342
1423
1432
2134
2143
2314
2341
2413
2431
3124
3142
3214
3241
3412
3421
4123
4132
4213
4231
4312
4321
下面是實(shí)現(xiàn)程序，請仔細(xì)分析程序邏輯，并填寫劃線部分缺少的代碼。
// 輪換前k個，再遞歸處理
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");
?? ?}
}
請注意：只需要填寫劃線部分缺少的內(nèi)容，不要抄寫已有的代碼或符號。
原文鏈接——wyk
【答案】：for (int j = cur + 1; j <= i; j++) data[j-1] = data[j];
【解析】：觀察題目發(fā)現(xiàn)是個全排列問題，填空部分是全排列的回溯部分，只需要根據(jù)函數(shù)體內(nèi)上半部分交換的原則重新進(jìn)行回溯回去即可。
package national_09_2018;import java.util.*;public class C03_全排列 {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 + 1; j <= i; j++)data[j-1] = data[j]; // _______________________________________;data[i] = tmp;}}static void permu(String x) {permu(x.toCharArray(), 0);}public static void main(String[] args) {permu("1234");}}四、整理玩具
標(biāo)題：整理玩具
小明有一套玩具，一共包含NxM個部件。這些部件擺放在一個包含NxM個小格子的玩具盒中，每個小格子中恰好擺放一個部件。 ?
每一個部件上標(biāo)記有一個0~9的整數(shù)，有可能有多個部件標(biāo)記相同的整數(shù)。 ?
小明對玩具的擺放有特殊的要求：標(biāo)記相同整數(shù)的部件必須擺在一起，組成一個矩形形狀。
如以下擺放是滿足要求的：
00022
00033
44444 ?
12244
12244
12233
01234
56789
以下擺放不滿足要求：
11122
11122
33311
111111
122221
122221
111111
11122
11113
33333
給出一種擺放方式，請你判斷是否符合小明的要求。
輸入
----
輸入包含多組數(shù)據(jù)。 ?
第一行包含一個整數(shù)T，代表數(shù)據(jù)組數(shù)。 (1 <= T <= 10)?
以下包含T組數(shù)據(jù)。 ?
每組數(shù)據(jù)第一行包含兩個整數(shù)N和M。 ?(1 <= N, M <= 10) ?
以下包含N行M列的矩陣，代表擺放方式。 ?
輸出
---
對于每組數(shù)據(jù)，輸出YES或者NO代表是否符合小明的要求。 ?
【樣例輸入】
3 ?
3 5 ?
00022
00033
44444 ?
3 5 ?
11122
11122
33311
2 5 ?
01234
56789
【樣例輸出】
YES
NO
YES
資源約定：
峰值內(nèi)存消耗（含虛擬機(jī)） < 256M
CPU消耗 ?< 1000ms
請嚴(yán)格按要求輸出，不要畫蛇添足地打印類似：“請您輸入...” 的多余內(nèi)容。
所有代碼放在同一個源文件中，調(diào)試通過后，拷貝提交該源碼。
不要使用package語句。不要使用jdk1.7及以上版本的特性。
主類的名字必須是：Main，否則按無效代碼處理。
原文鏈接——wyk
【解析】：由題目可以確定數(shù)字相同的玩具放在了一起，
所以我們可以定義一個數(shù)組用來存放當(dāng)前數(shù)據(jù)的信息，
我們采用二維數(shù)組，
每一行代表當(dāng)前編號玩具的信息
第一列表示當(dāng)前編號玩具的占地面積
第二列表示當(dāng)前編號玩具的占地右下角的橫坐標(biāo)
第三列表示當(dāng)前編號玩具的占地右下角的縱坐標(biāo)
第四列表示當(dāng)前編號玩具的占地左上角的橫坐標(biāo)
第五列表示當(dāng)前編號玩具的占地左上角的縱坐標(biāo)
所以應(yīng)該有
->?buf[i][0] != 0 && buf[i][0] != (buf[i][1] - buf[i][3] + 1) * (buf[i][2] - buf[i][4] + 1)
恒成立。
package national_09_2018;import java.util.Scanner;public class D04_整理玩具 {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int t = scanner.nextInt();while (t-- > 0) {int n = scanner.nextInt(), m = scanner.nextInt();char c[][] = new char[n][m];int buf[][] = new int[10][5];for (int i = 0; i < 10; i++) {buf[i][0] = 0;buf[i][1] = -1;buf[i][2] = -1;buf[i][3] = 999;buf[i][4] = 999;}for (int i = 0; i < n; i++) {c[i] = scanner.next().toCharArray();}for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {buf[c[i][j] - '0'][0]++;buf[c[i][j] - '0'][1] = Math.max(buf[c[i][j] - '0'][1], i);buf[c[i][j] - '0'][2] = Math.max(buf[c[i][j] - '0'][2], j);buf[c[i][j] - '0'][3] = Math.min(buf[c[i][j] - '0'][3], i);buf[c[i][j] - '0'][4] = Math.min(buf[c[i][j] - '0'][4], j);}}boolean ok = true;for (int i = 0; i < 10; i++) {if (buf[i][0] != 0 && buf[i][0] != (buf[i][1] - buf[i][3] + 1) * (buf[i][2] - buf[i][4] + 1)) {ok = false;}}System.out.println(ok ? "YES" : "NO");}}}五、版本分支
標(biāo)題：版本分支
小明負(fù)責(zé)維護(hù)公司一個奇怪的項(xiàng)目。這個項(xiàng)目的代碼一直在不斷分支(branch)但是從未發(fā)生過合并(merge)。
現(xiàn)在這個項(xiàng)目的代碼一共有N個版本，編號1~N，其中1號版本是最初的版本。
除了1號版本之外，其他版本的代碼都恰好有一個直接的父版本；即這N個版本形成了一棵以1為根的樹形結(jié)構(gòu)。 ?
如下圖就是一個可能的版本樹：
? ? 1
? ?/ \
? 2 ? 3
? | ?/ \
? 5 4 ? 6
現(xiàn)在小明需要經(jīng)常檢查版本x是不是版本y的祖先版本。你能幫助小明嗎？
輸入
----
第一行包含兩個整數(shù)N和Q，代表版本總數(shù)和查詢總數(shù)。 ?
以下N-1行，每行包含2個整數(shù)u和v，代表版本u是版本v的直接父版本。 ?
再之后Q行，每行包含2個整數(shù)x和y，代表詢問版本x是不是版本y的祖先版本。 ?
對于30%的數(shù)據(jù)，1 <= N <= 1000 ?1 <= Q <= 1000 ?
對于100%的數(shù)據(jù)，1 <= N <= 100000 ?1 <= Q <= 100000 ?
輸出
----
對于每個詢問，輸出YES或NO代表x是否是y的祖先。 ?
【樣例輸入】
6 5
1 2
1 3
2 5
3 6
3 4
1 1
1 4
2 6
5 2
6 4
【樣例輸出】
YES
YES
NO
NO
NO
資源約定：
峰值內(nèi)存消耗（含虛擬機(jī)） < 256M
CPU消耗 ?< 1000ms
請嚴(yán)格按要求輸出，不要畫蛇添足地打印類似：“請您輸入...” 的多余內(nèi)容。
所有代碼放在同一個源文件中，調(diào)試通過后，拷貝提交該源碼。
不要使用package語句。不要使用jdk1.7及以上版本的特性。
主類的名字必須是：Main，否則按無效代碼處理。
原文鏈接——wyk
【解析】：wyk大佬用并查集的思路，用一個數(shù)組儲存該節(jié)點(diǎn)的父節(jié)點(diǎn)，當(dāng)詢問祖先關(guān)系是，向上查找父節(jié)點(diǎn)，時間復(fù)雜度較高，通過數(shù)據(jù)50%。
package national_09_2018;import java.util.*;public class E05_版本分支 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt(), q = sc.nextInt(), u, v;int pa[] = new int[n + 1];for (int i = 1; i < n; i++) {u = sc.nextInt();v = sc.nextInt();pa[v] = u;}for (int i = 0; i < q; i++) {u = sc.nextInt();v = sc.nextInt();boolean is = false;while (v != 0) {if (v == u) {is = true;break;}v = pa[v];}System.out.println(is ? "YES" : "NO");}}}六、防御力
標(biāo)題：防御力
小明最近在玩一款游戲。對游戲中的防御力很感興趣。
我們認(rèn)為直接影響防御的參數(shù)為“防御性能”，記作d，而面板上有兩個防御值A(chǔ)和B，與d成對數(shù)關(guān)系，A=2^d，B=3^d（注意任何時候上式都成立）。
在游戲過程中，可能有一些道具把防御值A(chǔ)增加一個值，有另一些道具把防御值B增加一個值。
現(xiàn)在小明身上有n1個道具增加A的值和n2個道具增加B的值，增加量已知。
現(xiàn)在已知第i次使用的道具是增加A還是增加B的值，但具體使用那個道具是不確定的，請找到一個字典序最小的使用道具的方式，使得最終的防御性能最大。
初始時防御性能為0，即d=0，所以A=B=1。
【輸入格式】
輸入的第一行包含兩個數(shù)n1,n2，空格分隔。
第二行n1個數(shù)，表示增加A值的那些道具的增加量。
第三行n2個數(shù)，表示增加B值的那些道具的增加量。
第四行一個長度為n1+n2的字符串，由0和1組成，表示道具的使用順序。0表示使用增加A值的道具，1表示使用增加B值的道具。輸入數(shù)據(jù)保證恰好有n1個0，n2個1。
【輸出格式】
對于每組數(shù)據(jù)，輸出n1+n2+1行，前n1+n2行按順序輸出道具的使用情況，若使用增加A值的道具，輸出Ax，x為道具在該類道具中的編號（從1開始）。若使用增加B值的道具則輸出Bx。最后一行輸出一個大寫字母E。
【樣例輸入1】
1 2
4
2 8
101
【樣例輸出1】
B2
A1
B1
E
【樣例輸入2】
3 0
7 11 13
000
【樣例輸出2】
A1
A2
A3
E
【樣例說明】
對于第一組測試數(shù)據(jù)，操作過程如下：
操作 ?d ? ? ? ? A ? ? ? ? ? ? ?B
初始 ?0?? ? ? ? ? ?1 ? ? ? ? ? ? ?1
B2 ? ?2 ? ? ? ? 4 ? ? ? ? ? ? ?9
A1 ? ?3?? ? ? ? ? ?8 ? ? ? ? ? ? ?27
B1 ? log3(29) ? 2^(log3(29)) ? 29
可以證明，這個值是最大的。
對于第二組測試數(shù)據(jù)，可見無論用什么順序，A最后總為32，即d總為5，B總為243。?
【數(shù)據(jù)規(guī)模】
對于20%的數(shù)據(jù)，字符串長度<=10000；
對于70%的數(shù)據(jù)，字符串長度<=200000；
對于100%的數(shù)據(jù)，字符串長度<=2000000，輸入的每個增加值不超過2^30。
資源約定：
峰值內(nèi)存消耗（含虛擬機(jī)） < 256M
CPU消耗 ?< 1000ms
請嚴(yán)格按要求輸出，不要畫蛇添足地打印類似：“請您輸入...” 的多余內(nèi)容。
所有代碼放在同一個源文件中，調(diào)試通過后，拷貝提交該源碼。
不要使用package語句。不要使用jdk1.7及以上版本的特性。
主類的名字必須是：Main，否則按無效代碼處理。
【解析】：題目要求防御性能最好，
而且AB的先后順序已經(jīng)固定，
我們只需要排好A和B兩序列內(nèi)部的排列順序即可，
對于A序列，對2取log，如果要使最終防御性能最好，
那么就要先使用增益效果最差的道具，把增益效果好的道具放到后邊以獲得最大漲幅，
對于B序列，對3取log，如果要使最終防御性能最好，
那么就要先使用增益效果最好的道具，以便在初期能獲得最大漲幅。
小結(jié)
wyk大佬實(shí)在太強(qiáng)喇呀！！！多謝carry！！！
總結(jié)
以上是生活随笔為你收集整理的2018年 第09届 蓝桥杯 Java B组 决赛真题详解及小结的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 2020全国大学生数学建模竞赛【论文格式
- 下一篇： 2017年 第08届 蓝桥杯 Java