2019 第十屆藍橋杯大賽軟體類省賽 Java A組
試題A
題解
? 題目最后一句貼心的提示選手應該使用 long (C/C++ 應該使用 long long)，
? 本題思路很直白，兩重回圈，外層回圈 1 到 2019，內層回圈檢驗是否含有 2、0、1、9 這四個數字，
? 賽場上還可以將數字轉換為字串，利用 String.contains() 快速寫出代碼，雖然時間復雜沒有改變，但應付填空題足矣，
代碼
public static void questionA() {
long sum = 0;
for (int i = 1; i <= 2019; i++) {
String int2str = String.valueOf(i);
if (int2str.contains("2") || int2str.contains("0") || int2str.contains("1") || int2str.contains("9"))
sum += i * i;
}
System.out.println(sum);
}
答案
2658417853
試題B
題解
? 遞推數列，從第四項開始，每項都是前三項的和，
? 易得到遞推式 \(a_n=a_{n-1}+a_{n-2}+a_{n-3}\)
代碼
public static void questionB() {
int a, b, c, d;
a = b = c = d = 1;
for (int i = 4; i <= 20190324; i++) {
d = (a + b + c) % 10000;
a = b;
b = c;
c = d;
}
System.out.println(d);
}
答案
4659
試題C
題解
? 本題使用廣度優先搜索即可，
代碼
private static void questionC() throws IOException {
int n = 30;
int m = 50;
FileReader fr = new FileReader(new File("maze.txt"));
char[][] board = new char[n][m];
for (int i = 0; i < board.length; i++) {
fr.read(board[i]);
// 讀取換行符和回車，避免讀入到 board 中
fr.read(); fr.read();
}
Queue<Node> queue = new LinkedList<>();
boolean[][] visited = new boolean[n][m];
queue.add(new Node(0, 0));
visited[0][0] = true;
int[][] way = new int[n][m]; // 記錄到達 (i, j) 的方式
int[][] delta = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
char[] cc = {'D', 'U', 'R', 'L'};
while (!queue.isEmpty()) {
Node cur = queue.poll();
for (int i = 0; i < 4; i++) {
int x = cur.x + delta[i][0];
int y = cur.y + delta[i][1];
if (x >= 0 && x < n && y >= 0 && y < m && board[x][y] != '1' && !visited[x][y]) {
queue.add(new Node(x, y));
way[x][y] = i;
visited[x][y] = true;
}
}
}
int x = n - 1;
int y = m - 1;
StringBuilder sb = new StringBuilder();
while (x != 0 || y != 0) {
int i = way[x][y];
sb.append(cc[i]);
x -= delta[i][0];
y -= delta[i][1];
}
System.out.println(sb.reverse());
}
static class Node {
int x;
int y;
public Node(int x, int y) {
this.x = x;
this.y = y;
}
}
答案
DDDDRRURRRRRRDRRRRDDDLDDRDDDDDDDDDDDDRDDRRRUUURRRRDDDDRDRRRRRURRRDRRDDDRRRRUURUUUUUUUULLLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDDRRRRRDDRRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR
試題D
題解
? 假設每周的數字從周一到周日遞增，每周周四的數字從第一周到第七周遞增，
? 則第四周周四的數字即為降雨量，
? 又知下面表格中 15 個 \(\$\) 上的數字必大于 \(x\) ，
? 故 \(x \leq 49 - 15 = 34\)
| 周一 | 周二 | 周三 | 周四 | 周五 | 周六 | 周日 | |
|---|---|---|---|---|---|---|---|
| 第一周 | |||||||
| 第二周 | |||||||
| 第三周 | |||||||
| 第四周 | \(x\) | $ | $ | $ | |||
| 第五周 | $ | $ | $ | $ | |||
| 第六周 | $ | $ | $ | $ | |||
| 第七周 | $ | $ | $ | $ |
答案
34
試題F
題解
? 完全二叉樹除最后一層外，第 n 層的節點數為 \(2^n\)，
? 我們完全可以利用這個特性，在輸入資料時按層統計，
代碼
public static void questionF() {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int n = 1;
int ans = 0;
int depth = 1;
long maxSum = Long.MIN_VALUE;
while (N > 0) {
long sum = 0;
for (int i = 0; i < n && N > 0; i++) {
sum += sc.nextInt();
N--;
}
if (sum > maxSum) {
maxSum = sum;
ans = depth;
}
n <<= 1;
depth++;
}
System.out.println(ans);
}
試題G
題解
? 每一個店鋪相互獨立，可以存盤每個店鋪的訂單時間，判斷店鋪是否在優先快取中，
? 需要注意 T 時刻的優先級判斷，
? 若 T 時刻，優先級 priority > 5，顯然位于優先快取中，
? 若 T 時刻，優先級 priority == 5，且 T 時刻有一訂單，則 T - 1時刻，優先級 priority 為 3，不在優先快取中，
? 若 T 時刻，優先級 priority == 4，且 T - 1、T - 2 時刻無訂單，則在優先快取中，
代碼
public static void questionG() {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int M = sc.nextInt();
int T = sc.nextInt();
ArrayList<Integer>[] store = new ArrayList[N + 1];
while(M-- > 0) {
int ts = sc.nextInt();
int id = sc.nextInt();
if (store[id] == null)
store[id] = new ArrayList<Integer>();
store[id].add(ts);
}
int ans = 0;
for (int id = 1; id <= N; id++) {
if (store[id] == null) continue;
Collections.sort(store[id]);
int lastTime = 0;
int priority = 0;
for (int order = 0; order < store[id].size(); order++) {
int ts = store[id].get(order);
if (ts - lastTime >= 1)
priority -= ts - lastTime - 1;
priority = Math.max(priority, 0);
priority += 2;
lastTime = ts;
}
priority -= T - lastTime;
if (priority > 5
|| (priority == 5 && lastTime != T)
|| (priority == 4 && lastTime < T - 1)
) ans++;
}
System.out.println(ans);
}
試題H
題解
? 本題可以使用使用并查集可以快速的得到需要修改的數值，
? 首先對并查集初始化，然后依次讀入數字 a，
? 利用 visited 陣列判斷該數字 a 是否使用過：若使用過，則利用并查集尋找數字 a 的最大祖先，最大祖先加一即為需要修改的值，若未使用過，則不需要改動，
? 由此可知，我們的并查集需要單向從小到大，要注意路徑壓縮，
代碼
private static int[] parent = new int[100005];
private static boolean[] visited = new boolean[100005];
public static int find(int x) {
if (x != parent[x])
parent[x] = find(parent[x]); // 路徑壓縮
return parent[x];
}
public static void questionH() {
// 并查集初始化
for (int i = 1; i < parent.length; i++)
parent[i] = i;
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
while (N-- > 0) {
int a = sc.nextInt();
a = visited[a] ? find(a) + 1 : a;
visited[a] = true;
if (a != 1 && visited[a - 1])
parent[a - 1] = a;
if (visited[a + 1])
parent[a] = a + 1;
System.out.print(a + " ");
}
}
試題I
題解
? 本題為狀態壓縮動態規劃，
? 因為資料量小，可以使用二進制中的一位表示某袋是否含有糖果，如某一袋糖果為[2 , 3, 5] 可用二進制表示為 0010 0110 （低位在右，高位在左），
? 首先定義 dp 陣列的含義為 dp[j] 為狀態 j 的糖果組合所需要的最小袋數，
? base case 為 dp[0] = 0
? 狀態轉移方程為 dp[j | candies[i]] = Math.min(dp[j | candies[i]], dp[j] + 1)，
代碼
public static void questionI() {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int M = sc.nextInt();
int K = sc.nextInt();
int[] candies = new int[N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < K; j++) {
int candy = sc.nextInt();
candies[i] |= 1 << candy - 1;
}
}
int MAXN = 105;
int[] dp = new int[1 << M];
Arrays.fill(dp, MAXN);
dp[0] = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < 1 << M; j++) {
if (dp[j] > MAXN)
continue;
dp[j | candies[i]] = Math.min(dp[j | candies[i]], dp[j] + 1);
}
}
if (dp[(1 << M) - 1] < MAXN)
System.out.println(dp[(1 << M) - 1]);
else
System.out.println(-1);
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/257669.html
標籤：其他