藍橋杯 2020年省賽真題 10月第二場 (Java 大學B組)

我是C組的，不過對比一下題目錄，大致上也只有三兩題的不同

就程序而言我覺得我是爆炸的，當然，就結果而言也是

先掛，自倍訓

#A 門牌制作

本題總分：5 分

問題描述

小藍要為一條街的住戶制作門牌號，
這條街一共有 2020 位住戶，門牌號從 1 到 2020 編號，
小藍制作門牌的方法是先制作 0 到 9 這幾個數字字符，最后根據需要將字
符粘貼到門牌上，例如門牌 1017 需要依次粘貼字符 1、0、1、7，即需要 1 個
字符 0，2 個字符 1，1 個字符 7，
請問要制作所有的 1 到 2020 號門牌，總共需要多少個字符 2？

答案提交

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

624

calcCode：

public class Test {

    public static void main(String[] args) {
        int cnt = 0;
        for (int i = 1, n = 1; i <= 2020; n = ++i)
            do if (n % 10 == 2) cnt++;
            while((n /= 10) > 0);
        System.out.print(cnt);
    }
}

回看過來，這題也太幸福了8

#B 尋找 2020

本題總分：5 分

問題描述

小藍有一個數字矩陣，里面只包含數字 0 和 2，小藍很喜歡 2020，他想找
到這個數字矩陣中有多少個 2020 ，
小藍只關注三種構成 2020 的方式：

• 同一行里面連續四個字符從左到右構成 2020，
• 同一列里面連續四個字符從上到下構成 2020，
• 在一條從左上到右下的斜線上連續四個字符，從左上到右下構成 2020，

例如，對于下面的矩陣：

220000
000000
002202
000000
000022
002020

一共有 5 個 2020，其中 1 個是在同一行里的，1 個是在同一列里的，3 個
是斜線上的，
小藍的矩陣比上面的矩陣要大，由于太大了，他只好將這個矩陣放在了一
個檔案里面，在試題目錄下有一個檔案 2020.txt，里面給出了小藍的矩陣，
請幫助小藍確定在他的矩陣中有多少個 2020，

答案提交

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

16520

calcCode：

首先確定一下矩陣大小

BufferedReader in = new BufferedReader(new InputStreamReader(new FileInputStream("2020.txt")));
System.out.println(in.readLine().length());

動手

import java.io.*;

public class Test {

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(new FileInputStream("2020.txt")));
        int[] ioffset = { 0, 1, 1 };
        int[] joffset = { 1, 0, 1 };
        char[] word = { '2', '0', '2', '0' };
        char[][] map = new char[300][];
        for (int i = 0; i < 300; i++)
            map[i] = in.readLine().toCharArray();
        int cnt = 0;
        for (int n = 0; n < 300; n++)
            for (int m = 0; m < 300; m++)
                for (int k = 0; k < 3; k++) {
                    int temp = 0;
                    for (int i = n, j = m, step = 0; i >= 0 && i < 300 && j >= 0 && j < 300 && step < 4; i += ioffset[k], j += joffset[k], step++)
                        if (map[i][j] == word[step]) temp++;
                    if (temp == 4) cnt++;
                }
        System.out.print(cnt);
    }
}

#C 蛇形填數

本題總分：10 分

問題描述

如下圖所示，小明用從 1 開始的正整數“蛇形”填充無限大的矩陣，

1 2 6 7 15 ...
3 5 8 14 ...
4 9 13 ...
10 12 ...
11 ...
...

容易看出矩陣第二行第二列中的數是 5，請你計算矩陣中第 20 行第 20 列
的數是多少？

答案提交

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

761

calcCode：

public class Test {

    public static void main(String[] args) {
        int[][] map = new int[201][201];
        int n = 0;
        for (int k = 1; k <= 200; k++)
            for (int i = 1; i <= k; i++)
                    map[i][k - i + 1] = ++n;
        System.out.print(map[20][20]);
    }
}

憑啥啊，B組比C組簡單這么多

螞蟻競走十年了，小明已經跑了二十年了

#D 七段碼

本題總分：10 分

問題描述

小藍要用七段碼數碼管來表示一種特殊的文字，

上圖給出了七段碼數碼管的一個圖示，數碼管中一共有 7 段可以發光的二
極管，分別標記為 a, b, c, d, e, f, g，
小藍要選擇一部分二極管（至少要有一個）發光來表達字符，在設計字符
的表達時，要求所有發光的二極管是連成一片的，
例如：b 發光，其他二極管不發光可以用來表達一種字符，
例如：c 發光，其他二極管不發光可以用來表達一種字符，這種方案與上
一行的方案可以用來表示不同的字符，盡管看上去比較相似，
例如：a, b, c, d, e 發光，f, g 不發光可以用來表達一種字符，
例如：b, f 發光，其他二極管不發光則不能用來表達一種字符，因為發光
的二極管沒有連成一片，
請問，小藍可以用七段碼數碼管表達多少種不同的字符？

答案提交

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

80

calcCode：

import java.util.Arrays;

public class Test {

    static int cnt;
    static boolean[] select, marked, graph[];

    public static void main(String[] args) {
        // 0: a, 1: b, 2: c, 3: d, 4: e, 5: f, 6: g
        select = new boolean[7];
        marked = new boolean[7];
        graph = new boolean[7][7];
        graph[0][1] = graph[1][0] = true;
        graph[0][5] = graph[5][0] = true;
        graph[1][6] = graph[6][1] = true;
        graph[1][2] = graph[2][1] = true;
        graph[2][6] = graph[6][2] = true;
        graph[2][3] = graph[3][2] = true;
        graph[3][4] = graph[4][3] = true;
        graph[4][5] = graph[5][4] = true;
        graph[4][6] = graph[6][4] = true;
        graph[5][6] = graph[6][5] = true;
        dfs(0, 0);
        System.out.print(cnt);
    }

    static void dfs(int d, int len) {
        if (d == 7) {
            if (len == 0) return;
            int v = 0;
            while (!select[v]) v++;
            Arrays.fill(marked, false);
            if (findPath(v) == len) cnt++;
        } else {
            select[d] = true;
            dfs(d + 1, len + 1);
            select[d] = false;
            dfs(d + 1, len);
        }
    }

    static int findPath(int v) {
        marked[v] = true;
        int len = 1;
        for (int w = 0; w < 7; w++) {
            if (!select[w] || marked[w] || !graph[v][w]) continue;
            len += findPath(w);
        }
        return len;
    }
}

因為這個圖存在環，所以不能正常回溯，但全排列下來也只有 127 種組合，索性就不回溯了

#E 排序

本題總分：15 分

問題描述

小藍最近學習了一些排序演算法，其中冒泡排序讓他印象深刻，
在冒泡排序中，每次只能交換相鄰的兩個元素，
小藍發現，如果對一個字串中的字符排序，只允許交換相鄰的兩個字符，
則在所有可能的排序方案中，冒泡排序的總交換次數是最少的，
例如，對于字串 lan 排序，只需要 1 次交換，對于字串 qiao 排序，
總共需要 4 次交換，
小藍找到了很多字串試圖排序，他恰巧碰到一個字串，需要 100 次交
換，可是他忘了吧這個字串記下來，現在找不到了，
請幫助小藍找一個只包含小寫英文字母且沒有字母重復出現的字串，對
該串的字符排序，正好需要 100 次交換，如果可能找到多個，請告訴小藍最短的那個，如果最短的仍然有多個，請告訴小藍字典序最小的那個，請注意字串中不可以包含相同的字符，

答案提交

這是一道結果填空的題，你只需要算出結果后提交即可，本題的結果為一
個只包含小寫英文字母的字串，在提交答案時只填寫這個字串，填寫多余的內容將無法得分，

NULL

首先確定范圍，冒泡交換的次數是根據逆序數來看的，要交換100次的話，元素個數必須大于等于15個，然后列舉就行，先吃個飯

calcCode：

import java.util.Arrays;

public class Test {

    static final int len = 15;

    public static void main(String[] args) {
        char[] a = new char[len];
        for (int i = 0; i < len; i++)
            a[i] = (char)('a' + i);
        do {
            int cnt = 0;
            for (int i = 0; i < len; i++)
                for (int j = 0; j < i; j++)
                    if (a[i] < a[j]) cnt++;
            if (cnt == 100) {
                System.out.println(a);
                return;
            }
        } while (next(a));
    }

    static boolean next(char[] a) {
        int i = a.length - 2;
        while (i >= 0 && a[i] > a[i + 1]) i--;
        if (i < 0) return false;
        int j = i + 1;
        char t = a[i];
        while (j < a.length && a[j] > t) j++;
        a[i] = a[j - 1];
        a[j - 1] = t;
        Arrays.sort(a, i + 1, a.length);
        return true;
    }
}

寫出來后發現時間復雜度直接拉滿

先放放

#F 成績分析

時間限制: 1.0s 記憶體限制: 512.0MB 本題總分：15 分

問題描述

小藍給學生們組織了一場考試，卷面總分為 100 分，每個學生的得分都是
一個 0 到 100 的整數，
請計算這次考試的最高分、最低分和平均分，

輸入格式

輸入的第一行包含一個整數 n，表示考試人數，
接下來 n 行，每行包含一個 0 至 100 的整數，表示一個學生的得分，

輸出格式

輸出三行，
第一行包含一個整數，表示最高分，
第二行包含一個整數，表示最低分，
第三行包含一個實數，四舍五入保留正好兩位小數，表示平均分，

測驗樣例₁

Input：
7
80
92
56
74
88
99
10

Output：
99
10
71.29

評測用例規模與約定

對于 50% 的評測用例，1 ≤ n ≤ 100，
對于所有評測用例，1 ≤ n ≤ 10000，

code：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int)in.nval, sum = 0, max = 0, min = 128;
        for (int i = 0, t; i < n; i++) {
            in.nextToken();
            sum += t = (int)in.nval;
            if (t > max) max = t;
            if (t < min) min = t;
        }
        System.out.printf("%d\n%d\n%.2f", max, min, (double)sum / n);
    }
}

#G 單詞分析

時間限制: 1.0s 記憶體限制: 512.0MB 本題總分：20 分

問題描述

小藍正在學習一門神奇的語言，這門語言中的單詞都是由小寫英文字母組
成，有些單詞很長，遠遠超過正常英文單詞的長度，小藍學了很長時間也記不
住一些單詞，他準備不再完全記憶這些單詞，而是根據單詞中哪個字母出現得
最多來分辨單詞，
現在，請你幫助小藍，給了一個單詞后，幫助他找到出現最多的字母和這
個字母出現的次數，

輸入格式

輸入一行包含一個單詞，單詞只由小寫英文字母組成，

輸出格式

輸出兩行，第一行包含一個英文字母，表示單詞中出現得最多的字母是哪
個，如果有多個字母出現的次數相等，輸出字典序最小的那個，
第二行包含一個整數，表示出現得最多的那個字母在單詞中出現的次數，

測驗樣例₁

Input：
lanqiao

Output：
a
2

測驗樣例₂

Input：
longlonglongistoolong

Output：
o
6

評測用例規模與約定

對于所有的評測用例，輸入的單詞長度不超過 1000，

code：

import java.io.IOException;

public class Main {

    public static void main(String[] args) throws IOException {
        byte[] buff = new byte[1024];
        int l = System.in.read(buff), max = 0;
        int[] cnt = new int[128];
        for (int i = 0; i < l; i++)
            cnt[buff[i]]++;
        for (char i = 'z'; i >= 'a'; i--)
            if (cnt[i] >= max) {
                max = cnt[i];
                l = i;
            }
        System.out.println((char)l + "\n" + max);
    }
}

#H 數字三角形

時間限制: 1.0s 記憶體限制: 512.0MB 本題總分：20 分

問題描述

上圖給出了一個數字三角形，從三角形的頂部到底部有很多條不同的路徑，
對于每條路徑，把路徑上面的數加起來可以得到一個和，你的任務就是找到最大的和，
路徑上的每一步只能從一個數走到下一層和它最近的左邊的那個數或者右邊的那個數，此外，向左下走的次數與向右下走的次數相差不能超過 1，

輸入格式

輸入的第一行包含一個整數 N (1 < N ≤ 100)，表示三角形的行數，下面的
N 行給出數字三角形，數字三角形上的數都是 0 至 100 之間的整數

輸出格式

輸出一個整數，表示答案，

測驗樣例₁

Input：
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

Output：
27

code：

#I 子串分值和

時間限制: 1.0s 記憶體限制: 512.0MB 本題總分：25 分

問題描述

對于一個字串 S，我們定義 S 的分值 f(S ) 為 S 中出現的不同的字符個
數，例如 f(”aba”) = 2，f(”abc”) = 3, f(”aaa”) = 1，
現在給定一個字串 S [0…n ? 1]（長度為 n），請你計算對于所有 S 的非空
子串 S [i… j](0 ≤ i ≤ j < n)，f(S [i… j]) 的和是多少，

輸入格式

輸入一行包含一個由小寫字母組成的字串 S，

輸出格式

輸出一個整數表示答案，

測驗樣例₁

Input：
ababc

Output：
28

Explanation：
子串 f值
a     1
ab    2
aba   2
abab  2
ababc 3
b     1
ba    2
bab   2
babc  3
a     1
ab    2
abc   3
b     1
bc    2
c     1

評測用例規模與約定

對于 20% 的評測用例，1 ≤ n ≤ 10；
對于 40% 的評測用例，1 ≤ n ≤ 100；
對于 50% 的評測用例，1 ≤ n ≤ 1000；
對于 60% 的評測用例，1 ≤ n ≤ 10000；
對于所有評測用例，1 ≤ n ≤ 100000，

code：

#J 裝飾珠

時間限制: 1.0s 記憶體限制: 512.0MB 本題總分：25 分

問題描述

在怪物獵人這一款游戲中，玩家可以通過給裝備鑲嵌不同的裝飾珠來獲取
相應的技能，以提升自己的戰斗能力，
已知獵人身上一共有 6 6 6 件裝備，每件裝備可能有若干個裝飾孔，每個裝飾
孔有各自的等級，可以鑲嵌一顆小于等于自身等級的裝飾珠 (也可以選擇不鑲
嵌)，
裝飾珠有 M M M 種，編號 1 1 1 至 M M M，分別對應 M M M 種技能，第 i i i 種裝飾珠的等級
為 L i L_{i} Li?，只能鑲嵌在等級大于等于 L i L_i Li? 的裝飾孔中，
對第 i i i 種技能來說，當裝備相應技能的裝飾珠數量達到 K i K_{i} Ki? 個時，會產生
W i ( K i ) W_{i}(K_{i}) Wi?(Ki?) 的價值，鑲嵌同類技能的數量越多，產生的價值越大，即 W i ( K i ? 1 ) < W i ( K i ) W_{i}(K_{i} - 1) < W_{i}(K_{i}) Wi?(Ki??1)<Wi?(Ki?)，但每個技能都有上限 P i ( 1 ≤ P i ≤ 7 ) P_{i}(1 ≤ P_{i} ≤ 7) Pi?(1≤Pi?≤7)，當裝備的珠子數量超過 P i P_i Pi? 時，只
會產生 W i ( P i ) W_{i}(P_{i}) Wi?(Pi?) 的價值，
對于給定的裝備和裝飾珠資料，求解如何鑲嵌裝飾珠，使得 6 件裝備能得
到的總價值達到最大，

輸入格式

輸入的第 1 1 1 至 6 6 6 行，包含 6 6 6 件裝備的描述，其中第 i i i 的第一個整數 N i N_{i} Ni? 表示
第 i i i 件裝備的裝飾孔數量，后面緊接著 N i N_{i} Ni? 個整數，分別表示該裝備上每個裝飾
孔的等級 L ( 1 ≤ L ≤ 4 ) L(1 ≤ L ≤ 4) L(1≤L≤4)，
第 7 7 7 行包含一個正整數 M M M，表示裝飾珠 (技能) 種類數量，
第 8 8 8 至 M + 7 M + 7 M+7 行，每行描述一種裝飾珠 (技能) 的情況，每行的前兩個整數
L j ( 1 ≤ L j ≤ 4 ) L_{j}(1 ≤ L_{j} ≤ 4) Lj?(1≤Lj?≤4) 和 P j ( 1 ≤ P i ≤ 7 ) P_{j}(1 ≤ P_{i} ≤ 7) Pj?(1≤Pi?≤7) 分別表示第 j j j 種裝飾珠的等級和上限，接下來
P j P_j Pj? 個整數，其中第 k k k 個數表示裝備該中裝飾珠數量為 k k k 時的價值 W j ( k ) W_{j}(k) Wj?(k)，

輸出格式

輸出一行包含一個整數，表示能夠得到的最大價值，

測驗樣例₁

Input：
1 1
2 1 2
1 1
2 2 2
1 1
1 3
3
1 5 1 2 3 5 8
2 4 2 4 8 15
3 2 5 10

Output：
20

Explanation：
按照如下方式鑲嵌珠子得到最大價值 18，括號內表示鑲嵌的裝飾珠的種類編號：
1: (1)
2: (1) (2)
3: (1)
4: (2) (2)
5: (1)
6: (2)
4 顆技能 1 裝飾珠，4 顆技能 2 裝飾珠 W1(4) + W2(4) = 5 + 15 = 20，

評測用例規模與約定

對于 30% 的評測用例，1 ≤ Ni ≤ 10, 1 ≤ M ≤ 20, 1 ≤ Wj(k) ≤ 500；
對于所有評測用例，1 ≤ Ni ≤ 50, 1 ≤ M ≤ 10000, 1 ≤ Wj(k) ≤ 10000，

code：