A. ASC（5分）
已知大寫字母 A 的 ASCII 碼為 65，請問大寫字母 L 的 ASCII 碼是多少？
答案：76
代碼
點擊就送，直接輸出字母對應的 int 值即可，
public class Main {
public static void main(String[] args) {
// 76
System.out.println((int)'A' + " " + (int)'L');
}
}
B. 卡片（5分）
小藍有很多數字卡片，每張卡片上都是數字 0 到 9，
小藍準備用這些卡片來拼一些數，他想從 1 開始拼出正整數，每拼一個， 就保存起來，卡片就不能用來拼其它數了，
小藍想知道自己能從 1 拼到多少，
例如，當小藍有 30 張卡片，其中 0 到 9 各 3 張，則小藍可以拼出 1 到 10， 但是拼 11 時卡片 1 已經只有一張了，不夠拼出 11，
現在小藍手里有 0 到 9 的卡片各 2021 張，共 20210 張，請問小藍可以從 1 拼到多少？
答案：3181
代碼
哭了😭，這題白給，開始時讀了好幾遍讀不懂，放著最后一刻鐘再看，突然就看懂了:
當時還在想不是 11 = 8 + 3 or 9 + 2 嗎，怎么和 1 杠上了呢；
后面才發現使用單個數字作為數位來拼，換句話說，11 是用兩個 1 拼出來的…
也就是說這一堆卡片消耗到哪個數字時不能拼出來，我們就輸出這個數字的前一個數字！！！
題目給的例子是要我們輸出 10，好家伙，當時狀態也不太好了，腦子里滿是 11 ，程式跑出了 11 后改成 2021 ，得到結果 3182，我直接就交了😭😭😭！！！
思路是哈希，
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] hash = new int[10];
Arrays.fill(hash, 2021);
long num = 0;
boolean flag;
do {
num++;
flag = true;
char[] str = String.valueOf(num).toCharArray();
for (char bit : str) {
if (hash[bit - '0'] > 0) {
hash[bit - '0']--;
} else {
flag = false;
break;
}
}
} while (flag);
System.out.println(num - 1); // 3181 我吐了，大家一定要仔細讀題
}
}
C. 直線（10分）
在平面直角坐標系中，兩點可以確定一條直線，如果有多點在一條直線上， 那么這些點中任意兩點確定的直線是同一條，
給定平面上 2 × 3 個整點 {(x, y)|0 ≤ x < 2, 0 ≤ y < 3, x ∈ Z, y ∈ Z}，即橫坐標 是 0 到 1 (包含 0 和 1) 之間的整數、縱坐標是 0 到 2 (包含 0 和 2) 之間的整數 的點，這些點一共確定了 11 條不同的直線，
給定平面上 20 × 21 個整點 {(x, y)|0 ≤ x < 20, 0 ≤ y < 21, x ∈ Z, y ∈ Z}，即橫 坐標是 0 到 19 (包含 0 和 19) 之間的整數、縱坐標是 0 到 20 (包含 0 和 20) 之 間的整數的點，請問這些點一共確定了多少條不同的直線，
答案：
41300
4130040239
40239正解是 40257，
代碼
這道題我…拿到手就會做！
不太想做其實… 感覺自己寫的精度炸裂
思路是先獲得所有的點，再根據兩兩不同的點去計算直線，用的斜截式 y = kx + b，
然后得到所有的 k 和 b，并去重，問題就出在了 b 是浮點數，精度警告！
其實為了保險，可以把 b 也像 k 當最簡分數算出來的，哎，懶，
過不過看運氣吧~😪
======= 21 - 04 - 19 update =======
Guess what？這一題我也白給啦！！！好耶！！！
果然是精度爆炸，我就不該玩 double…
算了，這就叫 no zuo no die（攤手
import java.util.List;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;
public class Main {
static Set<String> ans = new HashSet<>();
public static int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
// 最初的 b 用 double 記錄 —— 精度爆炸
// public static void getKB(int a, int b) {
// int x1 = a / 100, x2 = b / 100;
// int y1 = a % 100, y2 = b % 100;
//
// int up = y1 - y2, down = x1 - x2;
// int div = gcd(up, down);
// String K = (up / div) + " " + (down / div);
// double B = x1 * 1.0f;
// if (down != 0) {
// double k = up * 1.0 / down;
// B = y1 - k * x1;
// }
// ans.add(K + " " + B);
// }
// 好家伙，又寫錯一次！細心啊細心啊細心啊細心啊細心啊！！！
// public static void getKB(int a, int b) {
// int x1 = a / 100, x2 = b / 100;
// int y1 = a % 100, y2 = b % 100;
//
// // 計算 k 的最簡分數
// int up = y1 - y2, down = x1 - x2;
// int div_k = gcd(up, down);
// String K = (up / div_k) + " " + (down / div_k);
//
// // 計算 kx 和 y 的分子
// int up_kx = up * x1, up_y = y1 * down;
//
// // 計算 b = y - kx 的最簡分數
// int up_b = up_y - up_kx;
// int div_b = gcd(up_b, down);
// // 除零處理
// String B = div_b == 0 ? up_b + "/0 " + down + "/0" :
// (up_b / div_b) + " " + (down / div_b);
// ans.add(K + " " + B);
// }
// String yyds！！！ 不能再錯了吧？
public static void getKB(int a, int b) {
int x1 = a / 100, x2 = b / 100;
int y1 = a % 100, y2 = b % 100;
// 計算 k 的最簡分數
int up = y1 - y2, down = x1 - x2;
int div_k = gcd(up, down);
String K = (up / div_k) + " " + (down / div_k);
// 特判 k 不存在，即 down = 0 的情況
// 此時方程為 x = x1 or x2;
if (down == 0) {
ans.add("x = " + x1);
return;
}
// 代入點 (x1, y1) 來計算 kx 和 y 的分數
// 因為分母都是 down，所以只求分子就好
int up_kx = up * x1, up_y = y1 * down;
// 計算 b = y - kx 的最簡分數
int up_b = up_y - up_kx;
int div_b = gcd(up_b, down);
String B = (up_b / div_b) + " " + (down / div_b);
// 加入答案
ans.add(K + " " + B);
}
public static void main(String[] args) {
Set<Integer> set = new HashSet<>();
int x = 19, y = 20;
for (int i = 0; i <= x; i++) {
for (int j = 0; j <= y; j++) {
set.add(i * 100 + j);
// System.out.println(i * 100 + j);
}
}
List<Integer> arr = new ArrayList<>(set);
int len = arr.size();
// System.out.println(len);
for (int i = 0; i < len; i++) {
int a = arr.get(i);
for (int j = i + 1; j < len; j++) {
int b = arr.get(j);
getKB(a, b);
}
}
// 41300? No 40239? No 40257? Yes!
// 好家伙，精度爆炸答案還變多了？
System.out.println("ans = " + ans.size());
}
}
D. 貨物擺放（10分）
小藍有一個超大的倉庫，可以擺放很多貨物，
現在，小藍有 n 箱貨物要擺放在倉庫，每箱貨物都是規則的正方體，小藍 規定了長、寬、高三個互相垂直的方向，每箱貨物的邊都必須嚴格平行于長、 寬、高， 小藍希望所有的貨物最終擺成一個大的立方體，即在長、寬、高的方向上 分別堆 L、W、H 的貨物，滿足 n = L × W × H，
給定 n，請問有多少種堆放貨物的方案滿足要求， 例如，當 n = 4 時，有以下 6 種方案：1×1×4、1×2×2、1×4×1、2×1×2、 2 × 2 × 1、4 × 1 × 1，
請問，當 n = 2021041820210418 （注意有 16 位數字）時，總共有多少種方案？
答案：28
28正解是 2430，
代碼
好家伙，最近看了回數論，還真就全用上了，gcd、lcm、因數…
具體思路就是求出這個大數的所有因數，然后隨便取三個看能不能得到它，妥妥的全排列問題，
這么大的數只能用 long 存了，求因子要 sqrt，不然跑億年~
======= 21 - 04 - 19 update =======
兄弟們，我炸了！昨晚睡前復盤代碼時，突然發現我在爆搜前沒有排序，導致 DFS 里面的剪枝會漏答案…
我吐了呀，早知道不剪枝了！😭
哎，大家一定要細心細心再細心！！！有 128 個因子卻只有這么點答案，我居然沒有懷疑是不是哪里錯了…
最近狀態是真的迷…
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class Main {
static int ans = 0;
static long num = 2021041820210418L;
private static void dfs(List<Long> list, Long[] arr, long prod, int cnt) {
if (cnt == 3) {
if (prod == num) {
for (long x : list) {
System.out.print(x + " ");
}
System.out.println();
ans++;
}
return;
}
for (int i = 0; i < arr.length; i++) {
long next = prod * arr[i];
if (next > num) {
break;
}
list.add(arr[i]);
dfs(list, arr, next, cnt + 1);
list.remove(list.size() - 1);
}
}
public static void main(String[] args) {
long end = (long)Math.sqrt(num);
Set<Long> div = new HashSet<>();
for (long i = 1; i <= end; i++) {
if (num % i == 0) {
div.add(num / i);
div.add(i);
}
}
// System.out.println(div.size()); -> 128;
List<Long> list = new ArrayList<>();
Long[] arr = div.toArray(new Long[0]);
// ==== 21/04/19 update 排序預處理 ====
Arrays.sort(arr);
// ==== 21/04/19 update 排序預處理 ====
for (long x : arr) {
list.add(x);
dfs(list, arr, x, 1);
list.remove(list.size() - 1);
}
System.out.println("ans = " + ans); // 28? No 2430? Yes
}
}
E. 路徑（15分）
小藍學習了最短路徑之后特別高興，他定義了一個特別的圖，希望找到圖 中的最短路徑，
小藍的圖由 2021 個結點組成，依次編號 1 至 2021，
對于兩個不同的結點 a, b，如果 a 和 b 的差的絕對值大于 21，則兩個結點 之間沒有邊相連；如果 a 和 b 的差的絕對值小于等于 21，則兩個點之間有一條 長度為 a 和 b 的最小公倍數的無向邊相連，
例如：結點 1 和結點 23 之間沒有邊相連；結點 3 和結點 24 之間有一條無 向邊，長度為 24；結點 15 和結點 25 之間有一條無向邊，長度為 75，
請計算，結點 1 和結點 2021 之間的最短路徑長度是多少，
答案：10266837
代碼
好家伙，我直接好家伙，最近一直在肝最短路，真就學到哪考到哪唄，最短路徑這不來一手 Floyd？😏
當然，如果這是程式題，那還是 Dijkstra 吧，不然 T 到吐~
======= 21 - 04 - 19 update =======
作為「最難的」填空題不該這么沒排面，所以再加上 Dijkstra 和 SPFA 兩種解法，就當復習了~
看這些方法的代碼量就知道填空題該選誰了吧~ 🤣
Floyd
public class Main {
static int[][] graph = new int[2050][2050];
static final int INF = 0x3f3f3f3f;
private static void floyd() {
for (int k = 1; k <= 2021; k++) {
for (int i = 1; i <= 2021; i++) {
for (int j = 1; j <= 2021; j++) {
if (i != j && graph[i][j] > graph[i][k] + graph[k][j]) {
graph[i][j] = graph[i][k] + graph[k][j];
}
}
}
}
}
private static int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
public static void main(String[] args) {
for (int i = 1; i <= 2021; i++) {
for (int j = 1; j <= 2021; j++) {
graph[i][j] = INF;
}
}
for (int i = 1; i <= 2021; i++) {
int st = Math.max(i - 21, 1);
for (int j = st; j <= i; j++) {
int div = gcd(j, i);
int lcm = i * j / div;
graph[i][j] = lcm;
graph[j][i] = lcm;
}
}
floyd();
System.out.println(graph[1][2021]); // 10266837
}
}
Dijkstra
import java.util.*;
public class Main {
static class Edge {
int to, length;
Edge(int _to, int _length) {
to = _to;
length = _length;
}
}
static List<Edge>[] graph;
static final int INF = 0x3f3f3f3f;
private static int dijkstra(int st, int ed) {
// 新建小根堆
PriorityQueue<Edge> pq = new PriorityQueue<>((a, b) ->
Integer.compare(a.length, b.length));
boolean[] vis = new boolean[2050];
int[] dist = new int[2050];
Arrays.fill(dist, INF);
dist[st] = 0;
// to 為點的編號，length 為當前路徑長度
pq.add(new Edge(st, dist[st]));
while (!pq.isEmpty()) {
int from = pq.poll().to;
if (vis[from]) {
continue;
}
vis[from] = true;
// 松弛操作
for (Edge next : graph[from]) {
int to = next.to, len = next.length;
if (dist[to] > dist[from] + len) {
dist[to] = dist[from] + len;
pq.add(new Edge(to, dist[to]));
}
}
}
return dist[ed];
}
private static int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
public static void main(String[] args) {
graph = new List[2050];
// 構建鄰接表
for (int i = 1; i <= 2021; i++) {
int st = Math.max(i - 21, 1);
for (int j = st; j <= i; j++) {
int div = gcd(j, i);
int lcm = i * j / div;
if (graph[i] == null) {
graph[i] = new ArrayList<>();
}
if (graph[j] == null) {
graph[j] = new ArrayList<>();
}
graph[i].add(new Edge(j, lcm));
graph[j].add(new Edge(i, lcm));
}
}
System.out.println(dijkstra(1, 2021)); // 10266837
}
}
SPFA
import java.util.*;
public class Main {
static class Edge {
int to, length;
Edge(int _to, int _length) {
to = _to;
length = _length;
}
}
static List<Edge>[] graph;
static final int INF = 0x3f3f3f3f;
// SPFA 本質是 Bellman-Ford 演算法的佇列優化
private static int SPFA(int st, int ed) {
// 標記那些結點可能會引起松弛操作
boolean[] inq = new boolean[2050];
int[] dist = new int[2050];
Arrays.fill(dist, INF);
Queue<Integer> q = new LinkedList<>();
q.offer(st);
dist[st] = 0;
inq[st] = true;
while (!q.isEmpty()) {
int cur = q.poll();
inq[cur] = false;
// 松弛操作
for (Edge next : graph[cur]) {
int to = next.to, len = next.length;
if (dist[to] > dist[cur] + len) {
dist[to] = dist[cur] + len;
if (!inq[to]) {
inq[to] = true;
q.offer(to);
}
}
}
}
return dist[ed];
}
private static int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
public static void main(String[] args) {
graph = new List[2050];
// 構建鄰接表
for (int i = 1; i <= 2021; i++) {
int st = Math.max(i - 21, 1);
for (int j = st; j <= i; j++) {
int div = gcd(j, i);
int lcm = i * j / div;
if (graph[i] == null) {
graph[i] = new ArrayList<>();
}
if (graph[j] == null) {
graph[j] = new ArrayList<>();
}
graph[i].add(new Edge(j, lcm));
graph[j].add(new Edge(i, lcm));
}
}
System.out.println(SPFA(1, 2021)); // 10266837
}
}
F. 時間限制（15分）
小藍要和朋友合作開發一個時間顯示的網站，在服務器上，朋友已經獲取 了當前的時間，用一個整數表示，值為從 1970 年 1 月 1 日 00:00:00 到當前時 刻經過的毫秒數，
現在，小藍要在客戶端顯示出這個時間，小藍不用顯示出年月日，只需要 顯示出時分秒即可，毫秒也不用顯示，直接舍去即可，
給定一個用整數表示的時間，請將這個時間對應的時分秒輸出，
輸入格式
輸入一行包含一個整數，表示時間，
輸出格式
輸出時分秒表示的當前時間，格式形如 HH:MM:SS，其中 HH 表示時，值 為 0 到 23，MM 表示分，值為 0 到 59，SS 表示秒，值為 0 到 59，時、分、秒 不足兩位時補前導 0，
樣例輸入 1
46800999
樣例輸出 1
13:00:00
樣例輸入 2
1618708103123
樣例輸出 2
01:08:23
評測用例規模與約定
對于所有評測用例，給定的時間為不超過 1 0 18 10^{18} 1018 的正整數，
代碼
有多少人死在了 1s == 1000ms 上…？
思路是模擬，注意開 long，
import java.io.BufferedInputStream;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(new BufferedInputStream(System.in));
long ms = in.nextLong();
long hour_div = 60 * 60 * 1000;
long min_div = 60 * 1000;
long hour = (ms / hour_div) % 24;
ms %= hour_div;
long min = (ms / min_div) % 60;
ms %= min_div;
long sec = ms / 1000;
System.out.printf("%02d:%02d:%02d\n", hour, min, sec);
in.close();
}
}
G. 最少砝碼（20分）
思路
貪心，力扣有道類似的題 330. 按要求補齊陣列 ，嗯就在這基礎上多了個條件，
啊好，我不會了！
H. 楊輝三角形（20分）
思路
只想到模擬 DP，暴力了一波，
大佬們都說使用組合算的，我不太懂…😢
I. 雙向排序（25分）
思路
找不出什么好規律來，也懶得去推了，暴力騙分不香嗎…
僅供參考！不是正解！！！
import java.io.BufferedInputStream;
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(new BufferedInputStream(System.in));
int n = in.nextInt(), m = in.nextInt();
Integer[] arr = new Integer[n + 1];
for (int i = 1; i <= n; i++) {
arr[i] = i;
}
for (int i = 0; i < m; i++) {
int p = in.nextInt();
int split = in.nextInt();
if (p == 0) {
Arrays.sort(arr, 1, split + 1, (a, b) -> Integer.compare(b, a));
} else {
Arrays.sort(arr, split, n + 1);
}
}
for (int i = 1; i <= n; i++) {
if (i > 1) {
System.out.print(" ");
}
System.out.print(arr[i]);
}
in.close();
}
}
J. 括號序列（25分）
思路
是它，是它，是它，就是它！我們的宿敵大 DP！
推不出狀態轉移方程😟，暴力 DFS 只能過個位數的用例🤣
害，不放了，太 SB 了，
總結
藍橋它變了，變得不簡單了！（還不是自己太菜了
可能是最后一次玩藍橋了（又菜又愛玩
給大家的建議就是，好好刷題，多向大佬學習，知識要成體系！
然后干就完了，奧里給！
哎，這一次做的好差，明明填空題可以拿滿分的，多撈哦😞
果然考試就應該提前調整好狀態，沉著冷靜，把自己應有的實力發揮出來就好了~害
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/278183.html
標籤：其他
上一篇：第十二屆藍橋杯 2021年4月 省賽 第一場 C/C++ B組 題解
下一篇：MySQL 索引和事務