本題解為非官方題解，可能存在包括但不限于下列問題

答案錯誤
時間復雜度太高，無法在規定時間內得出結果

填空題答案速覽

67108864
3181
40257
2430
10266837

填空題

A 空間

問題描述
小藍準備用 256 256 256 MB 的記憶體空間開一個陣列，陣列的每個元素都是 32 32 32 位二進制整數，如果不考慮程式占用的空間和維護記憶體需要的輔助空間，請問 256 256 256 MB 的空間可以存盤多少個 32 32 32 位二進制整數？

題解
計算機基礎

注意一位元組等于八位
（因為考場電腦是32位系統，用 long long 會有奇奇怪怪的錯誤，而且python代碼更短，所以用python寫了）

print(256 * 1024 * 1024 * 8 // 32)

答案

67108864

B 卡片

問題描述
小藍有很多數字卡片，每張卡片上都是數字 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 拼到多少？

提示：建議使用計算機編程解決問題，

題解
模擬

#include <bits/stdc++.h>
using namespace std;
int a[10];
bool solve(int x) {
    while (x) {
        if (a[x % 10] > 0) {
            --a[x % 10];
        } else {
            return false;
        }
        x /= 10;
    }
    return true;
}
int main() {
    for (int i = 0; i <= 9; ++i) {
        a[i] = 2021;
    }
    int p = 1;
    while (true) {
        if (!solve(p)) break;
        p++;
    }
    cout << p - 1 << endl;
    return 0;
}

答案

C 直線

問題描述
在平面直角坐標系中，兩點可以確定一條直線，如果有多點在一條直線上，那么這些點中任意兩點確定的直線是同一條，
給定平面上 2 × 3 2 \times 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 \times 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) 之間的整數的點，請問這些點一共確定了多少條不同的直線，

題解
計算幾何？

解法一
點兩兩連線，算出 k , b k, b k,b 放進set里
（豎直和水平線另算，避免 k k k 為 0 0 0 或 ∞ \infty ∞）

#include <bits/stdc++.h>
using namespace std;
#define N 502
#define X 21
#define Y 20
struct Point {
    int x, y;
    Point() {}
    Point(int _x, int _y) : x(_x), y(_y) {}
} a[N];
int cnt_point;
struct Line {
    double k, b;
    Line() {}
    Line(double _k, double _b) : k(_k), b(_b) {}
    bool operator<(const Line &y) const {
        if (k == y.k) {
            return b < y.b;
        }
        return k < y.k;
    }
};
set<Line> e;
void addedge(Point x, Point y) {
    if (x.x == y.x || x.y == y.y) return;
    double fm = (y.x - x.x) * 1.0;
    double k = (y.y - x.y) * 1.0 / fm;
    double b = (x.y * y.x - x.x * y.y) * 1.0 / fm;
    e.insert(Line(k, b));
}
int main() {
    for (int x = 0; x < X; ++x) {
        for (int y = 0; y < Y; ++y) {
            a[cnt_point++] = Point(x, y);
        }
    }
    for (int i = 0; i < cnt_point; ++i) {
        for (int j = 0; j < cnt_point; ++j) {
            addedge(a[i], a[j]);
        }
    }
    cout << e.size() + X + Y << endl;
    return 0;
}

解法二
用 A x + B y + C = 0 Ax + By + C = 0 Ax+By+C=0
其中 A = y 1 ? y 2 , B = x 2 ? x 1 , C = x 1 y 2 ? x 2 y 1 A=y_1-y_2, B=x_2-x_1, C=x_1y_2-x_2y_1 A=y1??y2?,B=x2??x1?,C=x1?y2??x2?y1?
可以避免浮點運算導致的精度問題

注意直線 A x + B y + C = 0 Ax + By + C = 0 Ax+By+C=0 與直線 k A x + k B y + k C = 0 kAx + kBy + kC = 0 kAx+kBy+kC=0 ( k ∈ Z , k ≠ 0 ) (k∈ Z, k \neq 0) (k∈Z,k?=0) 相同，記錄時需要對 A 、 B 、 C A、B、C A、B、C 進行化簡

代碼略

答案

D 貨物擺放

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

提示：建議使用計算機編程解決問題，

題解
數論

對 n n n 分解質因數
2021041820210418 = 2 × 3 × 3 × 3 × 17 × 131 × 2857 × 5882353 2021041820210418 = 2 \times 3 \times 3 \times 3 \times 17 \times 131 \times 2857 \times 5882353 2021041820210418=2×3×3×3×17×131×2857×5882353

解法一
dfs 算方案放進 set 里

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n = 2021041820210418;
ll a[102], cnt;
struct Node {
    ll l, w, h;
    Node() {}
    Node(ll _l, ll _w, ll _h) : l(_l), w(_w), h(_h) {}
    bool operator<(const Node &y) const {
        if (l == y.l) {
            if (w == y.w) {
                return h < y.h;
            }
            return w < y.w;
        }
        return l < y.l;
    }
};
set<Node> ans;
void dfs(int p, ll l, ll w, ll h) {
    if (p == cnt) {
        ans.insert(Node(l, w, h));
        return;
    }
    dfs(p + 1, l * a[p], w, h);
    dfs(p + 1, l, w * a[p], h);
    dfs(p + 1, l, w, h * a[p]);
}
int main() {
    for (ll i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            a[cnt++] = i;
            n /= i;
            i--;
        }
    }
    a[cnt++] = n;
    dfs(0, 1, 1, 1);
    cout << ans.size() << endl;
    return 0;
}

解法二
排列組合

注意到有 3 3 3 個 3 3 3
3 5 × ( 1 + 2 + 2 + 2 + 3 ) ＝ 2430 3 ^ 5 \times (1+2+2+2+3)＝2430 35×(1+2+2+2+3)＝2430

答案

E 路徑

問題描述
小藍學習了最短路徑之后特別高興，他定義了一個特別的圖，希望找到圖中的最短路徑，
小藍的圖由 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 之間的最短路徑長度是多少，

提示：建議使用計算機編程解決問題，

題解
圖論

解法一
根據題意建邊，跑最短路， Dijkstra 即可

#include <bits/stdc++.h>
#define N 2022
#define M 100005
#define INF 0x3f3f3f3f
using namespace std;
int gcd(int x, int y) { return (x % y) ? gcd(y, x % y) : y; }
int lcm(int x, int y) { return x / gcd(x, y) * y; }
struct Edge {
    int v, w, nxt;
} e[M];
int head[N], cnt;
void addedge(int u, int v, int w) {
    e[++cnt].v = v;
    e[cnt].w = w;
    e[cnt].nxt = head[u];
    head[u] = cnt;
}
struct Node {
    int u, d;
    Node() {}
    Node(int _u, int _d) : u(_u), d(_d) {}
    bool operator<(const Node &x) const { return d > x.d; }
};
int dis[N];
int dijkstra(int s, int t) {
    for (int i = 1; i < N; ++i) {
        dis[i] = INF;
    }
    dis[s] = 0;
    priority_queue<Node> q;
    q.push(Node(s, 0));
    while (!q.empty()) {
        Node tmp = q.top();
        q.pop();
        int u = tmp.u, d = tmp.d;
        if (d != dis[u]) continue;
        for (int i = head[u]; i; i = e[i].nxt) {
            int v = e[i].v, w = e[i].w;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                q.push(Node(v, dis[v]));
            }
        }
    }
    return dis[t];
}
int main() {
    for (int i = 1; i < N; ++i) {
        for (int j = 1; j < N; ++j) {
            if (abs(i - j) <= 21) {
                addedge(i, j, lcm(i, j));
            }
        }
    }
    cout << dijkstra(1, 2021) << endl;
    return 0;
}

解法二
用 Floyd 跑最短路
雖然時間復雜度為 O ( n 3 ) O(n^3) O(n3) ，但是代碼比 Dijkstra 短得多啊！
有寫 Dijkstra 的時間 Floyd 早就跑完了

代碼略

答案

10266837

編程題

F 時間顯示

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

輸入格式
輸入一行包含一個整數，表示時間，
輸出格式
輸出時分秒表示的當前時間，格式形如 H H : M M : S S HH:MM:SS HH:MM: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，

樣例輸入 1

46800999

樣例輸出 1

13:00:00

樣例輸入 2

1618708103123

樣例輸出 2

01:08:23

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

題解
模擬

注意 1 1 1 秒 = 1000 =1000 =1000 毫秒

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n;
ll hh, mm, ss;
int main() {
    scanf("%lld", &n);
    n /= 1000;
    ss = n % 60;
    n /= 60;
    mm = n % 60;
    n /= 60;
    hh = n % 24;
    printf("%02lld:%02lld:%02lld\n", hh, mm, ss);
    return 0;
}

G 砝碼稱重

問題描述
你有一架天平和 N N N 個砝碼，這 N N N 個砝碼重量依次是 W 1 , W 2 , ? ? , W N W_1, W_2,\cdots, W_N W1?,W2?,?,WN?，請你計算一共可以稱出多少種不同的重量？
注意砝碼可以放在天平兩邊，

輸入格式
輸入的第一行包含一個整數 N N N，
第二行包含 N N N 個整數： W 1 , W 2 , W 3 , ? ? , W N W_1, W_2, W_3,\cdots, W_N W1?,W2?,W3?,?,WN?，
輸出格式
輸出一個整數代表答案，

樣例輸入

3
1 4 6

樣例輸出

樣例說明
能稱出的 10 10 10 種重量是： 1 、 2 、 3 、 4 、 5 、 6 、 7 、 9 、 10 、 11 1、2、3、4、5、6、7、9、10、11 1、2、3、4、5、6、7、9、10、11，
1 = 1 1 = 1 1=1；
2 = 6 ? 4 2 = 6 ? 4 2=6?4 (天平一邊放 6 6 6，另一邊放 4 4 4)；
3 = 4 ? 1 3 = 4 ? 1 3=4?1；
4 = 4 4 = 4 4=4；
5 = 6 ? 1 5 = 6 ? 1 5=6?1；
6 = 6 6 = 6 6=6；
7 = 1 + 6 7 = 1 + 6 7=1+6；
9 = 4 + 6 ? 1 9 = 4 + 6 ? 1 9=4+6?1；
10 = 4 + 6 10 = 4 + 6 10=4+6；
11 = 1 + 4 + 6 11 = 1 + 4 + 6 11=1+4+6，

評測用例規模與約定
對于 50 % 50\% 50% 的評測用例， 1 ≤ N ≤ 15 1 \leq N \leq 15 1≤N≤15，
對于所有評測用例， 1 ≤ N ≤ 100 1 \leq N \leq 100 1≤N≤100， N N N 個砝碼總重不超過 100000 100000 100000，

題解
dp

解法一 （可能會超時）
對于砝碼 i i i ，在使用砝碼 1 1 1 到砝碼 i ? 1 i-1 i?1 能稱出的重量的基礎上，可以選擇將其放在天平左邊或者右邊
規定砝碼放在左邊為正，放在右邊為負

用 set 記錄所有能稱出的重量
最后再取絕對值去重
注意 0 0 0 不算

#include <bits/stdc++.h>
#define N 102
#define MAX_WEIGHT 100005
using namespace std;
int n, w[N], sum_weight, ans;
set<int> st, st2;
bool vis[MAX_WEIGHT];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &w[i]);
        sum_weight += w[i];
    }
    st.insert(0);
    st2.insert(0);
    for (int i = 0; i < n; ++i) {
        for (set<int>::iterator iter = st.begin(); iter != st.end(); ++iter) {
            st2.insert((*iter) + w[i]);
            st2.insert((*iter) - w[i]);
        }
        st = st2;
    }
    for (set<int>::iterator iter = st.begin(); iter != st.end(); ++iter) {
        vis[abs(*iter)] = true;
    }
    for (int i = 1; i <= sum_weight; ++i) {
        if (vis[i]) {
            ++ans;
        }
    }
    printf("%d\n", ans);
}

解法二
d p [ i ] [ j ] dp[i][j] dp[i][j] 表示前 i i i 個物品，若能稱出重量 j j j 則為 1 1 1 ，反之為 0 0 0
對于 j j j 為負數的情況可以對初始重量 0 0 0 進行偏移
因為砝碼總重不超過 100000 100000 100000 ，偏移量 200000 200000 200000 即可

狀態轉移方程如下
d p [ i ] [ j ] = { d p [ i ] [ j ] ∣ ∣ d p [ i ? 1 ] [ j ] 不放砝碼 i d p [ i ] [ j ] ∣ ∣ d p [ i ? 1 ] [ j ? w i ] 砝碼 i 放左邊 d p [ i ] [ j ] ∣ ∣ d p [ i ? 1 ] [ j + w i ] 砝碼 i 放右邊 dp[i][j] = \begin{cases} dp[i][j] \ || \ dp[i-1][j]& \text{不放砝碼 $i$ }\\ dp[i][j] \ || \ dp[i-1][j-w_i]& \text{砝碼 $i$ 放左邊}\\ dp[i][j] \ || \ dp[i-1][j+w_i]& \text{砝碼 $i$ 放右邊} \end{cases} dp[i][j]=??????dp[i][j] ∣∣ dp[i?1][j]dp[i][j] ∣∣ dp[i?1][j?wi?]dp[i][j] ∣∣ dp[i?1][j+wi?]?不放砝碼 i 砝碼 i 放左邊砝碼 i 放右邊?
其中 || 為或運算

#include <bits/stdc++.h>
#define N 102
#define MAX_WEIGHT 100005
using namespace std;
int n, m, k, w[N], sum_weight, ans;
bool dp[N][MAX_WEIGHT << 2];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &w[i]);
        sum_weight += w[i];
    }
    dp[0][sum_weight * 2] = true;
    for (int i = 1; i <= n; ++i) {
        for (int j = sum_weight; j <= sum_weight * 3; ++j) {
            dp[i][j] = dp[i][j] || dp[i - 1][j] || dp[i - 1][j - w[i]] || dp[i - 1][j + w[i]];
        }
    }
    for (int i = 1; i <= sum_weight; ++i) {
        if (dp[n][sum_weight + i] || dp[n][sum_weight - i]) {
            ++ans;
        }
    }
    printf("%d\n", ans);
    return 0;
}

H 楊輝三角形

問題描述
下面的圖形是著名的楊輝三角形：

如果我們按從上到下、從左到右的順序把所有數排成一列，可以得到如下數列：
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，
輸出格式
輸出一個整數代表答案，

樣例輸入

樣例輸出

評測用例規模與約定
對于 20 % 20\% 20% 的評測用例， 1 ≤ N ≤ 10 1 \leq N \leq 10 1≤N≤10；
對于所有評測用例， 1 ≤ N ≤ 1000000000 1 \leq N \leq 1000000000 1≤N≤1000000000，

題解
注意到有 n = C n 1 n = C_n^1 n=Cn1? ，即 n n n 必然會出現在第 n + 1 n+1 n+1 行第 2 2 2 列的位置上

若不存在 n = C i j , j ≤ i n = C_i^j , j \leq i n=Cij?,j≤i 且 n < C p 2 , i ≤ p < n n < C_p^2, i \leq p<n n<Cp2?,i≤p<n ，則 n n n 只可能在 C n 1 C_n^1 Cn1? 的位置
即前 p + 1 p+1 p+1 行沒有出現 n n n 且第 p + 1 p+1 p+1 行第三列大于 n n n 的時候就可以直接判斷 n n n 第一次出現在第 n + 1 n+1 n+1 行第 2 2 2 列

暴力列舉前 p + 1 p+1 p+1 行（每行的前一半就行了）
最壞情況下 p p p 需要列舉到 44722 44722 44722 ( C 44722 2 = 1 , 000 , 006 , 281 C_{44722}^2 = 1,000,006,281 C447222?=1,000,006,281 )

#include <bits/stdc++.h>
#define ll long long
#define N 100005
using namespace std;
ll n, c[N], p, q;
bool flag;
int main() {
    scanf("%lld", &n);
    if (n == 1) { //特判 1
        printf("1\n");
        return 0;
    }
    c[0] = c[1] = 1;
    p = 1;
    while (c[2] < n) {
        ++p;
        for (int i = p / 2 + 1; i > 0; --i) {
            c[i] += c[i - 1];
        }
        c[p] = 1;
        q = lower_bound(c, c + p / 2, n) - c;
        if (c[q] == n) {
            flag = true;
            break;
        }
    }
    if (flag) {
        printf("%lld\n", (1 + p) * p / 2ll + q + 1ll);
    } else {
        printf("%lld\n", (1 + n) * n / 2ll + 2ll);
    }
    return 0;
}

I 雙向排序

問題描述
給定序列 ( a 1 , a 2 , ? ? , a n ) = ( 1 , 2 , ? ? , n ) (a_1, a_2,\cdots, a_n) = (1, 2,\cdots, 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,\cdots, a_{q_i} a1?,a2?,?,aqi?? 降序排列，或者將 a q i , a q i + 1 , ? ? , a n a_{q_i}, a_{q_{i+1}},\cdots, a_n aqi??,aqi+1??,?,an? 升序排列，
請求出操作完成后的序列，

輸入格式
輸入的第一行包含兩個整數 n , m n, m n,m，分別表示序列的長度和操作次數，接下來 m m m 行描述對序列的操作，其中第 i i i 行包含兩個整數 p i p_i pi?, q i q_i qi? 表示操作型別和引數，當 p i = 0 p_i = 0 pi?=0 時，表示將 a 1 , a 2 , ? ? , a q i a_1, a_2,\cdots, 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}},\cdots, a_n aqi??,aqi+1??,?,an? 升序排列，
輸出格式
輸出一行，包含 n n n 個整數，相鄰的整數之間使用一個空格分隔，表示操作完成后的序列，

樣例輸入

樣例輸出

3 1 2

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

評測用例規模與約定
對于 30 % 30\% 30% 的評測用例， n , m ≤ 1000 n, m \leq 1000 n,m≤1000；
對于 60 % 60\% 60% 的評測用例， n , m ≤ 5000 n, m \leq 5000 n,m≤5000；
對于所有評測用例， 1 ≤ n , m ≤ 100000 ， 0 ≤ p i ≤ 1 ， 1 ≤ q i ≤ n 1 \leq n, m \leq 100000，0 \leq p_i \leq 1，1 \leq q_i \leq n 1≤n,m≤100000，0≤pi?≤1，1≤qi?≤n，

題解
暴力 sort ，時間復雜度 O ( m n log ? n ) O(mn \log n) O(mnlogn) ，拿 60 % 60\% 60% 分

正解暫無

#include <bits/stdc++.h>
#define N 100005
using namespace std;
int n, m;
int a[N], p[N], q[N];
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        a[i] = i;
    }
    for (int i = 1; i <= m; ++i) {
        scanf("%d%d", &p[i], &q[i]);
        if (p[i]) {
            sort(a + q[i], a + n + 1);
        } else {
            sort(a + 1, a + q[i] + 1, greater<int>());
        }
    }
    for (int i = 1; i <= n; ++i) {
        printf(" %d" + !(i - 1), a[i]);
    }
    printf("\n");
    return 0;
}

J 括號序列

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

輸入格式
輸入一行包含一個字串 s s s，表示給定的括號序列，序列中只有左括號和右括號，
輸出格式
輸出一個整數表示答案，答案可能很大，請輸出答案除以 1000000007 1000000007 1000000007 (即 1 0 9 + 7 10^9 + 7 109+7) 的余數，

樣例輸入

((()

樣例輸出

評測用例規模與約定
對于 40 % 40\% 40% 的評測用例， ∣ s ∣ ≤ 200 \lvert s \rvert \leq 200 ∣s∣≤200，
對于所有評測用例， 1 ≤ ∣ s ∣ ≤ 5000 1 \leq \lvert s \rvert \leq 5000 1≤∣s∣≤5000，

題解
特判合法括號序列輸出 0 0 0
特判樣例騙分

正解暫無

#include <bits/stdc++.h>
using namespace std;
string s;
int cnt;
bool flag = true;
int main() {
    cin >> s;
    for (int i = 0; i < s.length(); ++i) {
        if (s[i] == '(') {
            ++cnt;
        } else {
            if (cnt <= 0) {
                flag = false;
                break;
            }
            --cnt;
        }
    }
    if (cnt) {
        flag = false;
    }
    if (flag) {
        printf("0\n");
    } else {
        if (s == "((()") {
            printf("5\n");
        } else {
            printf("%d\n", s.length());
        }
    }
    return 0;
}

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

標籤：其他

上一篇：2021年第十二屆藍橋杯省賽B組C/C++部分填空題解

下一篇：2021 第十二屆藍橋杯 Java 省賽 B 組（第一場）真題 + 填空題決議

第十二屆藍橋杯 2021年4月省賽第一場 C/C++ B組題解

目錄

填空題

A 空間

B 卡片

C 直線

D 貨物擺放

E 路徑

編程題

F 時間顯示

G 砝碼稱重

H 楊輝三角形

I 雙向排序

J 括號序列

第十二屆藍橋杯 2021年4月 省賽 第一場 C/C++ B組 題解

目錄

填空題

A 空間

B 卡片

C 直線

D 貨物擺放

E 路徑

編程題

F 時間顯示

G 砝碼稱重

H 楊輝三角形

I 雙向排序

J 括號序列

第十二屆藍橋杯 2021年4月省賽第一場 C/C++ B組題解