2019第十屆藍橋杯國賽JAVA B組真題決議（帶原始碼及決議）

藍橋杯歷年真題及決議.

A：遞增序列（難度：★★）.

對于一個字母矩陣，我們稱矩陣中的一個遞增序列是指在矩陣中找到兩個字母，它們在同一行，同一列，或者在同一 45 度的斜線上，這兩個字母從左向右看、或者從上向下看是遞增的，

例如，如下矩陣中
LANN
QIAO
有LN、LN、AN、AN、IO、AO、LQ、AI、NO、NO、AQ、IN、AN 等 13 個
遞增序列，注意當兩個字母是從左下到右上排列時，從左向右看和從上向下看
是不同的順序，

對于下面的 30 行 50 列的矩陣，請問總共有多少個遞增序列？（如果你把
以下文字復制到文本檔案中，請務必檢查復制的內容是否與檔案中的一致，在
試題目錄下有一個檔案 inc.txt，內容與下面的文本相同，

VLPWJVVNNZSWFGHSFRBCOIJTPYNEURPIGKQGPSXUGNELGRVZAG
SDLLOVGRTWEYZKKXNKIRWGZWXWRHKXFASATDWZAPZRNHTNNGQF
ZGUGXVQDQAEAHOQEADMWWXFBXECKAVIGPTKTTQFWSWPKRPSMGA
BDGMGYHAOPPRRHKYZCMFZEDELCALTBSWNTAODXYVHQNDASUFRL
YVYWQZUTEPFSFXLTZBMBQETXGXFUEBHGMJKBPNIHMYOELYZIKH
ZYZHSLTCGNANNXTUJGBYKUOJMGOGRDPKEUGVHNZJZHDUNRERBU
XFPTZKTPVQPJEMBHNTUBSMIYEGXNWQSBZMHMDRZZMJPZQTCWLR
ZNXOKBITTPSHEXWHZXFLWEMPZTBVNKNYSHCIQRIKQHFRAYWOPG
MHJKFYYBQSDPOVJICWWGGCOZSBGLSOXOFDAADZYEOBKDDTMQPA
VIDPIGELBYMEVQLASLQRUKMXSEWGHRSFVXOMHSJWWXHIBCGVIF
GWRFRFLHAMYWYZOIQODBIHHRIIMWJWJGYPFAHZZWJKRGOISUJC
EKQKKPNEYCBWOQHTYFHHQZRLFNDOVXTWASSQWXKBIVTKTUIASK
PEKNJFIVBKOZUEPPHIWLUBFUDWPIDRJKAZVJKPBRHCRMGNMFWW
CGZAXHXPDELTACGUWBXWNNZNDQYYCIQRJCULIEBQBLLMJEUSZP
RWHHQMBIJWTQPUFNAESPZHAQARNIDUCRYQAZMNVRVZUJOZUDGS
PFGAYBDEECHUXFUZIKAXYDFWJNSAOPJYWUIEJSCORRBVQHCHMR
JNVIPVEMQSHCCAXMWEFSYIGFPIXNIDXOTXTNBCHSHUZGKXFECL
YZBAIIOTWLREPZISBGJLQDALKZUKEQMKLDIPXJEPENEIPWFDLP
HBQKWJFLSEXVILKYPNSWUZLDCRTAYUUPEITQJEITZRQMMAQNLN
DQDJGOWMBFKAIGWEAJOISPFPLULIWVVALLIIHBGEZLGRHRCKGF
LXYPCVPNUKSWCCGXEYTEBAWRLWDWNHHNNNWQNIIBUCGUJYMRYW
CZDKISKUSBPFHVGSAVJBDMNPSDKFRXVVPLVAQUGVUJEXSZFGFQ
IYIJGISUANRAXTGQLAVFMQTICKQAHLEBGHAVOVVPEXIMLFWIYI
ZIIFSOPCMAWCBPKWZBUQPQLGSNIBFADUUJJHPAIUVVNWNWKDZB
HGTEEIISFGIUEUOWXVTPJDVACYQYFQUCXOXOSSMXLZDQESHXKP
FEBZHJAGIFGXSMRDKGONGELOALLSYDVILRWAPXXBPOOSWZNEAS
VJGMAOFLGYIFLJTEKDNIWHJAABCASFMAKIENSYIZZSLRSUIPCJ
BMQGMPDRCPGWKTPLOTAINXZAAJWCPUJHPOUYWNWHZAKCDMZDSR
RRARTVHZYYCEDXJQNQAINQVDJCZCZLCQWQQIKUYMYMOVMNCBVY
ABTCRRUXVGYLZILFLOFYVWFFBZNFWDZOADRDCLIRFKBFBHMAXX

【答案提交】
這是一道結果填空的題，你只需要算出結果后提交即可，本題的結果為一
個整數，在提交答案時只填寫這個整數，填寫多余的內容將無法得分，

分析：

列舉每一個坐標，對每個坐標列舉兩字母的距離，
另外，每兩個字母的方位只有四個情況：
情況一，兩個字母在同一行
在此種情況下，當右邊字母大于左邊字母即可計數+1
情況二：兩個字母在同一列
在此種情況下，當下邊字母大于上邊字母即可計數+1
情況三：一個字母在另一個字母的右下方
在此種情況下，從上向下看和從左向右看答案是相同的，當右下方字母大于左上方字母即可計數+1
情況四：一個字母在另一個字母的左上方
在此種情況下，從上向下看和從左向右看答案是相反的，所以我們只需要要求兩字母不同即可計數+1

AC代碼：

答案：52800

package JAVA2019;

public class A {
	public static int n=30,m=50;
	public static String s[]={
			"VLPWJVVNNZSWFGHSFRBCOIJTPYNEURPIGKQGPSXUGNELGRVZAG",
			"SDLLOVGRTWEYZKKXNKIRWGZWXWRHKXFASATDWZAPZRNHTNNGQF",
			"ZGUGXVQDQAEAHOQEADMWWXFBXECKAVIGPTKTTQFWSWPKRPSMGA",
			"BDGMGYHAOPPRRHKYZCMFZEDELCALTBSWNTAODXYVHQNDASUFRL",
			"YVYWQZUTEPFSFXLTZBMBQETXGXFUEBHGMJKBPNIHMYOELYZIKH",
			"ZYZHSLTCGNANNXTUJGBYKUOJMGOGRDPKEUGVHNZJZHDUNRERBU",
			"XFPTZKTPVQPJEMBHNTUBSMIYEGXNWQSBZMHMDRZZMJPZQTCWLR",
			"ZNXOKBITTPSHEXWHZXFLWEMPZTBVNKNYSHCIQRIKQHFRAYWOPG",
			"MHJKFYYBQSDPOVJICWWGGCOZSBGLSOXOFDAADZYEOBKDDTMQPA",
			"VIDPIGELBYMEVQLASLQRUKMXSEWGHRSFVXOMHSJWWXHIBCGVIF",
			"GWRFRFLHAMYWYZOIQODBIHHRIIMWJWJGYPFAHZZWJKRGOISUJC",
			"EKQKKPNEYCBWOQHTYFHHQZRLFNDOVXTWASSQWXKBIVTKTUIASK",
			"PEKNJFIVBKOZUEPPHIWLUBFUDWPIDRJKAZVJKPBRHCRMGNMFWW",
			"CGZAXHXPDELTACGUWBXWNNZNDQYYCIQRJCULIEBQBLLMJEUSZP",
			"RWHHQMBIJWTQPUFNAESPZHAQARNIDUCRYQAZMNVRVZUJOZUDGS",
			"PFGAYBDEECHUXFUZIKAXYDFWJNSAOPJYWUIEJSCORRBVQHCHMR",
			"JNVIPVEMQSHCCAXMWEFSYIGFPIXNIDXOTXTNBCHSHUZGKXFECL",
			"YZBAIIOTWLREPZISBGJLQDALKZUKEQMKLDIPXJEPENEIPWFDLP",
			"HBQKWJFLSEXVILKYPNSWUZLDCRTAYUUPEITQJEITZRQMMAQNLN",
			"DQDJGOWMBFKAIGWEAJOISPFPLULIWVVALLIIHBGEZLGRHRCKGF",
			"LXYPCVPNUKSWCCGXEYTEBAWRLWDWNHHNNNWQNIIBUCGUJYMRYW",
			"CZDKISKUSBPFHVGSAVJBDMNPSDKFRXVVPLVAQUGVUJEXSZFGFQ",
			"IYIJGISUANRAXTGQLAVFMQTICKQAHLEBGHAVOVVPEXIMLFWIYI",
			"ZIIFSOPCMAWCBPKWZBUQPQLGSNIBFADUUJJHPAIUVVNWNWKDZB",
			"HGTEEIISFGIUEUOWXVTPJDVACYQYFQUCXOXOSSMXLZDQESHXKP",
			"FEBZHJAGIFGXSMRDKGONGELOALLSYDVILRWAPXXBPOOSWZNEAS",
			"VJGMAOFLGYIFLJTEKDNIWHJAABCASFMAKIENSYIZZSLRSUIPCJ",
			"BMQGMPDRCPGWKTPLOTAINXZAAJWCPUJHPOUYWNWHZAKCDMZDSR",
			"RRARTVHZYYCEDXJQNQAINQVDJCZCZLCQWQQIKUYMYMOVMNCBVY",
			"ABTCRRUXVGYLZILFLOFYVWFFBZNFWDZOADRDCLIRFKBFBHMAXX"
	};
//	public static int n=2,m=4;
//	public static String s[]={"LANN","QIAO"};
	public static void main(String[] args) {
		int ans=0;
		char c[][]=new char [n][m];
		for(int i=0;i<n;i++){
			c[i]=s[i].toCharArray();
		}
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				for(int k=1;k<m;k++){
					if(j+k<c[i].length&&c[i][j]<c[i][j+k]){
						System.out.println(c[i][j]+""+c[i][j+k]);
						ans++;
					}
					if(i+k<c.length&&c[i][j]<c[i+k][j]){
						System.out.println(c[i][j]+""+c[i+k][j]);
						ans++;
					}
					if(j+k<c[i].length&&i+k<c.length&&c[i][j]<c[i+k][j+k]){
						System.out.println(c[i][j]+""+c[i+k][j+k]);
						ans++;
					}
					if(j+k<c[i].length&&i-k>=0&&c[i][j]!=c[i-k][j+k]){
						System.out.println(c[i][j]+""+c[i-k][j+k]);
						ans++;
					}
				}
			}
		}
		System.out.println(ans);
	}
}

B：平方拆分（難度：★）.

【問題描述】
將 2019 拆分為若干個兩兩不同的完全平方數之和，一共有多少種不同的方
法？
注意交換順序視為同一種方法，例如 132 + 252 + 352 = 2019 與 132 + 352 +
252 = 2019 視為同一種方法，
【答案提交】
這是一道結果填空的題，你只需要算出結果后提交即可，本題的結果為一
個整數，在提交答案時只填寫這個整數，填寫多余的內容將無法得分，

分析：

深搜解決，將已選元素放入list容器，記錄當前最大元素cur，記錄剩余需要拼合的和n，
不斷遞回迭代呼叫即可
當運行到出口即為答案，

AC代碼：

答案為：26287

package JAVA2019;

import java.util.ArrayList;
import java.util.Arrays;

public class B平方拆分 {
	public static int cnt=0;
	public static void dfs(ArrayList<Integer> list,int cur,int n){
		if(n==0){
			cnt++;
		}else{
			for(int i=cur+1;i*i<=n;i++){
				list.add(i);
				dfs(list, i, n-i*i);
				list.remove(list.size()-1);
			}
		}
	}
	public static void main(String[] args) {
		ArrayList<Integer> list=new ArrayList<Integer>();
		dfs(list, 0, 2019);
		System.out.println(cnt);
	}
}

C：切割（難度：★★）.

【問題描述】
在 4 × 4 的方格矩陣中畫一條直線，則直線穿過的方格集合有多少種不同的
可能？
這個里直線穿過一個方格當且僅當直線將該方格分割成面積都大于 0 的兩
部分，
【答案提交】
這是一道結果填空的題，你只需要算出結果后提交即可，本題的結果為一
個整數，在提交答案時只填寫這個整數，填寫多余的內容將無法得分

分析：

AC代碼：

D：最優旅行（難度：★★★）.

【問題描述】
中國的高鐵四通八達，乘坐方便，小明經常乘坐高鐵在城市間旅游，
現在，小明又有了一個長假，他打算繼續乘坐高鐵旅游，這次，他打算到
下面的城市旅游，
上海、廣州、長沙、西安、杭州、濟南、成都、南京、昆明、鄭州、天津、
太原、武漢、重慶、南昌、長春、沈陽、貴陽、福州，
小明打算從北京出發，游覽以上每個城市正好一次，最侄訓到北京，在每
個城市（除北京外），小明都至少停留 24 小時，而當小明決定從一個城市去往
另一個城市時，他只會選擇有直接高鐵連接的城市，不會在中途換乘轉車，
在試題目錄下有一個檔案 trip.txt 保存了小明可以選擇的車次，小明不會
選擇其他車次，
小明出發的時間是第 1 天的中午 12:00，請問，小明游覽完以上城市正好一
次，最侄訓到北京，最快需要多少分鐘（請注意單位為分鐘，請注意除北京外
的城市需要至少停留 24 小時，即最少停留 1440 分鐘），
【答案提交】
這是一道結果填空的題，你只需要算出結果后提交即可，本題的結果為一
個整數，在提交答案時只填寫這個整數，填寫多余的內容將無法得分，

分析：

AC代碼：

E：序列求和（難度：★★★★）.

【問題描述】
學習了約數后，小明對于約數很好奇，他發現，給定一個正整數 t，總是可
以找到含有 t 個約數的整數，小明對于含有 t 個約數的最小數非常感興趣，并
把它定義為 S t ，
例如 S 1 = 1, S 2 = 2, S 3 = 4, S 4 = 6，· · · ，
現在小明想知道，前 60 個 S i 的和是多少？即 S 1 + S 2 + · · · + S 60 是多少？
【答案提交】
這是一道結果填空的題，你只需要算出結果后提交即可，本題的結果為一
個整數，在提交答案時只填寫這個整數，填寫多余的內容將無法得分，

分析：

AC代碼：

F：最長子序列（難度：★★★★★）.

【問題描述】
我們稱一個字串 S 包含字串 T 是指 T 是 S 的一個子序列，即可以從
字串 S 中抽出若干個字符，它們按原來的順序組合成一個新的字串與 T 完
全一樣，
給定兩個字串 S 和 T，請問 T 中從第一個字符開始最長連續多少個字符
被 S 包含？
【輸入格式】
輸入兩行，每行一個字串，第一行的字串為 S，第二行的字串為 T，
兩個字串均非空而且只包含大寫英文字母，
【輸出格式】
輸出一個整數，表示答案，
【樣例輸入】
ABCDEABCD
AABZ
【樣例輸出】
3
【評測用例規模與約定】
對于 20% 的評測用例，1 ≤ |T| ≤ |S | ≤ 20；
對于 40% 的評測用例，1 ≤ |T| ≤ |S | ≤ 100；
對于所有評測用例，1 ≤ |T| ≤ |S | ≤ 1000，

分析：

思路很簡單，從頭到尾遍歷串S，遇到與 t[p] 相同的 p++ 即可，
最終運行結束 p就是答案

AC代碼：

`package JAVA2019;

import java.util.Scanner;

public class F最長子序列 {
	public static void main(String[] args) {
		Scanner scanner=new Scanner(System.in);
		String s=scanner.next();
		String t=scanner.next();
		int p=0;
		for(int i=0;i<s.length();i++){
			if(s.charAt(i)==t.charAt(p)){
				p++;
				if(p==t.length()){
					break;
				}
			}
		}
		System.out.println(p);
	}
}

G：數正方形（難度：★★★★★

【問題描述】
在一個 N × N 的點陣上，取其中 4 個點恰好組成一個正方形的 4 個頂點，
一共有多少種不同的取法？
由于結果可能非常大，你只需要輸出模 109 + 7 的余數，
如上圖所示的正方形都是合法的，
【輸入格式】
輸入包含一個整數 N，
【輸出格式】
輸出一個整數代表答案，
【樣例輸入】
4
【樣例輸出】
20
【資料規模與約定】
對于所有評測用例，2 ≤ N ≤ 1000000，

分析：

AC代碼：

H：大胖子走迷宮（難度：★★★★★）.

【問題描述】
小明是個大胖子，或者說是個大大胖子，如果說正常人占用 1 × 1 的面積，
小明要占用 5 × 5 的面積，
由于小明太胖了，所以他行動起來很不方便，當玩一些游戲時，小明相比
小伙伴就吃虧很多，
小明的朋友們制定了一個計劃，幫助小明減肥，計劃的主要內容是帶小明
玩一些游戲，讓小明在游戲中運動消耗脂肪，走迷宮是計劃中的重要環節，
朋友們設計了一個迷宮，迷宮可以看成是一個由 n × n 個方陣組成的方陣，
正常人每次占用方陣中 1 × 1 的區域，而小明要占用 5 × 5 的區域，小明的位置
定義為小明最正中的一個方格，迷宮四周都有障礙物，
為了方便小明，朋友們把迷宮的起點設定在了第 3 行第 3 列，終點設定在
了第 n n 2 行第 n n 2 列，
小明在時刻 0 出發，每單位時間可以向當前位置的上、下、左、右移動單
位 1 的距離，也可以停留在原地不動，小明走迷宮走得很辛苦，如果他在迷宮
里面待的時間很長，則由于消耗了很多脂肪，他會在時刻 k 變成一個胖子，只
占用 3 × 3 的區域，如果待的時間更長，他會在時刻 2k 變成一個正常人，只占
用 1 × 1 的區域，注意，當小明變瘦時迷宮的起點和終點不變，
請問，小明最少多長時間能走到迷宮的終點，注意，小明走到終點時可能
變瘦了也可能沒有變瘦，
【輸入格式】
輸入的第一行包含兩個整數 n, k，
接下來 n 行，每行一個由 n 個字符組成的字串，字符為 + 表示為空地，
字符為 * 表示為阻礙物，
【輸出格式】
輸出一個整數，表示答案，
【樣例輸入】

9 5
+++++++++
+++++++++
+++++++++
+++++++++
+++++++++
***+*****
+++++++++
+++++++++
+++++++++

【樣例輸出】
16
【評測用例規模與約定】
對于 30% 的評測用例，1 ≤ n ≤ 50，
對于 60% 的評測用例，1 ≤ n ≤ 100，
對于所有評測用例，1 ≤ n ≤ 300，1 ≤ k ≤ 1000，

分析：

AC代碼：

I：估計人數（難度：★★★★★）.

【問題描述】
給定一個 N × M 的方格矩陣，矩陣中每個方格標記 0 或者 1 代表這個方格
是不是有人踩過，
已知一個人可能從任意方格開始，之后每一步只能向右或者向下走一格，
走了若干步之后，這個人可以離開矩陣，這個人經過的方格都會被標記為 1，
包括開始和結束的方格，注意開始和結束的方格不需要一定在矩陣邊緣，
請你計算至少有多少人在矩陣上走過，
【輸入格式】
輸入第一行包含兩個整數 N、M，
以下 N 行每行包含 M 個整數 (0/1)，代表方格矩陣，
【輸出格式】
輸出一個整數代表答案，
【樣例輸入】
5 5
00100
11111
00100
11111
00100
【樣例輸出】
3
【資料規模與約定】
對于所有評測用例，1 ≤ N, M ≤ 20，標記為 1 的方格不超過 200 個，

分析：

AC代碼：

J：分考場（難度：★★★★★）.

【問題背景】
古語有云：春風得意馬蹄疾，一日看盡長安花，
當然在一場考試中所有人都春風得意馬蹄疾是不可能的，尤其是碰到一些
毒瘤出題人的時候，
【問題描述】
又到了每月一次的月考，又是 xf 老師出題，
上一次 xf 老師出的題太毒瘤了，平均分只有 40 多，同學們都非常不滿意，
畢竟別的科的平均分都是 80 多，
這次 xf 為了不被同學們寄刀片，想了一個辦法：只公布所有考場的平均分
的平均分，這樣他就可以通過調整考場的分配方式，使得平均分顯得高，（每個
考場都可以容納無限人）
每次考試也不是所有同學都參加的，只有學號在 [l,r] 這個區間中的同學會
參加，
他想知道對于每次考試，他調整過考場后，所有考場的平均分的平均分的
最大值，
當然，同學們也可能會努力學習或整日頹廢使成績發生改變，
【輸入格式】
輸入的第一行包含一個整數 n，
第二行包含 n 個整數，第 i 個數 vi，表示開始時每個同學的成績，
第三行包含一個整數 q，表示有 q 次操作，
之后 q 行，每行描述一個操作，第一個數表示操作型別，
如果操作為 1 p x，表示學號為 p 的同學分數變為 x，
如果操作為 2 l r k, 表示把學號在 [l,r] 中的同學分成 k 個考場，求這 k 個
考場的平均分的平均分的最大值，
【輸出格式】
對于每個 2 操作輸出一行，四舍五入保留正好 3 位小數，
【樣例輸入】
5
5 3 4 2 1
5
2 1 4 3
1 4 8
2 3 5 3
1 2 2
2 1 3 2
【樣例輸出】
3.833
4.333
4.000
【樣例說明】
第一個操作詢問學號在 [1, 4] 之間的同學分成 3 個考場的平均分的平均分
的最大值，最優策略是：{1}, {2, 4}, {3}，平均分是

第二個操作把學號為 4 的同學的分數變為 8，
第三個操作詢問學號在 [3, 5] 之間的同學分成 3 個考場的平均分的平均分
的最大值，最優策略是：{3}, {4}, {5}，
第四個操作把學號為 2 的同學分數變為 2，
第五個操作詢問學號在 [1, 3] 之間的同學分成 2 個考場的平均分的平均分
的最大值，最優策略是：{1}, {2 3}，
【評測用例規模與約定】
對于全部評測用列，n ≤ 200000, q ≤ 200000, 任意時刻同學的分數 vi ≤ 10^9， k ≤ r - l+ 1，
評測時將使用 10 個評測用例測驗你的程式，每個評測用例的限制如下：

分析：

AC代碼：