ACGO 排位赛#10 - 题目解析

自我反省：确实这次比赛没考好（问题不大，至少排位分没掉）。

第一题 - A24630.ASCII 码

题目链接跳转：A24630.ASCII 码

直接用 C++ 内置的类型转换工具就可以了，(char) 可以将任意的数字转换成一个字符（其实字符底层就是用数字存储的）。

本题的 AC 代码如下：

#include <iostream>
using namespace std;

int main(){
    int n;
    cin >> n;
    cout << (char)n << endl;
	return 0;
}

第二题 - A24631.挑食的小码君

题目链接跳转：A24631.挑食的小码君

做题思路：遍历两遍，第一次遍历通过 maxi 变量记录这些食物中最大的美味值。之后遍历小码君所有不喜欢的食物，判断某项食物的美味值是否等于 maxi。

代码很简单，本题的 AC 代码如下：

#include <iostream>
using namespace std;

int n, k, maxi;
int arr[105];

int main(){
    cin >> n >> k;
    for (int i=1; i<=n; i++){
        cin >> arr[i];
        maxi = max(maxi, arr[i]);
    }
    for (int i=1, t; i<=k; i++){
        cin >> t;
        if (arr[t] == maxi){
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
    return 0;
}

第三题 - A24632.奇怪的机器

题目链接跳转：A24632.奇怪的机器

数据量不大，直接模拟和暴力枚举就行了。枚举全部数字变成 $k$ 所需要花费的最少时间。

在枚举的过程中需要注意的是，由于在一秒之内小码君只能按下一个按钮，因此如果一个数字 $a$ 在某一列出现了 $x$ 次，那么当枚举 $k=a$ 的时候，需要多经过 $(x - 1) \times 10$ 轮才可以把这些转盘（在同一列都出现了 $x$ 次）变成相同的数字。

本题的 AC 代码如下：

#include <iostream>
#include <algorithm>
using namespace std;

int n, result = 0x7f7f7f7f;
string arr[105];

int query(int pos, int num){
    int ans = 0;
    for (int i=1; i<=n; i++){
        if (arr[i][pos] == num + '0')
            ans += 1;
    }
    return ans;
}

signed main(){
    cin >> n;
    for (int i=1; i<=n; i++) cin >> arr[i];
    // 暴力枚举：枚举全都变成数字 $k$ 所需要花费的最小时间。
    for (int k=0; k<=9; k++){
        int ans = 0;
        for (int i=1; i<=n; i++){
            // 查询某个数在某一列出现了几次。
            int tmp = query(arr[i].find(k + '0'), k);
            int time = (tmp - 1) * 10 + arr[i].find(k + '0');
            ans = max(time, ans);
        }
        result = min(result, ans);
    }
    cout << result << endl;
}

第四题 - A24633.独特三元组

题目链接跳转：A24633.独特三元组

这道题有很多做法，这里提供一个基于排列组合的算法。

假设有 $N$ 个元素，且每个元素各不相同，那么满足题目要求的三元组数量就是这 $N$ 个元素中任意取 $3$ 个元素的组合。也就是 $\binom{n}{3} = n \times (n-1) \times (n-2) / 1$​。

如果有重复的元素呢？我们只需要把重复的元素再“去除”掉就行。

具体地说，如果某个元素的出现次数 arr[i] 大于等于 $3$，则可以从这些重复的元素中选出三个元素组成一个三元组 $(A_i,A_i,A_i)$，这是不符合条件的，因此再删除掉这些重复元素的组合数即可。即 $\binom{arr[i]}{3}$。

如果某个元素的出现次数 arr[i] 大于等于 $2$，则可以从这些重复的元素中选出两个元素，再从数组中的其他元素中选出一个不同的元素组成三元组 $(A_i,A_i,A_j)$，其中 $A_i \neq A_j$，即 $\binom{arr[i]}{2}$​。

最后本题的 AC 代码如下：

#include <iostream>
#include <algorithm>
#include <cstring>
#define int long long
using namespace std;

const int N = 2e5 + 5;
int n, ans, arr[N];

signed main(){
    cin >> n;
    ans = n * (n-1) * (n-2) / 6;
    for (int i=1, t; i<=n; i++){
        cin >> t;
        arr[t] += 1;
    }
    for (int i=1; i<=N-1; i++){
        int p1 = 0, p2 = 0;
        if (arr[i] == 0) continue;
        if (arr[i] >= 3) p1 = arr[i] * (arr[i] - 1) * (arr[i] - 2) / 6;
        if (arr[i] >= 2) p2 = (n - arr[i]) * arr[i] * (arr[i] - 1) / 2;
        ans -= p1 + p2;
    }
    cout << ans << endl;
    return 0;
}

第五题 - A24634.道路削减

题目链接跳转：A24634.道路削减

前言：刚开始看这道题目的时候看成了最小生成树的模板题目，盲目的 wsq 随手打了一篇最小生成树的代码交上去，荣获满堂红（葬送了好多次提交记录，真是个悲惨的事情）。

最短路树的模板题目，在 Dijkstra 求最短路径的基础上，记录每一个顶点的“前驱边”就行了。更进一步地，如果松弛了某一条边 $E(A, B)$，可以使得从源点到达 $B$ 点的最短距离缩短，那么就保留这一条边（覆盖掉原本通往 $B$ 点的前驱边即可，一开始没有可以设置为无穷大或者是一个无意义的数字）。可以证明，如果有 $N$ 个顶点，排除源点，当每一个顶点都有一个前驱边时，图上正好只有 $N-1$ 条边。且每一个点到源点的距离都是最小的。

PS：本题的数据量比较大，一定要开 long long 数据类型，同时在计算最短路初始化的时候，切记无穷大要开的大一点。

本题的 AC 代码如下：

#include <iostream>
#include <queue>
#include <algorithm>
#include <unordered_map>
#define int unsigned long long
using namespace std;

const int M = 2e5 + 10;
int n, m, ei, vertex[M];
struct node{
    int to, next;
    int weight, id;
} edges[M * 2];
struct Node {
    int vertex, distance;
    bool operator>(const Node& other) const {
        return distance > other.distance;
    }
};
int dis[M], fa[M], road[M];

void add(int v1, int v2, int weight, int id){
    ei += 1;
    edges[ei].to = v2;
    edges[ei].weight = weight;
    edges[ei].next = vertex[v1];
    edges[ei].id = id;
    vertex[v1] = ei;
}

void dijkstra(){
    for (int i=1; i<=n; i++){
        dis[i] = 1e15;
        fa[i] = -1;
    }
    dis[1] = 0;
    priority_queue<Node, vector<Node>, greater<Node>> que;
    que.push((Node){1, 0});
    while(que.size()){
        Node t = que.top();
        que.pop();
        int u = t.vertex;
        if (t.distance > dis[u]) continue;
        for (int index=vertex[u]; index; index=edges[index].next){
            int v = edges[index].to;
            int weight = edges[index].weight;
            if (dis[u] + weight < dis[v]){
                dis[v] = dis[u] + weight;
                fa[v] = u;
                road[v] = edges[index].id;
                que.push((Node){v, dis[v]});
            }
        }
    }
    return ;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i=1, u, v, w; i<=m; i++){
        cin >> u >> v >> w;
        add(u, v, w, i); add(v, u, w, i);
    }
    dijkstra();
    for (int i=1; i<=n; i++) {
        if (i != 1 && fa[i] != -1) {
            cout << road[i] << " ";
        }
    }
    return 0;
}

第六题 - A24635.分面包

题目链接跳转：A24635.分面包

这道题正着思考比较麻烦，但可以反着思考（选择从小面包逐步拼成大面包，而不是从大面包逐步切割成小面包）。不难发现反着思考后就是一个典型的贪心问题（哈夫曼树）。假设现在有 $N$ 块长度不一的小面包，那么将这些小面包合并成稍大一些的面包的最优策略就是选择剩下的小面包中长度最短的两块进行合并。每次合并的代价是两个面包的长度之和。通过这种方式，可以确保每次合并的代价最小，从而最终达到最小的总花费。

为了实现这个过程，我们可以使用一个优先队列（最小堆）来维护当前所有待合并的面包。每次从队列中取出两个长度最小的面包进行合并，并将合并后的新面包重新加入到队列中。如此反复，直到队列中只剩下一个面包。

接下来，考虑如何处理“每个孩子 $i$ 必须收到一个长度正好为 $A_i$ 的面包”这个要求。如果原始面包长度 $L$ 大于这些长度之和，则将多余的部分 $L - \sum A_i$ 也加入到队列中。代表“多出来的部分”也需要被单独分割出来。

本题的 AC 代码如下：

#include <iostream>
#include <queue>
using namespace std;
#define int long long

int L, N, sum;
priority_queue<int, vector<int>, greater<int> > que;

void solve(){
    int total = 0;
    bool flag = 1;
    if (L != sum)
        que.push(L - sum);
    while(que.size() > 1){
        int a = que.top(); que.pop();
        int b = que.top(); que.pop();
        total += a + b;
        que.push(a + b);
    }
    cout << total << endl;
    return ;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> N >> L;
    for (int i=1, t; i<=N; i++){
        cin >> t;
        sum += t;
        que.push(t);
    }
    solve();
    return 0;
}