指导老师：毛明松
编撰：衷铭川（大数据 231 班，程设协会负责人）
友链：其实连按部就班也比想象中难
江西财经大学信息管理与数学学院编程会、计算机与人工智能学院程序设计竞赛协会

# 数据结构训练的意义

在蓝桥杯竞赛中，数据结构训练具有重要的意义。数据结构是算法的基础，掌握常见的数据结构是解决复杂问题的关键。在比赛中，时间和空间复杂度是评分的重要标准之一。通过数据结构训练，可以学会如何选择最优的数据结构来减少时间和空间的开销，从而在比赛中取得更好的成绩。

# 题目

题目集链接：https://vjudge.net/contest/702049
题目集密码：$duoxichangan$
$VJ$ 比较抽象，可能需要～～ 魔法～～科学上网
排行榜链接：https://vjudge.net/contest/702049#rank

# Card Pile

有一叠 $100$ 纸牌，每张都标有整数 $0$ 。
处理 $Q$ 个查询。每个查询都属于以下情况之一：

• 输入 $1$ ：将一张标有整数 $x$ 的卡片放在堆栈顶部。
• 类型 $2$ ：取出牌堆顶端的卡片，并输出写在该卡片上的整数。在此问题的限制条件下，牌堆中总是至少有一张牌。

# 题解

纯粹考栈的操作，会栈 $stack$ 就会写的题目，无需多言。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

void solve () {
    int q;
    cin >> q;
    stack<int> s;

    for (int i = 1; i <= 100; i++)
        s.push(0);

    while (q--) {
        int op, x;
        cin >> op;

        if (op == 2) {
            cout << s.top() << endl;
            s.pop();
        }
        else {
            cin >> x;
            s.push(x);
        }
    }
}

# 约瑟夫问题

# 题目大意

$n$ 个人围成一圈，从第一个人开始报数，数到 $m$ 的人出列，再由下一个人重新从 $1$ 开始报数，数到 $m$ 的人再出圈，依次类推，直到所有的人都出圈，请输出依次出圈人的编号。

# 数据范围

$1 \le m, n \le 100$

# 题解

这题其实也可以变成大模拟，但是这是数据结构专题，这种题目应该用 $queue$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

int n, m;

void solve () {
    cin >> n >> m;
    queue<int> q;
    for (int i = 1; i <= n; i++)
        q.push(i);

    int cnt = 0, t;

    while (!q.empty()) {
        cnt++, t = q.front(), q.pop();
        
        if (cnt % m == 0) {
            cout << t << " ";
            continue;
        }

        q.push(t);
    }
}

# Variety Split

# 题目大意

给你一个长度为 $N$ 的整数序列： $A = (A_1, A_2, ..., A_N)$ .
当在一个位置将 $A$ 分割成两个非空 (连续) 子数组时，请找出这些子数组中不同整数计数的最大可能和。
更正式地说，求整数 $i$ 的以下两个值的最大和： $(A_1, A_2, ..., A_i)$ 中的不同整数计数，以及 $(A_{i+1}, A_{i+2}, ..., A_N)$ 中的不同整数计数。

# 数据范围

• $2 \le N \le 3 \times 10^5$
• $1 \le A_i \le N$ ($1 \le i \le N$)

# 题解

用 $map$ 分别记录两边出现过什么数。
$l,r$ 分别记录左边、右边出现过什么数。$cntLeft,cntRight$ 记录左边、右边数的个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

int n, a[N];

map<int, int> l, r;
int cntLeft = 0, cntRight = 0;
int res = 0;

void solve () {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];

        if (!r[a[i]])
            cntRight++;
        r[a[i]]++;
    }

    for (int i = 1; i < n; i++) {
        if (l[a[i]] == 0)
            cntLeft++;
        l[a[i]]++, r[a[i]]--;
        if (r[a[i]] == 0)
            cntRight--;
        res = max(cntLeft + cntRight, res);
    }

    cout << res << endl;
}

# 【模板】单调栈

# 题目大意

给出项数为 $n$ 的整数数列 $a_{1 \dots n}$。
定义函数 $f(i)$ 代表数列中第 $i$ 个元素之后第一个大于 $a_i$ 的元素的下标，即 $f(i)=\min_{i<j\leq n, a_j > a_i} \{j\}$. 若不存在，则 $f(i)=0$。试求出 $f(1\dots n)$.

# 输入格式

第一行一个正整数 $n$。
第二行 $n$ 个正整数 $a_{1\dots n}$。

# 输出格式

一行 $n$ 个整数表示 $f(1), f(2), \dots, f(n)$ 的值。

# 数据范围

对于 $30\%$ 的数据，$n\leq 100$.
对于 $60\%$ 的数据，$n\leq 5 \times 10^3$.
对于 $100\%$ 的数据，$1 \le n\leq 3\times 10^6$，$1\leq a_i\leq 10^9$.

# 题解

维护一个单调递减的栈 $s$

• 对于当前元素  a[i]
  • 如果栈  s  不为空且栈顶元素对应的值  a[s.top()]  小于等于  a[i] ，则弹出栈顶元素，从而保证了栈  s  中的元素始终是单调递减的。
  • 如果栈  s  为空，说明当前元素  a[i]  没有右边比它大的。
  • 如果栈  s  不为空，说明栈顶元素对应的值  a[s.top()]  是当前元素  a[i]  右边第一个比它大的元素
    

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

    int n, a[N]; void solve () { cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; stack<int> s, res; for (int i = n; i >= 1; i--) { while (!s.empty() && a[i] >= a[s.top()]) s.pop(); if (s.empty()) res.push(0); else res.push(s.top()); s.push(i); } while (!res.empty()) cout << res.top() << " ", res.pop(); }

# 【模板】并查集

# 题目大意

如题，现在有一个并查集，你需要完成合并和查询操作。

# 输入格式

第一行包含两个整数 $N,M$ ，表示共有 $N$ 个元素和 $M$ 个操作。
接下来 $M$ 行，每行包含三个整数 $Z_i,X_i,Y_i$.
当 $Z_i=1$ 时，将 $X_i$ 与 $Y_i$ 所在的集合合并。
当 $Z_i=2$ 时，输出 $X_i$ 与 $Y_i$ 是否在同一集合内，是的输出 Y ；否则输出 N .

# 输出格式

对于每一个 $Z_i=2$ 的操作，都有一行输出，每行包含一个大写字母，为 Y 或者 N .

# 数据范围

对于 $50\%$ 的数据，$1\le N \le 10^4$，$1\le M \le 2\times 10^5$。
对于 $100\%$ 的数据，$1\le N\le 2\times 10^5$，$1\le M\le 10^6$，$1 \le X_i, Y_i \le N$，$Z_i \in \{ 1, 2 \}$.

# 题解

并查集模板题，如果不懂并查集的可以参考：一个并查集的知乎教程。
注意，此题不能用简单的、不经任何优化的并查集，不然你会喜提 $TLE$，得用路径压缩后的并查集。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

int n, m, z, x, y, f[N];

int find(int x) {
    return f[x] = (f[x] != x ? find(f[x]) : x);
}

void solve () {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        f[i] = i;

    for (int i = 1; i <= m; i++) {
        cin >> z >> x >> y;
        if (z == 1)
            f[find(y)] = find(x);
        else
            cout << (find(x) == find(y) ? "Y" : "N") << endl;
    }
}

# Max × Sum

# 题目大意

给定一个长度为 $N$ 的序列： $A = (A_1, A_2, ..., A_N)$ 和 $B = (B_1, B_2, ..., B_N)$ 。
设 $S$ 是大小为 $K$ 的 $\lbrace1, 2, \dots, N\rbrace$ 的子集。求以下表达式的最小可能值：

$$(\max_{i \in S} A_i) \times (\sum_{i \in S} B_i)$$

给你 $T$ 个测试用例，请逐个求解。

# 数据范围

• $1 \le T \le 2 \times 10^5$
• $1 \le K \le N \le 2 \times 10^5$
• $1 \le A_i, B_i \le 10^6$

# 题解

将 $A$ 序列按从小到大的顺序排。
排完序之后，显然，$A_i~(i \in [1,k-1])$ ，不可能会被选上
那么我们只需要从 $A_k$ 枚举到 $A_n$，这个范围内都是满足题意的、可以被选的 $A_i$.

那么问题来了？$\sum_{i \in S} B_i$ 怎么办呢？
我们可以用优先队列维护，先将前 $B_1 \to B_{k-1}$，$push$ 进队列并用一个 sum 累加和。
而对于可以选择的 $A_i,(i \in [k, n])$，当 $A_i$ 被选中时，$B_i$ 即要加入和，那么这时会有两种情况：

• heap.size() == k
  • 那么我们就要先弹出一个最大的来，代表不选它。
• heap.size() == k - 1
  • 直接 $push$ 进队列，算新的和即可。
    描述思路有点抽象，可以结合代码理解。
    

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

    #define int long long using namespace std; typedef pair<int, int> PII; const int N = 2e5 + 10; int n, k; PII num[N]; bool cmp(PII x, PII y) { return x.first < y.first; } void solve () { cin >> n >> k; for (int i = 1; i <= n; i++) cin >> num[i].first; for (int i = 1; i <= n; i++) cin >> num[i].second; sort(num + 1, num + n + 1, cmp); priority_queue<int> heap; int ans = LONG_LONG_MAX, sum = 0; for (int i = 1; i <= k - 1; i++) { heap.push(num[i].second); sum += num[i].second; } for (int i = k; i <= n; i++) { if (heap.size() == k) { sum -= heap.top(); heap.pop(); } heap.push(num[i].second), sum += num[i].second; ans = min(ans, sum * num[i].first); } cout << ans << endl; }