第十屆藍橋杯 2019年國賽真題（Java 大學C組）（第十屆藍橋杯scratch真題和答案）

#A 奇數倍數

題目：

問題描述 請你找到最小的整數 X 同時滿足： X 是 2019 的整倍數 X 的每一位數字都是奇數

import java.util.*; public class Main { public static void main(String args[]) { for (int i = 2019; i < 1000000; i+=2019) { int x=0; int t=i; while(t>0) { if (t%10%2==0) { x=1; } t=t/10; } if (x==0) { System.out.println(i); break; } } } }

#B 遞增序列

題目：

問題描述 對于一個字母矩陣，我們稱矩陣中的一個遞增序列是指在矩陣中找到兩個字母，它們在同一行，同一列，或者在同一 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 藍橋杯省模擬賽_高職組; import java.util.Scanner; public class 遞增序列 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] num = new int[n]; int temp=-1; int count=0; int max=0; for (int i=0;i

#C 平方拆分

題目：

問題描述 將 2019 拆分為若干個兩兩不同的完全平方數之和，一共有多少種不同的方法？ 注意交換順序視為同一種方法，例如 13^2 + 25^2 + 35^2 = 2019 與 13^2 + 35^2 +25^2 = 2019 視為同一種方法(^代表平方)。

public class Main1 { public static void main(String[] args) { dfs(2019,0,45); System.out.println(sum); } static int sum; //深搜平方和為2019的所有子集 private static void dfs(int num, int min, int max) { if (num < 0) { return; } if (num == 0) { sum ++; return; } for (int i = min; i < max; i++) { //去重，保證下一位數字一定大于當前數字 dfs(num - i * i, i + 1, max); } } }

#D 切割

題目：

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

import java.util.HashSet; import java.util.Set; public class Main { //方格字符標記 String[][] ss = { { "1", "2", "3", "4" }, { "5", "6", "7", "8" }, { "9", "a", "b", "c" }, { "d", "e", "f", "g" } }; //結果集合 Set set = new HashSet(); int a = 0, b = 0, c = 0, d = 0; public Main() { //遍歷x1,x2 for (int x1 = 0; x1 <= 400; x1++) { for (int x2 = 0; x2 <= 400; x2++) { // System.out.println("x1="+x1+",x2="+x2); if (x1 == 0 || x1 == 400) { // 固定x1，直線從側邊出去的結果 getlist4(x1, x2); } // 固定y=400，直線從頂部出去的數量結果 getlist(x1, x2); } } System.out.println(a); System.out.println(b); System.out.println(c); System.out.println(d); System.out.println(set.size()); } // 分別統計字符開頭的數據，用于觀察 public void count(String s) { if (s.startsWith("1")) { a++; } else if (s.startsWith("2")) { b++; } else if (s.startsWith("3")) { c++; } else if (s.startsWith("4")) { d++; } } // 求頂部結果 public void getlist(double x1, double x2) { String s = ""; for (int i = 0; i < 400; i++) { double x = x2 + (x1 - x2) / 400 * i; if (x > 0 && x < 100) {// 第一格內 if (s.equals("") || !s.substring(s.length() - 1, s.length()).equals(ss[i / 100][0])) { s += ss[i / 100][0]; } } else if (x > 100 && x < 200) {// 第二格內 if (s.equals("") || !s.substring(s.length() - 1, s.length()).equals(ss[i / 100][1])) { s += ss[i / 100][1]; } } else if (x > 200 && x < 300) {// 第三格內 if (s.equals("") || !s.substring(s.length() - 1, s.length()).equals(ss[i / 100][2])) { s += ss[i / 100][2]; } } else if (x > 300 && x < 400) {// 第四格內 if (s.equals("") || !s.substring(s.length() - 1, s.length()).equals(ss[i / 100][3])) { s += ss[i / 100][3]; } } } // 存起來 if (!s.equals("") && !set.contains(s)) { // System.out.println(s); count(s); set.add(s); } } // 求兩側邊結果 public void getlist4(double x1, double x2) { String s = ""; // 這里x1,x2固定時，y在變化， for (int j = 0; j < 400; j++) { //每次變化都是不一樣的直線 for (int i = 0; i < j; i++) { double x = x2 + (x1 - x2) / j * i; if (x > 0 && x < 100) {// 第一格內 if (s.equals("") || !s.substring(s.length() - 1, s.length()).equals(ss[i / 100][0])) { s += ss[i / 100][0]; } } else if (x > 100 && x < 200) {// 第二格內 if (s.equals("") || !s.substring(s.length() - 1, s.length()).equals(ss[i / 100][1])) { s += ss[i / 100][1]; } } else if (x > 200 && x < 300) {// 第三格內 if (s.equals("") || !s.substring(s.length() - 1, s.length()).equals(ss[i / 100][2])) { s += ss[i / 100][2]; } } else if (x > 300 && x < 400) {// 第四格內 if (s.equals("") || !s.substring(s.length() - 1, s.length()).equals(ss[i / 100][3])) { s += ss[i / 100][3]; } } } // 存起來 if (!s.equals("") && !set.contains(s)) { // System.out.println(s); count(s); set.add(s); } s = ""; } } public static void main(String[] args) { new Main(); } }

#E 序列求和

題目：

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

package com.cxyax.november.tenth; import java.util.ArrayList; import java.util.List; public class Main { public static void main(String[] args) { //用list集合去裝每次的值 List list = new ArrayList(); int sum = 0; //遍歷循環60次，即S60 for(int i = 1; i <= 60;i++) { //每次都進行爆破 for(int j = 1; ; j++ ) { //在每次進入時清除list集合，下步使用 list.clear(); //尋找約數 for(int k = 1; k <= j;k++) { //判斷約數 if(j%k==0) { //如果是把約數加進list集合 list.add(k); } //判斷因數個數是否等于i if(list.size() == i) { sum += j; break; } } //如果等于i即跳出循環 if(list.size() == i) { break; } } } System.out.println(sum); } }

#F 最長子序列

題目：

問題描述 我們稱一個字符串 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。

import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sn=new Scanner(System.in); String S=sn.next(); String T=sn.next(); char[] s=S.toCharArray(); char[] t=T.toCharArray(); int k=0;//統計個數 for(int j=0;j

#G 數正方形

題目：

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

import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sn = new Scanner(System.in); int n = sn.nextInt() - 1; long count = 0; long num = 1000000007; //平放 // a 表示正方形邊長 for (int a = 1; a <= n; a++) { count += (n - a + 1) * (n - a + 1); count%=num; } // 斜放 //i+j=斜正方形所占區域的邊長=平放正方形的邊長 //但i+j>=2，也就是平放正方形的邊長從2開始 for (int i = 1; i <= n - 1; i++) { for (int j = 1; j <= n - i; j++) { count += (n - (i + j) + 1) * (n - (i + j) + 1); count%=num; } } System.out.println(count); } }

#H 矩陣計數

題目：

問題描述 一個 N × M 的方格矩陣，每一個方格中包含一個字符 O 或者字符 X。 要求矩陣中不存在連續一行 3 個 X 或者連續一列 3 個 X。 問這樣的矩陣一共有多少種？ 輸入格式 輸入一行包含兩個整數 N 和 M。 輸出格式 輸出一個整數代表答案。 測試樣例1 Input： 2 3 Output： 49 評測用例規模與約定 對于所有評測用例，1 ≤ N, M ≤ 5。

import java.util.Scanner; public class test1 { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n1=sc.nextInt(); int n2=sc.nextInt(); long starttime=System.currentTimeMillis(); int a [][]=new int[n1][n2]; int sum=0; for(int t=0;t>x&1)==1) { a[i][j]=1; } x++; } } //檢查數組 if(check(a)) { }else { sum++; } //查看數組 // System.out.println(t); // for(int i=0;i2&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 × 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。

import java.util.Scanner; import java.util.concurrent.ArrayBlockingQueue; public class Main { int n;//n行n列 int k;//每k個小時小明瘦一圈 char[][] maze;//迷宮地圖 boolean[][] vis;//地圖訪問標記 ArrayBlockingQueue queue;//隊列 //位置節點 class Point { int x;//橫坐標 int y;//縱坐標 int time;//時間 Point parent;//從哪個位置節點來的 int a;//將肥胖轉換成比常人的厚度，最開始為2，方便計算坐標 public Point(int x1, int y1, Point p,int t,int a1) { this.x = x1; this.y = y1; this.parent = p; this.time=t; this.a=a1; } } public Main() { Scanner sn = new Scanner(System.in); n = sn.nextInt(); k = sn.nextInt(); maze = new char[n][n]; vis = new boolean[n][n]; sn.nextLine(); queue = new ArrayBlockingQueue(n * n); for (int i = 0; i < n; i++) { maze[i] = sn.nextLine().trim().toCharArray(); } //以上都是初始化 queue.add(new Point(2, 2, null,0,2));//加入初始點 vis[2][2] = true;//標記 Point p=bfs();//獲取到達終點的那個節點 System.out.println(p.time);//輸出時間 // //展示逆推路線 // while (p.parent != null) { // System.out.println("x="+p.x+"，y="+p.y+"，time="+p.time+",a="+p.a); // p = p.parent; // } // System.out.println("x="+p.x+"，y="+p.y+"，time="+p.time+",a="+p.a); } //廣度優先搜索 public Point bfs() { while (!queue.isEmpty()) { Point p = queue.poll();//取出隊頭 //更新時間，胖瘦 p.time++; if (p.time % k == 0 && p.a > 0) p.a--; //判斷這個節點是不是已經是終點了 if (p.x == n - 3 && p.y == n - 3) return p; //將四個方向可以移動的位置加入隊列 // 下 if (check(p.x, p.y + 1,p) && !vis[p.y + 1][p.x]) { queue.add(new Point(p.x, p.y + 1, p,p.time,p.a)); vis[p.y + 1][p.x] = true; } // 右 if (check(p.x + 1, p.y,p) && !vis[p.y][p.x + 1]) { queue.add(new Point(p.x + 1, p.y, p,p.time,p.a)); vis[p.y][p.x + 1] = true; } // 左 if (check(p.x - 1, p.y,p) && !vis[p.y][p.x - 1]) { queue.add(new Point(p.x - 1, p.y, p,p.time,p.a)); vis[p.y][p.x - 1] = true; } // 上 if (check(p.x, p.y - 1,p) && !vis[p.y - 1][p.x]) { queue.add(new Point(p.x, p.y - 1, p,p.time,p.a)); vis[p.y - 1][p.x] = true; } //如果存在空地但又無法移動，說明小明太胖了，重新加入隊列，相當于等待 if(exist(p.x, p.y)) { queue.add(p); } } //到不了終點，返回空 return null; } // 判斷p是否能移動到（x,y） public boolean check(int x, int y,Point p) { //x是否越界 if (x - p.a >= 0 && x + p.a < n) { //y是否越界 if (y - p.a >= 0 && y + p.a < n) { //x，y都正常，因此檢查若移動后自身范圍是否存在障礙物，若存在則無法移動 for (int i = x - p.a; i <= x + p.a; i++) { for (int j = y - p.a; j <= y + p.a; j++) { if (maze[j][i] == '*') return false; } } //全部通過檢查，可以移動 return true; } } //未通過檢查 return false; } //檢查上下左右當前還有空位 public boolean exist(int x, int y) { //左 if (x - 1 >= 0) { if (!vis[x - 1][y]) { return true; } } //上 if (y - 1 >= 0) { if (!vis[x][y - 1]) { return true; } } //下 if (y + 1 < n) { if (!vis[x][y + 1]) { return true; } } //右 if (x + 1 < n) { if (!vis[x + 1][y]) { return true; } } return false; } public static void main(String[] args) { new Main(); } }

#J 估計人數

題目：

問題描述 給定一個 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 第十屆決賽; import java.util.Arrays; import java.util.Scanner; public class 估計人數 { static int[][] map;//地圖 static boolean[][] con;//關系圖 static int[] boy;//匹配點 static boolean[] vis; static int n; static int m; static int sum = 1; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); m = sc.nextInt(); map = new int[n][n]; //寫入圖 for (int i = 0; i < n; i++) { String str = sc.next(); for (int j = 0; j < m; j++) { if (str.charAt(j) == '1') map[i][j] = sum++; } } con=new boolean[sum][sum]; boy=new int[sum]; vis=new boolean[sum]; //初始化關系圖 for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (map[i][j]>0&&i+10) con[map[i][j]][map[i+1][j]]=true; if (map[i][j]>0&&j+10) con[map[i][j]][map[i][j+1]]=true; } } //Floyd for (int i = 1; i < sum; i++) { for (int j = 1; j < sum; j++) { for (int k = 1; k < sum; k++) { if(con[j][i]&&con[i][k]&&j!=k) con[j][k]=true; } } } //匈牙利算法 int num=0; for (int i = 1; i < sum; i++) { Arrays.fill(vis, true); if(dfs(i)) num++; } System.out.println(sum-num-1); } static boolean dfs(int x) { for (int i = 1; i < sum; i++) { if(con[x][i]&&vis[i]) { vis[i]=false; if(boy[i]==0||dfs(boy[i])) { boy[i]=x; return true; } } } return false; } }

Java 大賽 數據結構

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。