第十屆藍橋杯決賽JavaC組真題——詳細答案對照(完整版)
目錄
A、奇數倍數
B、遞增序列
C、平方拆分
D、切割(挺過分的題)
E、序列求和
F、最長子序列
G、數正方形
H、矩陣計數
I、大胖子走迷宮
J、估計人數
A、奇數倍數
本題總分：5 分
問題描述
請你找到最小的整數 X 同時滿足：
X 是 2019 的整倍數
X 的每一位數字都是奇數
package action; public class demo { public static void main(String[] args) { a: for (int i = 2019, n = 2019; true; n = i += 2019) { do { if ((n & 1) == 0) continue a; } while ((n /= 10) > 0); System.out.println(i); break; } } }
B、遞增序列
本題總分：5 分
問題描述
對于一個字母矩陣，我們稱矩陣中的一個遞增序列是指在矩陣中找到兩個字母，它們在同一行，同一列，或者在同一 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
package action; import java.io.BufferedReader; public class demo { static String str = "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"; static char[][] c = new char[30][50]; static int count = 0; public static void main(String[] args) { for (int i = 0; i < c.length; i++) { for (int j = 0; j < c[i].length; j++) { c[i][j] = str.charAt(i * c[i].length + j); } } for (int i = 0; i < c.length; i++) { for (int j = 0; j < c[i].length; j++) { check(i, j); } } System.out.println(count); } public static void check(int i, int j) { // 右 for (int k = 1; k < c[i].length - j; k++) { if (j + k < c[i].length && c[i][j] < c[i][j + k]) { count++; } } // 下 for (int k = 1; k < c.length - i; k++) { if (i + k < c.length && c[i][j] < c[i + k][j]) { count++; } } // 右下角 for (int k = 1; k < c.length - i; k++) { if (i + k < c.length && j + k < c[i].length && c[i][j] < c[i + k][j + k]) { count++; } } // 右上角 for (int k = 1; k < c.length; k++) { if (i - k >= 0 && j + k < c[i].length && c[i][j] < c[i - k][j + k]) { count++; } } // 左下角 for (int k = 1; k < c.length; k++) { if (i + k < c.length && j - k >= 0 && c[i][j] < c[i + k][j - k]) { count++; } } } }
這種題沒啥猶豫的，暴力吧。
C、平方拆分
本題總分：10 分
問題描述
將 2019 拆分為若干個兩兩不同的完全平方數之和，一共有多少種不同的方法？
注意交換順序視為同一種方法，例如 13^2 + 25^2 + 35^2 = 2019 與 13^2 + 35^2 +25^2 = 2019 視為同一種方法(^代表平方)。
package action; public class demo { static int count = 0; public static void main(String[] args) { dfs(2019, -1); System.out.println(count); } public static void dfs(int num, int start) { if (num < 0) { return; } if (num == 0) { count++; } else { for (int i = start + 1, high = (int) Math.sqrt(num); i <= high; i++) dfs(num - i * i, i); } } }
D、切割(挺過分的題)
本題總分：10 分
問題描述
在 4 × 4 的方格矩陣中畫一條直線。則直線穿過的方格集合有多少種不同的可能？這個里直線穿過一個方格當且僅當直線將該方格分割成面積都大于 0 的兩部分。
答案提交
這是一道結果填空的題，你只需要算出結果后提交即可。本題的結果為一個整數，在提交答案時只填寫這個整數，填寫多余的內容將無法得分。
package action; import java.util.HashSet; import java.util.Set; public class demo { final static int range = 100; static Set
E、序列求和
本題總分：15 分
問題描述
學習了約數后，小明對于約數很好奇，他發現，給定一個正整數 t，總是可以找到含有 t 個約數的整數。小明對于含有 t 個約數的最小數非常感興趣，并把它定義為 St 。
例如 S1 = 1, S2 = 2, S3 = 4, S4 = 6，· · · 。
現在小明想知道，前 60 個 Si 的和是多少？即 S1 + S2 + · · · + S60 是多少？
答案提交
這是一道結果填空的題，你只需要算出結果后提交即可。本題的結果為一個整數，在提交答案時只填寫這個整數，填寫多余的內容將無法得分。
package action; import java.util.Collections; import java.util.List; import java.util.Vector; import static java.lang.Math.min; import static java.lang.Math.pow; public class demo { static List
看到有人說結果是：【101449】，但是我能確定【292809912969717649】絕對是給分了的。
F、最長子序列
時間限制: 1.0s 內存限制: 512.0MB 本題總分：15 分
問題描述
我們稱一個字符串 S 包含字符串 T 是指 T 是 S 的一個子序列，即可以從字符串 S 中抽出若干個字符，它們按原來的順序組合成一個新的字符串與 T 完全一樣。
給定兩個字符串 S 和 T，請問 T 中從第一個字符開始最長連續多少個字符被 S 包含？
輸入格式
輸入兩行，每行一個字符串。第一行的字符串為 S，第二行的字符串為 T。
兩個字符串均非空而且只包含大寫英文字母。
輸出格式
輸出一個整數，表示答案。
測試樣例1
Input：
ABCDEABCD
AABZ
Output：
3
評測用例規模與約定
對于 20% 的評測用例，1 ≤ |T| ≤ |S | ≤ 20；
對于 40% 的評測用例，1 ≤ |T| ≤ |S | ≤ 100；
對于所有評測用例，1 ≤ |T| ≤ |S | ≤ 1000。
package action; import java.util.Scanner; public class demo { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String s1 = sc.next(); String s2 = sc.next(); sc.close(); int n1 = 0; int n2 = 0; int sum = 0; for (; n1 < s1.length(); n1++) { if (s1.charAt(n1) == s2.charAt(n2)) { sum++; n2++; } } System.out.println(sum); } }
G、數正方形
時間限制: 1.0s 內存限制: 512.0MB 本題總分：20 分
問題描述
在一個 N × N 的點陣上，取其中 4 個點恰好組成一個正方形的 4 個頂點，一共有多少種不同的取法？
由于結果可能非常大，你只需要輸出模 109 + 7 的余數。
（如：圖7）所示的正方形都是合法的。
輸入格式
輸入包含一個整數 N。
輸出格式
輸出一個整數代表答案。
測試樣例1
Input：
4
Output：
20
評測用例規模與約定
對于所有評測用例，2 ≤ N ≤ 1000000。
package action; import java.math.BigInteger; import java.util.Scanner; public class demo { final static BigInteger mod = BigInteger.valueOf(1000_000_007); public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); sc.close(); BigInteger ans = BigInteger.ZERO; for (int i = 1; i <= n; i++) { BigInteger x = BigInteger.valueOf(n - i); ans = ans.add(BigInteger.valueOf(i).multiply(x.pow(2))).mod(mod); } System.out.println(ans.longValue()); } }
H、矩陣計數
時間限制: 1.0s 內存限制: 512.0MB 本題總分：20 分
問題描述
一個 N × M 的方格矩陣，每一個方格中包含一個字符 O 或者字符 X。
要求矩陣中不存在連續一行 3 個 X 或者連續一列 3 個 X。
問這樣的矩陣一共有多少種？
輸入格式
輸入一行包含兩個整數 N 和 M。
輸出格式
輸出一個整數代表答案。
測試樣例1
Input：
2 3
Output：
49
評測用例規模與約定
對于所有評測用例，1 ≤ N, M ≤ 5。
package action; import java.util.Scanner; public class demo { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n1 = sc.nextInt(); int n2 = sc.nextInt(); sc.close(); int a[][] = new int[n1][n2]; int sum = 0; for (int t = 0; t < Math.pow(2, n1 * n2); t++) { int x = 0; // 將數組賦值 for (int i = 0; i < n1; i++) { for (int j = 0; j < n2; j++) { if ((t >> x & 1) == 1) { a[i][j] = 1; } x++; } } if (check(a)) {// 檢查數組 } else { sum++; } // 數組清空 for (int i = 0; i < n1; i++) { for (int j = 0; j < n2; j++) { a[i][j] = 0; } } } System.out.println(sum); } private static boolean check(int[][] a) { int x = 0; for (int i = 0; i < a.length; i++) { for (int j = 0; j < a[0].length; j++) { if (a.length - i > 2 & a[i][j] == 1) { if (a[i + 1][j] == 1 & a[i + 2][j] == 1) { x = 1; return true; } } if (a[0].length - j > 2 & a[i][j] == 1) { if (a[i][j + 1] == 1 & a[i][j + 2] == 1) { x = 1; return true; } } } } if (x == 1) { return true; } return false; } }
I、大胖子走迷宮
時間限制: 1.0s 內存限制: 512.0MB 本題總分：25 分
問題描述
小明是個大胖子，或者說是個大大胖子，如果說正常人占用 1 × 1 的面積，小明要占用 5 × 5 的面積。由于小明太胖了，所以他行動起來很不方便。當玩一些游戲時，小明相比小伙伴就吃虧很多。
小明的朋友們制定了一個計劃，幫助小明減肥。計劃的主要內容是帶小明玩一些游戲，讓小明在游戲中運動消耗脂肪。走迷宮是計劃中的重要環節。
朋友們設計了一個迷宮，迷宮可以看成是一個由 n × n 個方陣組成的方陣，正常人每次占用方陣中 1 × 1 的區域，而小明要占用 5 × 5 的區域。小明的位置定義為小明最正中的一個方格。迷宮四周都有障礙物。
為了方便小明，朋友們把迷宮的起點設置在了第 3 行第 3 列，終點設置在了第 n-2 行第 n-2 列。
小明在時刻 0 出發，每單位時間可以向當前位置的上、下、左、右移動單位 1 的距離，也可以停留在原地不動。小明走迷宮走得很辛苦，如果他在迷宮里面待的時間很長，則由于消耗了很多脂肪，他會在時刻 k 變成一個胖子，只占用 3 × 3 的區域。如果待的時間更長，他會在時刻 2k 變成一個正常人，只占用 1 × 1 的區域。注意，當小明變瘦時迷宮的起點和終點不變。
請問，小明最少多長時間能走到迷宮的終點。注意，小明走到終點時可能變瘦了也可能沒有變瘦。
輸入格式
輸入的第一行包含兩個整數 n, k。
接下來 n 行，每行一個由 n 個字符組成的字符串，字符為 + 表示為空地，
字符為 * 表示為阻礙物。
輸出格式
輸出一個整數，表示答案。
測試樣例1
Input：
9 5
+++++++++
+++++++++
+++++++++
+++++++++
+++++++++
***+*****
+++++++++
+++++++++
+++++++++
Output：
16
評測用例規模與約定
對于 30% 的評測用例，1 ≤ n ≤ 50。
對于 60% 的評測用例，1 ≤ n ≤ 100。
對于所有評測用例，1 ≤ n ≤ 300，1 ≤ k ≤ 1000。
package action; import java.io.IOException; import java.io.InputStream; import java.util.LinkedList; import java.util.Queue; public class demo { public static void main(String[] args) { InputReader in = new InputReader(System.in); int n = in.nextInt(), k = in.nextInt(); if (n <= 5) System.out.print('0'); else { int map[][] = new int[n][n], INF = 0x3F3F3F3F; boolean[][] visit = new boolean[n][n]; for (int i = 0, hi = n - 1; i <= hi; i++) { if (i < hi) map[1][i] = map[hi - 1][i] = map[i][1] = map[i][hi - 1] = 1; map[0][i] = map[hi][i] = map[i][0] = map[i][hi] = 2; } int[] os2i = { -1, -1, 0, 1, 1, 1, 0, -1 }; int[] os2j = { 0, 1, 1, 1, 0, -1, -1, -1 }; int[] os1i = { -2, -2, -2, -1, 0, 1, 2, 2, 2, 2, 2, 1, 0, -1, -2, -2 }; int[] os1j = { 0, 1, 2, 2, 2, 2, 2, 1, 0, -1, -2, -2, -2, -2, -2, -1 }; for (int i = 0, x, y; i < n; i++) for (int j = 0; j < n; j++) { if (in.split() == '*') { map[i][j] = INF; for (int l = 0; l < 8; l++) { x = i + os2i[l]; y = j + os2j[l]; if (x < 0 || x >= n || y < 0 || y >= n || map[x][y] > 2) continue; map[x][y] = 2; } for (int l = 0; l < 16; l++) { x = i + os1i[l]; y = j + os1j[l]; if (x < 0 || x >= n || y < 0 || y >= n || map[x][y] > 1) continue; map[x][y] = 1; } } } class Step { int x, y, time; Step(int x, int y, int time) { this.x = x; this.y = y; this.time = time; } Step relax() { this.time++; return this; } } Queue
J、估計人數
時間限制: 1.0s 內存限制: 512.0MB 本題總分：25 分
問題描述
給定一個 N × M 的方格矩陣，矩陣中每個方格標記 0 或者 1 代表這個方格是不是有人踩過。
已知一個人可能從任意方格開始，之后每一步只能向右或者向下走一格。
走了若干步之后，這個人可以離開矩陣。這個人經過的方格都會被標記為 1，包括開始和結束的方格。注意開始和結束的方格不需要一定在矩陣邊緣。
請你計算至少有多少人在矩陣上走過。
輸入格式
輸入第一行包含兩個整數 N、M。
以下 N 行每行包含 M 個整數 (0/1)，代表方格矩陣。
輸出格式
輸出一個整數代表答案。
測試樣例1
Input：
5 5
00100
11111
00100
11111
00100
Output：
3
評測用例規模與約定
對于所有評測用例，1 ≤ N, M ≤ 20，標記為 1 的方格不超過 200 個。
package action; import java.io.IOException; import java.io.InputStream; import java.util.Arrays; public class demo { static int V = 1; static int source[]; static boolean graph[][], marked[]; public static void main(String[] args) { InputReader in = new InputReader(System.in); int n = in.nextInt(), m = in.nextInt(); int idx[][] = new int[n + 1][m + 1]; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) if (in.split() == '1') idx[i][j] = V++; graph = new boolean[V][V]; marked = new boolean[V]; source = new int[V]; for (int i = 0, v; i < n; i++) for (int j = 0; j < m; j++) if (idx[i][j] > 0) { v = idx[i][j]; if (idx[i + 1][j] > 0) graph[v][idx[i + 1][j]] = true; if (idx[i][j + 1] > 0) graph[v][idx[i][j + 1]] = true; } for (int k = 1; k < V; k++) for (int i = 1; i < V; i++) for (int j = 1; j < V; j++) graph[i][j] |= graph[i][k] & graph[k][j]; int cnt = 0; for (int i = 1; i < V; i++) { Arrays.fill(marked, false); cnt += dfs(i) ? 1 : 0; } System.out.print(V - cnt - 1); } static boolean dfs(int v) { for (int i = 1; i < V; i++) { if (graph[v][i]) { if (marked[i]) continue; marked[i] = true; if (source[i] == 0 || dfs(source[i])) { source[i] = v; return true; } } } return false; } static class InputReader { InputStream in; int next, len; byte[] buff; InputReader(InputStream in) { this(in, 8192); } InputReader(InputStream in, int buffSize) { this.buff = new byte[buffSize]; this.next = this.len = 0; this.in = in; } int getByte() { if (next >= len) try { next = 0; len = in.read(buff); if (len == -1) return -1; } catch (IOException e) { e.fillInStackTrace(); } return buff[next++]; } int split() { int c = getByte(); while (c <= 32 || c == 127) c = getByte(); return c; } int nextInt() { int n = 0, c = split(); boolean flag = true; if (c == '-') { c = getByte(); flag = false; } while (c >= '0' && c <= '9') { n = n * 10 + (c & 0xf); c = getByte(); } return flag ? n : -n; } } }
這套題有幾個題應該是給本科的，專門刁難了一下大專的孩子們，不道義啊。
Java 數據結構
版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。
相關文章
