藍橋杯 2021年省賽真題 (Java 大學B組）

#A ASC
#B 卡片
- 樸素解法
- 彎道超車
#C 直線
- 直線方程集合
- 分式消除誤差
- 平面幾何
#D 貨物擺放
- 暴力搜索
- 縮放質因子
#E 路徑
- 搜索
- - 深度優先搜索
  - 記憶化搜索
  - 枝剪廣搜
  - 雙向搜索
- 單源最短路徑
- - Dijkstra
  - Floyd
  - A*
- 動態規劃
#F 時間顯示
- Java Win
- 不依賴 API 的實作
#G 最少砝碼
- 變種三進制
#H 楊輝三角形
- 類比單調數列
#I 雙向排序
- 去冗操作
- 填數游戲
- 樹分裂&合并 (未填)
#J 括號序列
- 不會

_Placeholder

#A ASC

本題總分：5 分

問題描述

??已知大寫字母 A A A 的 A S C I I ASCII ASCII 碼為 65 65 65，請問大寫字母 L L L 的 A S C I I ASCII ASCII 碼是多少？

答案提交

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

76

calcCode：

public class Test {

    public static void main(String[] args) { new Test().run(); }

    void run() {
        // System.out.println(65 + 'L' - 'A');
        System.out.println((int)'L');
    }
}

麻煩簽到題寫的認真一點，謝謝，

#B 卡片

本題總分：5 分

問題描述

??小藍有很多數字卡片，每張卡片上都是數字 0 0 0 到 9 9 9，
??小藍準備用這些卡片來拼一些數，他想從 1 1 1 開始拼出正整數，每拼一個，就保存起來，卡片就不能用來拼其它數了，
??小藍想知道自己能從 1 1 1 拼到多少，
??例如，當小藍有 30 30 30 張卡片，其中 0 0 0 到 9 9 9 各 3 3 3 張，則小藍可以拼出 1 1 1 到 10 10 10，但是拼 11 11 11 時卡片 1 1 1 已經只有一張了，不夠拼出 11 11 11，
??現在小藍手里有 0 0 0 到 9 9 9 的卡片各 2021 2021 2021 張，共 20210 20210 20210 張，請問小藍可以從 1 1 1 拼到多少？
??提示：建議使用計算機編程解決問題，

答案提交

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

3181

樸素解法

public class Test {

    public static void main(String[] args) { new Test().run(); }

    void run() { System.out.println(calc(2021)); }

    int calc(int upper) {
        int[] count = new int[10];
        for (int n = 1, k = 1; ; k = ++n)
            do
                if (++count[k % 10] > upper)
                	return n - 1;
            while ((k /= 10) > 0);
    }
}

??沒什么好說的，

彎道超車

??觀察 [ 1 , 9 ] [1,9] [1,9] 這個區間中， [ 0 , 9 ] [0,9] [0,9] 的出現情況，

??在 [ 1 , 9 ] [1,9] [1,9] 中， 1 1 1 至 9 9 9 各出現 1 1 1 次，

??把觀察的范圍擴大到 [ 1 , 99 ] [1,99] [1,99]，十位的 1 1 1 出現 [ 10 , 19 ] [10,19] [10,19] 共 10 10 10 次，十位的 2 2 2 出現 [ 20 , 29 ] [20,29] [20,29] 共 10 10 10 次， ? \cdots ? ，十位的 9 9 9 出現 [ 90 , 99 ] [90,99] [90,99] 共 10 10 10 次，低位 [ 0 , 9 ] [0,9] [0,9] 重復出現 10 10 10 次， 1 1 1 至 9 9 9 各出現 20 20 20 次， 0 0 0 出現 9 9 9 次，

??將這個觀察范圍繼續擴大，會發現 1 1 1 的使用次數總是不小于 0 0 0 、 2 2 2 至 9 9 9，也就是說統計 0 0 0 、 2 2 2 至 9 9 9 是沒有意義的，

public class Test {

    public static void main(String[] args) { new Test().run(); }

    void run() { System.out.println(calc(2021)); }

    int calc(int upper) {
        int count = 0;
        for (int n = 1, k = 1; ; k = ++n) {
            do
                if (k % 10 == 1) count++;
            while ((k /= 10) > 0);
            if (count >= upper)
                return count == upper ? n : n - 1;
        }
    }
}

#C 直線

本題總分：10 分

問題描述

??在平面直角坐標系中，兩點可以確定一條直線，如果有多點在一條直線上，那么這些點中任意兩點確定的直線是同一條，
??給定平面上 2 × 3 2 × 3 2×3 個整點 { ( x , y ) ∣ 0 ≤ x < 2 , 0 ≤ y < 3 , x ∈ Z , y ∈ Z } \{(x, y)|0 ≤ x < 2, 0 ≤ y < 3, x ∈ Z, y ∈ Z\} {(x,y)∣0≤x<2,0≤y<3,x∈Z,y∈Z}，即橫坐標是 0 0 0 到 1 1 1 (包含 0 0 0 和 1 1 1) 之間的整數、縱坐標是 0 0 0 到 2 2 2 (包含 0 0 0 和 2 2 2) 之間的整數的點，這些點一共確定了 11 11 11 條不同的直線，
??給定平面上 20 × 21 20 × 21 20×21 個整點 { ( x , y ) ∣ 0 ≤ x < 20 , 0 ≤ y < 21 , x ∈ Z , y ∈ Z } \{(x, y)|0 ≤ x < 20, 0 ≤ y < 21, x ∈ Z, y ∈ Z\} {(x,y)∣0≤x<20,0≤y<21,x∈Z,y∈Z}，即橫坐標是 0 0 0 到 19 19 19 (包含 0 0 0 和 19 19 19) 之間的整數、縱坐標是 0 0 0 到 20 20 20 (包含 0 0 0 和 20 20 20) 之間的整數的點，請問這些點一共確定了多少條不同的直線，

答案提交

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

40257

直線方程集合

??一種樸素的想法，是將所有點連接起來，去掉重復的線，然后統計，

??為了方便表示，這里采用斜截式方程 y = k x + b y=kx+b y=kx+b 來表示每一條直線，其中 k k k 為直線斜率， b b b 為直線在 y y y 軸上的截距，并統一不處理斜率不存在的線，將結果加上一個 20 20 20，

??注意！ 這段程式的結果是不準確的，

import java.util.HashSet;
import java.util.Set;

public class Test {

    public static void main(String[] args) { new Test().run(); }

    int X = 20, Y = 21;

    void run() {
        Set<Line> set = new HashSet();
        for (int x1 = 0; x1 < X; x1++)
            for (int y1 = 0; y1 < Y; y1++)
                for (int x2 = x1; x2 < X; x2++)
                    for (double y2 = 0; y2 < Y; y2++)
                        if (x1 != x2){
                            double k = (y2 - y1) / (x2 - x1);
                            double b = -x1 * k + y1;
                            set.add(new Line(k, b));
                        }
        System.out.println(set.size() + X);
    }

    class Line {

        double k, b;

        Line(double b, double k) {
            this.k = k;
            this.b = b;
        }

        @Override
        public boolean equals(Object obj) {
            return k == ((Line)obj).k && b == ((Line)obj).b;
        }

        @Override
        public int hashCode() {
            return (int)k ^ (int)b;
        }
    }
}

分式消除誤差

??斜率在浮點數表示下，精度那是參差不齊，誠然可以將誤差限制在一個范圍內，當絕對差落入當中時，我們就將其視為值相同，

??但是對于這種需要可表示的范圍小的時候，我們可以定義分式來做到無誤差，而不是控制精度，

import java.util.HashSet;
import java.util.Set;

public class Test {

    public static void main(String[] args) { new Test().run(); }

    int X = 20, Y = 21;

    void run() {
        Set<Line> set = new HashSet();
        for (int x1 = 0; x1 < X; x1++)
            for (int y1 = 0; y1 < Y; y1++)
                for (int x2 = x1; x2 < X; x2++)
                    for (int y2 = 0; y2 < Y; y2++)
                        if (x1 != x2){
                            Fraction k = new Fraction(y2 - y1, x2 - x1);
                            Fraction b = new Fraction(y1 * (x2 - x1) - x1 * (y2 - y1),x2 - x1);
                            set.add(new Line(k, b));
                        }
        System.out.println(set.size() + X);
    }

    class Fraction {

        int numerator, denominator;

        Fraction(int numerator, int denominator) {
            int gcd = gcd(numerator, denominator);
            this.denominator = denominator /gcd;
            this.numerator = numerator / gcd;
        }

        int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }

        @Override
        public boolean equals(Object obj) {
            return this.numerator == ((Fraction)obj).numerator && this.denominator == ((Fraction)obj).denominator;
        }
    }

    class Line {

        Fraction k, b;

        Line(Fraction b, Fraction k) {
            this.k = k;
            this.b = b;
        }

        @Override
        public boolean equals(Object obj) {
            return this.k.equals(((Line)obj).k) && this.b.equals(((Line)obj).b);
        }

        @Override
        public int hashCode() {
            return k.denominator;
        }
    }
}

平面幾何

??這是一個平面直角坐標系，原點與 ( 1 , 2 ) (1,2) (1,2) 連成一條線段，

請添加圖片描述
??我們將經過這兩點的直線，以及這條直線經過的點與該點于橫豎軸的垂線標記出來，

??顯然，若直線經過 ( x 1 , y 1 ) (x_{1},y_{1}) (x1?,y1?)、 ( x 2 , y 2 ) (x_{2},y_{2}) (x2?,y2?) 兩點，那么它必然也經過 ( x 1 + k ( x 1 ? x 2 ) , y 1 + k ( y 1 ? y 2 ) ) (x_{1} +k(x_{1} - x_{2}),y_{1} + k(y_{1} - y_{2})) (x1?+k(x1??x2?),y1?+k(y1??y2?))， k ∈ Z k \in Z k∈Z，

??若在連接一條直線時，將所有直線經過的點標記起來，在下次遇到已經標記過的兩點，我們便可直接跳過，

public class Test {

    public static void main(String[] args) { new Test().run(); }

    int X = 20, Y = 21;

    void run() {
        int count = 0;
        boolean[][][][] marked = new boolean[X][Y][X][Y];
        for (int x1 = 0; x1 < X; x1++)
            for (int y1 = 0; y1 < Y; y1++) {
                marked[x1][y1][x1][y1] = true;
                for (int x2 = 0; x2 < X; x2++)
                    for (int y2 = 0; y2 < Y; y2++) {
                        if (marked[x1][y1][x2][y2]) continue;
                        int x = x1, y = y1, xOffset = x - x2, yOffset = y - y2;
                        while (x >= 0 && x < X && y >= 0 && y < Y) {
                            x += xOffset;
                            y += yOffset;
                        }
                        x -= xOffset;
                        y -= yOffset;
                        while (x >= 0 && x < X && y >= 0 && y < Y) {
                            for (int i = x - xOffset, j = y - yOffset; i >= 0 && i < X && j >= 0 && j < Y; i -= xOffset, j -= yOffset) {
                                marked[x][y][i][j] = marked[i][j][x][y] = true;
                            }
                            x -= xOffset;
                            y -= yOffset;
                        }
                        count++;
                    }
            }
        System.out.println(count);
    }
}

??我覺得可能會再考個差不多的，這里給大伙一個推論，

??平面直角坐標系上有 n × n n × n n×n， n ≥ 2 n \ge 2 n≥2 個點 { ( x , y ) ∣ 0 ≤ x < n , 0 ≤ y < n , x ∈ Z , y ∈ Z } \{(x, y)|0 ≤ x < n, 0 ≤ y < n, x ∈ Z, y ∈ Z\} {(x,y)∣0≤x<n,0≤y<n,x∈Z,y∈Z}，從原點出發可連接的不同直線為 1 ≤ x , y < n 1 \leq x,y <n 1≤x,y<n， x ≠ y x \ne y x?=y 中 g c d ( x , y ) = 1 gcd(x,y) = 1 gcd(x,y)=1 的次數加 3 3 3，

??感興趣的讀者可以自行證明，

??同時在 1 ≤ x < y < n 1 \leq x < y < n 1≤x<y<n 時， g c d ( x , y ) = 1 gcd(x,y) = 1 gcd(x,y)=1 的出現次數恰好等于 ∑ y = 2 n ? 1 φ ( y ) \displaystyle\sum_{y = 2}^{n-1}\varphi(y) y=2∑n?1?φ(y)，其中 φ \varphi φ 為歐拉函式，

??能力有限，這里便不再繼續討論，

#D 貨物擺放

本題總分：10 分

問題描述

??小藍有一個超大的倉庫，可以擺放很多貨物，
??現在，小藍有 n n n 箱貨物要擺放在倉庫，每箱貨物都是規則的正方體，小藍規定了長、寬、高三個互相垂直的方向，每箱貨物的邊都必須嚴格平行于長、寬、高，
??小藍希望所有的貨物最終擺成一個大的立方體，即在長、寬、高的方向上分別堆 L 、 W 、 H L、W、H L、W、H 的貨物，滿足 n = L × W × H n = L × W × H n=L×W×H，
??給定 n n n，請問有多少種堆放貨物的方案滿足要求，
??例如，當 n = 4 n = 4 n=4 時，有以下 6 6 6 種方案： 1 × 1 × 4 1×1×4 1×1×4、 1 × 2 × 2 1×2×2 1×2×2、 1 × 4 × 1 1×4×1 1×4×1、 2 × 1 × 2 2×1×2 2×1×2、 2 × 2 × 1 2 × 2 × 1 2×2×1、 4 × 1 × 1 4 × 1 × 1 4×1×1，
??請問，當 n = 2021041820210418 n = 2021041820210418 n=2021041820210418 （注意有 16 16 16 位數字）時，總共有多少種方案？
??提示：建議使用計算機編程解決問題，

答案提交

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

2430

暴力搜索

??每屆必考的基本算術定理，

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;

public class Test {

    public static void main(String[] args) { new Test().run(); }

    long n = 2021041820210418L;

    void run() {
        List<Integer> exps0 = new ArrayList();
        ArrayDeque<Integer> exps1 = new ArrayDeque();
        for (int k = 2; k <= n; k++)
            if (n % k == 0) {
                int e = 0;
                while (n % k == 0) {
                    n /= k;
                    e++;
                }
                exps0.add(e);
            }
        System.out.println(dfs(exps0, exps1, 0));
    }

    int dfs(List<Integer> exps0, ArrayDeque<Integer> exps1, int cur) {
        if (cur == exps0.size()) {
            int comb = 1;
            for (int exp : exps1)
                comb *= exp + 1;
            return comb;
        }
        int ans = 0;
        for (int i = exps0.get(cur); i >= 0; i--) {
            exps1.push(i);
            ans += dfs(exps0, exps1, cur + 1);
            exps1.pop();
        }
        return ans;
    }
}

??直接套兩 for 也不是不行，但這么寫出來的程式，通常到比賽結束都跑不完，

??因此我們要避免無效因子的判斷，

??這里統計的為質因子分成三份，可能的組合個數，它與原命題等價，

??沒什么好講的，

??只用套兩 for 是因為一個數的因子只能成對出現，

??掃一下數盲，

縮放質因子

??舉個例子，

??當 n = 9 n = 9 n=9? 時，有 6 6 6 種方案： 1 × 1 × 9 1×1×9 1×1×9、 1 × 3 × 3 1×3×3 1×3×3、 1 × 9 × 1 1×9×1 1×9×1、 3 × 1 × 3 3×1×3 3×1×3、 3 × 3 × 1 3 × 3 × 1 3×3×1、 9 × 1 × 1 9 × 1 × 1 9×1×1;

??當 n = 25 n = 25 n=25 時，有 6 6 6 種方案： 1 × 1 × 25 1×1×25 1×1×25、 1 × 5 × 5 1×5×5 1×5×5、 ? \cdots ? ;

??當 n = p 2 n =p^{2^{}} n=p2 時，有 6 6 6 種方案： 1 × 1 × p 2 1×1×p^{2} 1×1×p2、 1 × p × p 1×p×p 1×p×p、 ? \cdots ? ;

??其中 p p p 為質數，

??其實上例解法當中，我們就能發現，組合的個數與其具體的值無關，它只與質因數指數掛鉤，

?? 2021041820210418 = 2 × 3 3 × 17 × 131 × 2857 × 5882353 2021041820210418 = 2 × 3^3 × 17 × 131 × 2857 × 5882353 2021041820210418=2×33×17×131×2857×5882353

??如果我們找最小的幾個質數來代替它們，得到的新數字 2 3 × 3 × 5 × 7 × 11 × 13 = 120120 2^3 × 3 × 5 × 7 × 11 × 13 = 120120 23×3×5×7×11×13=120120 與 2021041820210418 2021041820210418 2021041820210418 在這個命題下等價，

??而 120120 120120 120120 的大小就足夠我們真暴搜把它的全部因陣列合找到了，

import java.util.ArrayList;
import java.util.List;

public class Test {

    public static void main(String[] args) { new Test().run(); }

    long N = 2021041820210418L;

    void run() {
        List<Integer> exps = new ArrayList();
        for (int k = 2; k <= N; k++)
            if (N % k == 0) {
                int e = 0;
                while (N % k == 0) {
                    N /= k;
                    e++;
                }
                exps.add(e);
            }
        exps.sort((a, b) -> (b - a));
        int n = 1, p = 2, ans = 0;
        for (int exp : exps) {
            for (int i = 2; i * i <= p; i++)
                if (p % i == 0) {
                    i = 1;
                    p++;
                }
            while (exp-- > 0) n *= p;
            p++;
        }
        for (int a = 1; a <= n; a++)
            if (n % a == 0)
                for (int b = 1; b <= n; b++)
                    if (n / a % b == 0) ans++;
        System.out.println(ans);
    }
}

#E 路徑

本題總分：15 分

問題描述

??小藍學習了最短路徑之后特別高興，他定義了一個特別的圖，希望找到圖中的最短路徑，
??小藍的圖由 2021 2021 2021 個結點組成，依次編號 1 1 1 至 2021 2021 2021，對于兩個不同的結點 a , b a, b a,b，如果 a a a 和 b b b 的差的絕對值大于 21 21 21，則兩個結點之間沒有邊相連；如果 a a a 和 b b b 的差的絕對值小于等于 21 21 21，則兩個點之間有一條長度為 a a a 和 b b b 的最小公倍數的無向邊相連，
??例如：結點 1 1 1 和結點 23 23 23 之間沒有邊相連；結點 3 3 3 和結點 24 24 24 之間有一條無向邊，長度為 24 24 24；結點 15 15 15 和結點 25 25 25 之間有一條無向邊，長度為 75 75 75，
??請計算，結點 1 1 1 和結點 2021 2021 2021 之間的最短路徑長度是多少，
??提示：建議使用計算機編程解決問題，

答案提交

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

10266837

??題目已經說的夠清楚了，

??建一個有 2021 2021 2021 個頂點 21 × 2000 + 21 ( 21 + 1 ) 2 21 × 2000 + \cfrac{21(21 + 1)}{2} 21×2000+221(21+1)? 條邊的無向圖，跑圖上的演算法就完事了，

??還有的細節就是整形是否會溢位，我們取 ( 1 , 2021 ] (1,2021] (1,2021] 中最大的質數 2017 2017 2017 與 202 1 2 2021^2 20212 相乘，得到的結果還是有點夸張的，雖然經過測驗，可能的線路權值合至多不會超過 2 31 ? 1 2^{31} - 1 231?1，但畢竟是面向競賽，考慮甄別的時間成本，直接使用長整形更為劃算，

搜索

深度優先搜索

?? 2021 2021 2021 個頂點，絕大多數頂點都連有 2 × 21 2 × 21 2×21 條邊，

??別深搜了，一搜就是

??compilaition completed successfully in 500ms(4 hour ago)

??就，電腦跟選手對著坐牢，

記憶化搜索

??深度優先搜索，在搜索最優結果時，通常需要完整的列舉全部可能的問題狀態，

??但在這個問題狀態的集合中，所有可選方案的 “后綴” 都是相同，也就是所有可選的分支，它們都是以同一個節點結尾，

??如果我們將已經搜索到的節點到目標節點間的最短路徑保存下來，在再次搜索到這個 “后綴” 的分支時直接回傳，

??那么問題就可能在一個較短的時間內解決，

??這也是所謂的記憶化搜索，

import java.util.ArrayList;
import java.util.List;

public class Test {

    public static void main(String[] args) { new Test().run(); }

    int N = 2021;

    int[] weight = new int[N + 1];

    List<Edge>[] graph = new List[N + 1];

    boolean[] visited = new boolean[N + 1];

    void run() {
        for (int i = 1; i <= N; i++)
            graph[i] = new ArrayList();
        for (int v = 1; v <  N; v++)
            for (int w = v + 1; w <= min(v + 21, N);  w++) {
                graph[v].add(new Edge(w, lcm(v, w)));
                graph[w].add(new Edge(v, lcm(v, w)));
            }
        visited[1] = true;
        System.out.println(dfs(1));
    }

    int dfs(int v) {
        if (v == N) return 0;
        if (weight[v] != 0) return weight[v];
        int min = 0x7FFFFFFF;
        for (Edge edge : graph[v]) {
            if (visited[edge.w]) continue;
            visited[edge.w] = true;
            min = min(min, dfs(edge.w) + edge.weight);
            visited[edge.w] = false;
        }
        return weight[v] = min;
    }

    int min(int a, int b) { return a < b ? a : b; }

    int lcm(int a, int b) { return a * b / gcd(a, b); }

    int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }

    class Edge {

        int w, weight;

        Edge(int w, int weight) {
            this.weight = weight;
            this.w = w;
        }
    }
}

枝剪廣搜

??其實樸素的去搜索，不論深搜還是廣搜，在競賽里都是很冒進的行為，

??影響這兩個演算法執行效率的因素太多，

??當然要是沒有其他的思路，也只能死馬當活馬醫了，

??幸運的是，只需簡單的枝剪，就能在很短的時間計算出結果

import java.util.PriorityQueue;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Queue;
import java.util.List;

public class Test {

    public static void main(String[] args) { new Test().run(); }

    int N = 2021;
    
    void run() {
        List<Edge>[] graph = new List[N + 1];
        long[] visited = new long[N + 1];
        for (int i = 1; i <= N; i++)
            graph[i] = new ArrayList();
        for (int v = 1; v <  N; v++)
            for (int w = v + 1; w <= min(v + 21, N);  w++) {
                graph[v].add(new Edge(w, lcm(v, w)));
                graph[w].add(new Edge(v, lcm(v, w)));
            }
        Queue<Vertex> queue = new PriorityQueue();
        Arrays.fill(visited, Long.MAX_VALUE);
        queue.offer(new Vertex(1, 0));
        Vertex V = null;
        while (queue.size() > 0) {
            V = queue.poll();
            if (V.v == N) break;
            if (V.weight >= visited[V.v]) continue;
            visited[V.v] = V.weight;
            for (Edge edge : graph[V.v])
                queue.offer(new Vertex(edge.w, edge.weight + V.weight));
        }
        System.out.println(V.weight);
    }

    int min(int a, int b) { return a < b ? a : b; }

    int lcm(int a, int b) { return a * b / gcd(a, b); }

    int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }

    class Edge {

        int w, weight;

        Edge(int w, int weight) {
            this.weight = weight;
            this.w = w;
        }
    }

    class Vertex implements Comparable<Vertex> {

        int v;
        long weight;

        Vertex(int v, long weight) {
            this.weight = weight;
            this.v = v;
        }

        @Override
        public int compareTo(Vertex V) { return Long.compare(this.weight, V.weight); }
    }
}

雙向搜索

??很容易就能發現，越是編號大的節點，連接著它的邊的權重可能越大，

??也就是在最短路徑的這條分支中，越是靠近目標節點，就越可能進入無效的分支，

??通常，在這個資料規模下，不帶策略的去廣搜是致命的，

??一種常見的優化方法是從源點和終點雙向開始搜索，當兩條分支相遇時，即視為找到了最短路徑，

??由于這種問題可選擇的解法有很多，這里便不做展開，

import java.util.PriorityQueue;
import java.util.ArrayList;
import java.util.Queue;
import java.util.List;

public class Test {

    public static void main(String[] args) { new Test().run(); }

    int N = 2021;

    void run() {
        List<Edge>[] graph = new List[N + 1];
        long[] visited0 = new long[N + 1];
        long[] visited1 = new long[N + 1];
        for (int i = 1; i <= N; i++) {
            graph[i] = new ArrayList();
            visited0[i] = visited1[i] = Long.MAX_VALUE;
        }
        for (int v = 1; v <  N; v++)
            for (int w = v + 1; w <= min(v + 21, N);  w++) {
                graph[v].add(new Edge(w, lcm(v, w)));
                graph[w].add(new Edge(v, lcm(v, w)));
            }
        Queue<Vertex> queue = new PriorityQueue();
        queue.offer(new Vertex(N, 0, false));
        queue.offer(new Vertex(1, 0));
        Vertex V = null;
        while (true) {
            V = queue.poll();
            if (V.fromHead) {
                if (visited1[V.v] != Long.MAX_VALUE) break;
                if (V.weight >= visited0[V.v]) continue;
                visited0[V.v] = V.weight;
            } else {
                if (visited0[V.v] != Long.MAX_VALUE) break;
                if (V.weight >= visited1[V.v]) continue;
                visited1[V.v] = V.weight;
            }
            for (Edge edge : graph[V.v])
                queue.add(new Vertex(edge.w, edge.weight + V.weight, V.fromHead));
        }
        System.out.println(V.weight + (V.fromHead ? visited1[V.v] : visited0[V.v]));
    }

    int min(int a, int b) { return a < b ? a : b; }

    int lcm(int a, int b) { return a * b / gcd(a, b); }

    int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }

    class Edge {

        int w, weight;

        Edge(int w, int weight) {
            this.weight = weight;
            this.w = w;
        }
    }

    class Vertex implements Comparable<Vertex> {

        int v;
        long weight;
        boolean fromHead;

        Vertex(int v, long weight) { this(v, weight, true); }

        Vertex(int v, long weight, boolean fromHead) {
            this.fromHead = fromHead;
            this.weight = weight;
            this.v = v;
        }

        @Override
        public int compareTo(Vertex V) { return Long.compare(this.weight, V.weight); }
    }
}

單源最短路徑

Dijkstra

??題目給出的圖顯然是個邊加權，權重非負的無向圖，跑遍 D i j k s t r a Dijkstra Dijkstra 就完事了，

import java.util.PriorityQueue;
import java.util.ArrayList;
import java.util.Queue;
import java.util.List;

public class Test {

    public static void main(String[] args) { new Test().run(); }

    int N = 2021;

    void run() {
        boolean[] marked = new boolean[N + 1];
        List<Edge>[] graph = new List[N + 1];
        long[] distTo = new long[N + 1];
        for (int i = 1; i <= N; i++) {
            graph[i] = new ArrayList();
            distTo[i] = Long.MAX_VALUE;
        }
        for (int v = 1; v <  N; v++)
            for (int w = v + 1; w <= min(v + 21, N);  w++) {
                graph[v].add(new Edge(w, lcm(v, w)));
                graph[w].add(new Edge(v, lcm(v, w)));
            }
        Queue<Vertex> queue = new PriorityQueue();
        queue.offer(new Vertex(1, distTo[1] = 0));
        while (queue.size() > 0) {
            Vertex V = queue.poll();
            if (marked[V.v])
                    continue;
            marked[V.v] = true;
            for (Edge edge : graph[V.v])
                if (distTo[edge.w] > distTo[V.v] + edge.weight)
                    queue.offer(new Vertex(edge.w, distTo[edge.w] = distTo[V.v] + edge.weight));
        }
        System.out.println(distTo[N]);
    }

    int min(int a, int b) { return a < b ? a : b; }

    int lcm(int a, int b) { return a * b / gcd(a, b); }

    int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }

    class Edge {

        int w, weight;

        Edge(int w, int weight) {
            this.weight = weight;
            this.w = w;
        }
    }

    class Vertex implements Comparable<Vertex> {

        int v;
        long dist;

        Vertex(int v, long dist) {
            this.dist = dist;
            this.v = v;
        }

        @Override
        public int compareTo(Vertex V) { return Long.compare(this.dist, V.dist); }
    }
}

Floyd

??如果是一道最短路徑的結果題，

??競賽時限內能運行完 O ( n 3 ) O(n^{3}) O(n3) 的程式，

??那其實無腦套 F l o y d Floyd Floyd 就行，

public class Test {

    public static void main(String[] args) { new Test().run(); }

    int N = 2021;

    void run() {
        long[][] floyd = new long[N + 1][N + 1];
        for (int v = 1; v < N; v++)
            for (int w = v + 1; w <= min(N, v + 21); w++)
                floyd[v][w] = floyd[w][v] = lcm(v, w);
        for (int k = 1; k <= N; k++)
            for (int v = 1; v <= N; v++)
                if (floyd[v][k] == 0) continue;
                else for (int w = 1; w <= N; w++)
                    if (floyd[k][w] == 0) continue;
                    else if (floyd[v][w] == 0 || floyd[v][k] + floyd[k][w] < floyd[v][w])
                        floyd[v][w] = floyd[v][k] + floyd[k][w];
        System.out.println(floyd[1][N]);
    }

    long min(int a, int b) { return a < b ? a : b; }

    int lcm(int a, int b) { return a * b / gcd(a, b); }

    int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
}

??半分鐘就出來了，還行，

A*

??隱隱覺得能找到一些有啟發性的性質，

??推了一下午狗屁沒推出來，就當在這開個坑把，

在這里插入代碼片

動態規劃

??受不同的圖性質影響，通常最短路徑問題難以在線性時間內用動態規劃解決，

??但這里給定無向圖，

??我們將最短路徑上的節點按升序排列，對于任意 v v v、 w w w， 1 < v < w < n 1 < v < w < n 1<v<w<n 只存在以下兩種情況：

在這里插入圖片描述
??但只有序號的絕對差小于等于 21 21 21 時，兩個節點之間才存在邊，即二圖情況的前提條件是 1 < v < w ≤ 22 1 < v < w \leq 22 1<v<w≤22，將其推廣至 1 ≤ x < v < w < y ≤ n 1 \leq x < v < w < y \leq n 1≤x<v<w<y≤n 的情況，

??顯然，從源點到任意點 V V V 的最短路徑只會從 [ V ? 21 , V + 21 ] [V -21,V+21] [V?21,V+21] 中產生，我們先順序的求出每個 W = V + 21 W = V + 21 W=V+21 較優路徑，再用每個 W W W 對 [ W ? 21 , W ) [W - 21, W) [W?21,W) 間的節點進行松弛，松弛完畢時 ( 1 , V ] (1,V] (1,V] 間的路徑已是最優，

??綜上有狀態轉移方程：

?? d p ( i ) = min ? { d p ( j ) + l c m ( i , j ) } dp(i) = \min\{dp(j) + lcm(i, j)\} dp(i)=min{dp(j)+lcm(i,j)}， i > j ≥ i ? 21 i > j \ge i -21 i>j≥i?21

public class Test {

    public static void main(String[] args) { new Test().run(); }

    int N = 2021;

    void run() {
        long[] dp = new long[N + 1];
        for (int w = 2; w <= N; w++) {
            dp[w] = Long.MAX_VALUE;
            for (int v = w - 1; v > 0 && v >= w - 21; v--)
                dp[w] = min(dp[w], dp[v] + lcm(v, w));
        }
        System.out.println(dp[N]);
    }

    long min(long a, long b) { return a < b ? a : b; }

    int lcm(int a, int b) { return a * b / gcd(a, b); }

    int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
}

#F 時間顯示

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

問題描述

??小藍要和朋友合作開發一個時間顯示的網站，在服務器上，朋友已經獲取了當前的時間，用一個整數表示，值為從 1970 1970 1970 年 1 1 1 月 1 日 00 : 00 : 00 00:00:00 00:00:00 到當前時刻經過的毫秒數，
??現在，小藍要在客戶端顯示出這個時間，小藍不用顯示出年月日，只需顯示出時分秒即可，毫秒也不用顯示，直接舍去即可，
??給定一個用整數表示的時間，請將這個時間對應的時分秒輸出，

輸入格式

??輸入一行包含一個整數，表示時間，

輸出格式

??輸出時分秒表示的當前時間，格式形如 H H HH HH: M M MM MM: S S SS SS，其中 H H HH HH 表示時，值為 0 0 0 到 23 23 23， M M MM MM 表示分，值為 0 0 0 到 59 59 59， S S SS SS 表示秒，值為 0 0 0 到 59 59 59，時、分、秒不足兩位時補前導 0 0 0，

測驗樣例₁

Input：
46800999

Output：
13:00:00

測驗樣例₂

Input：
1618708103123

Output：
01:08:23

評測用例規模與約定

??對于所有評測用例，給定的時間為不超過 1 0 18 10^{18} 1018 的正整數，

Java Win

import java.util.Scanner;
import java.time.LocalTime;
import java.time.format.DateTimeFormatter;

public class Main {

    public static void main(String[] args) { new Main().run(); }

    void run() {
        System.out.println(
            LocalTime.MIDNIGHT.
            plusSeconds(
            	new Scanner(System.in).nextLong() / 1000).
            format(DateTimeFormatter.ISO_LOCAL_TIME)
        );
    }
}

不依賴 API 的實作

import java.util.Scanner;

public class Test {

    public static void main(String[] args) { new Test().run(); }

    void run() {
        long t = new Scanner(System.in).nextLong();
        System.out.printf("%02d:%02d:%02d",
            t / 3600000 % 24, t / 60000 % 60, t / 1000 % 60);
    }
}

??送分，

#G 最少砝碼

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

問題描述

??你有一架天平，現在你要設計一套砝碼，使得利用這些砝碼可以稱出任意小于等于 N N N 的正整數重量，
??那么這套砝碼最少需要包含多少個砝碼？
??注意砝碼可以放在天平兩邊，

輸入格式

??輸入包含一個正整數 N N N，

輸出格式

??輸出一個整數代表答案，

測驗樣例₁

Input：
7

Output：
3

Explanation：
3 個砝碼重量是 1、4、6，可以稱出 1 至 7 的所有重量，
1 = 1；
2 = 6 ? 4 (天平一邊放 6，另一邊放 4)；
3 = 4 ? 1；
4 = 4；
5 = 6 ? 1；
6 = 6；
7 = 1 + 6；
少于 3 個砝碼不可能稱出 1 至 7 的所有重量，

評測用例規模與約定

??對于所有評測用例， 1 ≤ N ≤ 1000000000 1 ≤ N ≤ 1000000000 1≤N≤1000000000，

變種三進制

??不知道怎么取標題，也算是個規律題，

??這不是純純的惡心人嗎，

??一個集合中包含 n n n 個數，任取若干數可以加減出任意小于等于 N N N 的正整數，

??首先要考慮怎么去滿足題目要求的性質，

??設第 i i i 個砝碼的重量為 w i w_{i} wi?，原集合 A N = { w 1 , w 2 , ? ? , w n } A_{N} = \{w_{1},w_{2},\cdots,w_{n}\} AN?={w1?,w2?,?,wn?}，

??要滿足題意首先要有 s u m ( A ) ≥ N sum(A) \ge N sum(A)≥N，

??設我們知道了 A ? N / 3 ? A_{\lfloor N/3 \rfloor} A?N/3?? 的方案，那么我們就能在這個方案里加入一個 2 ? N / 3 ? + 1 2\lfloor N/3 \rfloor + 1 2?N/3?+1，就能用 2 ? N / 3 ? + 1 2\lfloor N/3 \rfloor + 1 2?N/3?+1 對 A ? N / 3 ? A_{\lfloor N/3 \rfloor} A?N/3?? 中個若干元素做差表示出 ( ? N / 3 ? , 2 ? N / 3 ? + 1 ) (\lfloor N/3 \rfloor, 2\lfloor N/3 \rfloor + 1) (?N/3?,2?N/3?+1)，對若干元素求和表示出 ( 2 ? N / 3 ? + 1 , N ] (2\lfloor N/3 \rfloor + 1, N] (2?N/3?+1,N]，并入 A ? N / 3 ? A_{\lfloor N/3 \rfloor} A?N/3?? 本身能表示的范圍，即能表示出任意小于等于 N N N 的正整數，

??如果 A ? N / 3 ? A_{\lfloor N/3 \rfloor} A?N/3?? 本身是最優的，那么往里面加入 K = 2 ? N / 3 ? + 1 K = 2\lfloor N/3 \rfloor + 1 K=2?N/3?+1 的 A N A_N AN? 也一定是最優的，因為要使得 K + s u m ( A ? N / 3 ? ) ≥ N K + sum(A_{\lfloor N/3 \rfloor}) \ge N K+sum(A?N/3??)≥N， K K K 必須大于等于 2 ? N / 3 ? + 1 2\lfloor N/3 \rfloor + 1 2?N/3?+1，而當 K > 2 ? N / 3 ? + 1 K > 2\lfloor N/3 \rfloor + 1 K>2?N/3?+1 時，就無法表示出 ? N / 3 ? + 1 \lfloor N/3 \rfloor + 1 ?N/3?+1，

??當然這一切還有個前提條件，那就是 s u m ( A ? N / 3 ? ) = ? N / 3 ? sum(A_{\lfloor N/3 \rfloor}) = \lfloor N/3 \rfloor sum(A?N/3??)=?N/3?，’

??不過到這里已經足夠啟發我們去順推了，

??因為這個問題的邊界是顯然的，

??當 N = 1 N = 1 N=1 時， A 1 = { 1 } A_{1} = \{1\} A1?={1}，

??我們往 A 1 A_{1} A1? 中加入 2 × s u m ( A 1 ) + 1 2 × sum(A_{1}) + 1 2×sum(A1?)+1，得到 A 4 A_{4} A4?，即

??當 N = 4 N = 4 N=4 時， A 4 = { 1 , 3 } A_{4} = \{1,3\} A4?={1,3}，

??當 N = 13 N = 13 N=13 時， A 13 = { 1 , 3 , 9 } A_{13} = \{1,3,9\} A13?={1,3,9}，

?? ? ? \cdots \cdots ??

??當然還存在 N N N 不在我們找到的最優規律中，

??我們設 N = 5 N = 5 N=5，

??因為 A 4 = { 1 , 3 } A_{4} = \{1,3\} A4?={1,3} 的最優性， 2 2 2 個元素至多組成任意小于等于 4 4 4 的正整數，

??因為 A 13 = { 1 , 3 , 9 } A_{13} = \{1,3,9\} A13?={1,3,9} 的最優性， 3 3 3 個元素可以表示任意小于等于 13 13 13 的正整數，

??即對 N = 5 N = 5 N=5 給出的答案，必須大于 2 2 2 小于等于 3 3 3，

??對于給出任意 N N N 我們都可以按照這個性質求出答案，

??同時在三進制下來看這個規律：

?? { N } = { ( 1 ) 3 , ( 11 ) 3 , ( 11 ) 3 , ? ? } \{N\} = \{(1)_{3},(11)_{3},(11)_{3},\cdots\} {N}={(1)3?,(11)3?,(11)3?,?}

??可以二分，但沒有必要，

import java.util.Scanner;

public class Main {

    public static void main(String[] args) { new Main().run(); }

    void run() {
        long N = new Scanner(System.in).nextLong(), ans = 1;
        for (long pow3 = 1; pow3 < N; pow3 = pow3 * 3 + 1, ans++);
        System.out.println(ans);
    }
}

??寫的稀爛，主要這題目出的就惡心人，

#H 楊輝三角形

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

??下面的圖形是著名的楊輝三角形：
??如果我們按從上到下、從左到右的順序把所有數排成一列，可以得到如下數列：

請添加圖片描述
?? 1 , 1 , 1 , 1 , 2 , 1 , 1 , 3 , 3 , 1 , 1 , 4 , 6 , 4 , 1 , ? 1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, \cdots 1,1,1,1,2,1,1,3,3,1,1,4,6,4,1,?
??給定一個正整數 N N N，請你輸出數列中第一次出現 N N N 是在第幾個數？

輸入格式

??輸入一個整數 N N N，

輸出格式

??輸出一個整數代表答案，

測驗樣例₁

Input：
6

Output：
13

評測用例規模與約定

??對于 20 20 20% 的評測用例， 1 ≤ N ≤ 10 1 ≤ N ≤ 10 1≤N≤10；
??對于所有評測用例， 1 ≤ N ≤ 1000000000 1 ≤ N ≤ 1000000000 1≤N≤1000000000，

??圖片高清重置

類比單調數列

??楊輝三角最外層全部是 1 1 1，

??第二層則是自然數序列，
在這里插入圖片描述
??因為楊輝三角是左右對稱的，因此我們可以忽略右邊(左邊的數字總是比右邊先出現)，并將數字按層分成若干序列，
請添加圖片描述
??由于序列都是從上置下單調遞增的，我們可以在每一個這種序列上，二分查找 N N N 的位置，特別的， N = 1 N = 1 N=1 時直接輸出 1 1 1，

??此外，楊輝三角第 n n n 行 m 列列列

?? = C n ? 1 m ? 1 = ( n ? 1 ) ! ( m ? 1 ) ! ( n ? m ) ! =C_{n-1}^{m-1} = \cfrac{(n-1)!}{(m-1)!(n - m)!} =Cn?1m?1?=(m?1)!(n?m)!(n?1)!?

??這個數字增長的非常快 C 32 16 = 1166803110 > 1 e 9 C_{32}^{16} = 1166803110 > 1e9 C3216?=1166803110>1e9，

??也就至多在 14 14 14 條(除去最外兩層)這樣的序列中查找 N N N 的位置，因為序列的單調性不允許 N N N 的出現，

import java.util.Scanner;

public class Main {

    public static void main(String[] args) { new Main().run(); }

    int N;

    void run() {
        N = new Scanner(System.in).nextInt();
        if (N == 1) System.out.println(1);
        else {
            long ans = (N + 1L) * N / 2 + 2;
            for (int m = 2; m < 16; m++) {
                int start = m * 2, end = N;
                while (start <= end) {
                    int mid = start + end >> 1;
                    if (C(mid, m) == N) {
                        ans = min(ans, (mid + 1L) * mid / 2 + m + 1);
                        break;
                    } if (C(mid, m) > N) end = mid - 1;
                    else start = mid + 1;
                }
            }
            System.out.println(ans);
        }
    }

    long min(long a, long b) { return a < b ? a : b; }

    long C(int n, int m) {
        long num = 1;
        for (int nm = 1; nm <= m; n--, nm++)
            if ((num = num * n / nm) > N) return num;
        return num;
    }
}

#I 雙向排序

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

問題描述

??給定序列 ( a 1 , a 2 , ? ? ? , a n ) = ( 1 , 2 , ? ? ? , n ) (a_{1}, a_{2}, · · · , a_{n}) = (1, 2, · · · , n) (a1?,a2?,???,an?)=(1,2,???,n)，即 a i = i a_{i} = i ai?=i，
??小藍將對這個序列進行 m m m 次操作，每次可能是將 a 1 , a 2 , ? ? ? , a q i a_{1}, a_{2}, · · · , a_{q_{i}} a1?,a2?,???,aqi?? 降序排列，或者將 a q i , a q i + 1 , ? ? ? , a n a_{q_{i}}, a_{q_{i+1}}, · · · , a_{n} aqi??,aqi+1??,???,an? 升序排列，
??請求出操作完成后的序列，

輸入格式

??輸入的第一行包含兩個整數 n , m n, m n,m，分別表示序列的長度和操作次數，
??接下來 m m m 行描述對序列的操作，其中第 i i i 行包含兩個整數 p i , q i p_{i}, q_{i} pi?,qi? 表示操作型別和引數，當 p i = 0 p_{i} = 0 pi?=0 時，表示將 a 1 , a 2 , ? ? ? , a q i a_{1}, a_{2}, · · · , a_{q_{i}} a1?,a2?,???,aqi?? 降序排列；當 p i = 1 p_{i} = 1 pi?=1 時，表示將 a q i , a q i + 1 , ? ? ? , a n a_{q_{i}}, a_{q_{i+1}}, · · · , a_{n} aqi??,aqi+1??,???,an? 升序排列，

輸出格式

??輸出一行，包含 n n n 個整數，相鄰的整數之間使用一個空格分隔，表示操作完成后的序列，

測驗樣例₁

Input：
3 3
0 3
1 2
0 2

Output：
3 1 2

Explanation：
原數列為 (1, 2, 3)，
第 1 步后為 (3, 2, 1)，
第 2 步后為 (3, 1, 2)，
第 3 步后為 (3, 1, 2)，與第 2 步操作后相同，因為前兩個數已經是降序了，

評測用例規模與約定

??對于 30 30 30% 的評測用例， n , m ≤ 1000 n, m ≤ 1000 n,m≤1000；
??對于 60 60 60% 的評測用例， n , m ≤ 5000 n, m ≤ 5000 n,m≤5000；
??對于所有評測用例， 1 ≤ n , m ≤ 100000 1 ≤ n, m ≤ 100000 1≤n,m≤100000， 0 ≤ p i ≤ 1 0 ≤ p_{i} ≤ 1 0≤pi?≤1， 1 ≤ q i ≤ n 1 ≤ q_{i} ≤ n 1≤qi?≤n；

去冗操作

??其實看到這個資料規模，五分鐘寫完 Brute Force，就可以下一道了， O ( m n log ? n ) O(mn \log n) O(mnlogn) 就能過 60 60 60% 的用例，

??多的時間去證明其他程式的正確性可能收益會高點，

??不過，騙分就多騙兩個吧，

??對于連續且 p i p_{i} pi? 相同操作，在 p i = 0 p_{i} = 0 pi?=0 時只需要做 q i q_{i} qi? 最大的操作，在 p i = 1 p_{i} = 1 pi?=1 時只需要做 q i q_{i} qi? 最小的操作，如圖：

請添加圖片描述
??顯然去掉冗余操作后，還是和原操作是等價的，只需要建立一個堆疊就能在線性時間內完成去冗，并且代碼量較少，

??特別的，我可以先將 ( p : 1 , q : 1 ) (p:1,q:1) (p:1,q:1) 壓入堆疊底，

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) { new Main().run(); }

    void run() {
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);
        int n = in.readInt(), m = in.readInt();
        Deque<Step> deque = new ArrayDeque();
        deque.push(new Step(1, 1));
        while (m-- > 0) {
            int p = in.readInt();
            int q = in.readInt();
            while (deque.size() > 0 && deque.peek().p == p)
                if (p == 0)
                    q = max(q, deque.pop().q);
                else
                    q = min(q, deque.pop().q);
            deque.push(new Step(p, q));
        }
        Integer[] ans = new Integer[n];
        for (int i = 0; i < n; i++)
            ans[i] = i + 1;
        deque.pollLast();
        while (deque.size() > 0) {
            Step step = deque.pollLast();
            if (step.p == 0)
                Arrays.sort(ans, 0, step.q, (a, b)->(b - a));
            else
                Arrays.sort(ans, step.q - 1, n);
        }
        for (int i = 0; i < n; i++) {
            out.print(ans[i]);
            out.print(' ');
        }
        out.flush();
    }

    int max(int a, int b) { return a > b ? a : b; }

    int min(int a, int b) { return a < b ? a : b; }

    class Step {

        int p, q;

        Step(int p, int q) {
            this.p = p;
            this.q = q;
        }
    }

    class InputReader {

        BufferedReader reader;
        StringTokenizer token;

        InputReader(InputStream in) {
            this.reader = new BufferedReader(new InputStreamReader(in));
        }

        String read() {
            while (token == null || !token.hasMoreTokens()) {
                try {
                    token = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return token.nextToken();
        }

        int readInt() { return Integer.parseInt(read()); }
    }
}

填數游戲

??其實最開始就想直接寫到這一步，

??但是我忙的同時又有點閑，就拆開寫吧，

??經過上述去冗操作，可以發現，最后需要操作的是一個 p 0 ∣ 1 p \ 0\mid 1 p 0∣1 交替的序列，為了便于讀者理解，

??這里將原序列和操作抽象成不等長不同色線段，

??特別的，原序列和 p = 1 p = 1 p=1 的操作是一個顏色，因為原序列本就是升序，

請添加圖片描述
??將 p = 0 p=0 p=0 和 p = 1 p=1 p=1 最大操作范圍標記出來，

在這里插入圖片描述
??顯然，在 q q q 不為端點時，每次操作都有段不變的區間，

??影像告訴了我們，如果 q q q 操作的范圍蓋過了堆疊里最近的 q q q，那么不僅這個最近的 q q q，連同堆疊頂 q q q 相反的操作都是可以跳過的，

??同時根據這個性質優化后，根據堆疊內剩余的操作，我們總是能找到一段順或倒序的不變區間，

??將不變區間填入最終的答案，整個演算法就大體完成了，

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) { new Main().run(); }

    void run() {
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);
        int n = in.readInt(), m = in.readInt(), top;
        Step[] stack = new Step[m + 1];
        for (top = 0; m-- > 0;) {
            int p = in.readInt();
            int q = in.readInt();
            if (p == 0) {
                while (top > 0 && stack[top].p == p) q = max(q, stack[top--].q);
                while (top > 1 && stack[top - 1].q <= q) top -= 2;
                stack[++top] = new Step(p, q);
            } else if (top > 0){
                while (top > 0 && stack[top].p == p) q = min(q, stack[top--].q);
                while (top > 1 && stack[top - 1].q >= q) top -= 2;
                stack[++top] = new Step(p, q);
            }
        }
        int[] ans = new int[n + 1];
        int a = n, l = 0, r = n - 1;
        for (int i = 1; i <= top; i++)
            if (stack[i].p == 0)
                while (r >= stack[i].q && l <= r) ans[r--] = a--;
            else
                while (l + 1 < stack[i].q && l <= r) ans[l++] = a--;
        if ((top & 1) == 1)
            while (l <= r) ans[l++] = a--;
        else
            while (l <= r) ans[r--] = a--;
        for (int i = 0; i < n; i++) {
            out.print(ans[i]);
            out.print(' ');
        }
        out.flush();
    }

    int max(int a, int b) { return a > b ? a : b; }

    int min(int a, int b) { return a < b ? a : b; }

    class Step {

        int p, q;

        Step(int p, int q) {
            this.p = p;
            this.q = q;
        }
    }

    class InputReader {

        BufferedReader reader;
        StringTokenizer token;

        InputReader(InputStream in) {
            this.reader = new BufferedReader(new InputStreamReader(in));
        }

        String read() {
            while (token == null || !token.hasMoreTokens()) {
                try {
                    token = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return token.nextToken();
        }

        int readInt() { return Integer.parseInt(read()); }
    }
}

樹分裂&合并 (未填)

#J 括號序列

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

問題描述

??給定一個括號序列，要求盡可能少地添加若干括號使得括號序列變得合法，當添加完成后，會產生不同的添加結果，請問有多少種本質不同的添加結果，
??兩個結果是本質不同的是指存在某個位置一個結果是左括號，而另一個是右括號，
??例如，對于括號序列 ((()，只需要添加兩個括號就能讓其合法，有以下幾種不同的添加結果：()()()、()(())、(())()、(()()) 和 ((()))，

輸入格式

??輸入一行包含一個字串 s s s，表示給定的括號序列，序列中只有左括號和右括號，

輸出格式

??輸出一個整數表示答案，答案可能很大，請輸出答案除以 1000000007 1000000007 1000000007 (即 1 0 9 + 7 10^{9} + 7 109+7) 的余數，

測驗樣例₁

Input：
((()

Output：
5

評測用例規模與約定

??對于 40 40 40% 的評測用例， ∣ s ∣ ≤ 200 |s| ≤ 200 ∣s∣≤200，
??對于所有評測用例， 1 ≤ ∣ s ∣ ≤ 5000 1 ≤ |s| ≤ 5000 1≤∣s∣≤5000，

不會

??遇到困難睡大覺，

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/338440.html

標籤：其他

上一篇：八佰(800)低代碼精耕行業細分領域數字化轉型

下一篇：重命名terraforms3狀態存盤桶

第十二屆藍橋杯 2021年省賽真題 (Java 大學B組) 第一場

藍橋杯 2021年省賽真題 (Java 大學B組 ）

#A ASC

#B 卡片

樸素解法

彎道超車

#C 直線

直線方程集合

分式消除誤差

平面幾何

#D 貨物擺放

暴力搜索

縮放質因子

#E 路徑

搜索

深度優先搜索

記憶化搜索

枝剪廣搜

雙向搜索

單源最短路徑

Dijkstra

Floyd

A*

動態規劃

#F 時間顯示

Java Win

不依賴 API 的實作

#G 最少砝碼

變種三進制

#H 楊輝三角形

類比單調數列

#I 雙向排序

去冗操作

填數游戲

樹分裂&合并 (未填)

#J 括號序列

不會

藍橋杯 2021年省賽真題 (Java 大學B組）