2021 RoboCom 世界机器人开发者大赛-本科组（初赛）

7-1 懂的都懂

众所周知，在互联网上有很多话是不好直接说出来的，不过一些模糊的图片仍然能让网友看懂你在说什么。然而对这种言论依然一定要出重拳，所以请你实现一个简单的匹配算法。

现在我们采集了原图的一些特征数据，由 N 个小于 255 的非负整数组成，假设对于给定的若干张由 M_i 个同样小于 255 的非负整数组成的新图的特征数据，每个数据都可以由原图中任意四个不同数据的平均值计算而来，则称新图为原图的相似图片。对于给出的数据，请你判断是不是相似图片。

注意，不同数据指的并非是数据的值不同，而是不能取同一个数据多次。对于两个相同值的数据，如果给出两次，则可以取两次。

输入格式:

输入第一行是两个整数 N,K (1 ≤ N ≤ 50, 1 ≤ K ≤ 200)，表示采集的原图的特征数据个数和新图的张数。

接下来一行为 N 个小于 255 的非负整数，表示原图的特征数据。

最后的 K 行，每行第一个数是 M_i (1 ≤ M_i ≤ 200)，表示新图的特征数据个数。然后是 M_i 个小于 255 的非负整数，表示新图的特征数据。

输出格式:

对于每一张新图，如果为相似图片，则在一行中输出 Yes，否则输出 No。

输入样例:

5 3
4 8 12 20 40
3 11 16 19
3 12 16 19
10 11 11 11 11 11 11 11 11 11 11

输出样例:

Yes
No
Yes

解题：暴力模拟哈希表

思路

把原图中任意四个不同数据的和的所有可能枚举出来，存在一个不重复集合(sums)中。

然后对于每一个新图，其中每个数据*4都存在于 sums 中则该图为原图的相似图片，输出 "Yes"。如果新图有任一个数据*4不存在于 sums 中，则输出 “No”，并跳过该图之后的数据取判断下一张图。

代码

#include <iostream>
#include <unordered_set>
#include <limits>

using namespace std;

int main() {
    int N, K;
    scanf("%d%d", &N, &K);
    int ori[N];
    for (int i = 0; i < N; i++) scanf("%d", &ori[i]);
    unordered_set<int> sums;
    for (int i = 0; i < N; i++) {
        for (int j = i + 1; j < N; j++) {
            for (int k = j + 1; k < N; k++) {
                for (int l = k + 1; l < N; l++) {
                    sums.insert(ori[i] + ori[j] + ori[k] + ori[l]);
                }
            }
        }
    }
    int M, m;
    while (K--) {
        scanf("%d", &M);
        while (M--) {
            scanf("%d", &m);
            if (sums.count(m * 4) == 0) {
                printf("No\n");
                cin.ignore(numeric_limits<streamsize>::max(), '\n');
                goto out;
            }
        }
        printf("Yes\n");
        out:;
    }

    return 0;
}

使用布尔数组代替哈希表

#include <iostream>
#include <limits>

using namespace std;

int main() {
    int N, K;
    scanf("%d%d", &N, &K);
    int ori[N];
    for (int i = 0; i < N; i++) scanf("%d", &ori[i]);
    bool hasSum[1100] = {false};
    for (int i = 0; i < N; i++) {
        for (int j = i + 1; j < N; j++) {
            for (int k = j + 1; k < N; k++) {
                for (int l = k + 1; l < N; l++) {
                    hasSum[ori[i] + ori[j] + ori[k] + ori[l]] = true;
                }
            }
        }
    }
    int M, m;
    while (K--) {
        scanf("%d", &M);
        while (M--) {
            scanf("%d", &m);
            if (!hasSum[m * 4]) {
                printf("No\n");
                cin.ignore(numeric_limits<streamsize>::max(), '\n');
                goto out;
            }
        }
        printf("Yes\n");
        out:;
    }

    return 0;
}

7-2 芬兰木棋

芬兰木棋（Mölkky，又称芬兰木柱）是源自芬兰的一项运动。哲哲将这个运动改造成了赛博朋克单人版，现在场上一开始有 N 根立起的小木棋（上面分别标有一个非负整数），哲哲投掷一根大木棋去击倒这些小木棋以获得分数。分数规则如下：

如果仅击倒 1 根木棋，则得木棋上的分数。
如果击倒 2 根或以上的木棋，则只得击倒根数的分数。（例如击倒 5 根，则得 5 分。）

哲哲固定站在 (0,0) 点上，四周放着若干个小木棋 (X_i,Y_i)，坐标均为整数。每次哲哲可以朝一个方向扔出大木棋，大木棋会打倒这个方向上离哲哲最近的 k 个小木棋。哲哲游戏水平很高超，所以这个 k 可以自由控制。

请问哲哲最多能拿多少分，在获得最多分数的情况下最少需要扔出多少次大木棋？

规则与真实规则有较大出入，真实游玩时请以国际莫尔基组织的规则为准

输入格式:

输入第一行是一个正整数 N (1 ≤ N ≤ 105)，表示场上一开始有 N 个木棋。

接下来 N 行，每行 3 个整数 X_i,Y_i,P_i，分别表示木棋放置在 (X_i,Y_i)，木棋上的分数是 P_i。坐标在 32 位整数范围内，分数为小于等于 1000 的正整数。

保证 (0,0) 点没有木棋，也没有木棋重叠放置。

输出格式:

输出一行两个数，表示最多分数以及获得最多分数最少需要投掷大木棋多少次。

输入样例:

输出样例:

1022 9

解题：数学哈希表

思路

根据规则，如果要以最少投掷拿最优分数那么就必须：

大于 1 分的木棋单根击倒。
多个连续等于 1 分的木棋一起击倒。
单个等于 1 分的木棋随意。

每次可以朝一个方向扔出大木棋，也就是说要按照方向(斜率)对小木棋进行分类(使用 unordered_map)，要找到可以连续击倒的木棋，就需要对每一个方向按照坐标进行排序(没必要考虑象限)。

用哈希表<斜率, 木棋向量> 接收数据，每对数据计算出斜率 $\frac{y}{x}$ (注意：当 x 为 0 时，斜率算出来为 null，但哈希表中可以以 null 为键，所以不用特判)，然后取出键为对应斜率的木棋向量推入木棋对象(木棋对象排序规则为坐标)。

输入完所有数据后遍历哈希表，对取出的木棋向量进行排序，然后遍历该向量，直接自增计数器，然后根据当前木棋的分数判断需不需要进行循环以找到下一个可以自增计数器的地方。

代码

#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>

using namespace std;

struct Molkky {
    int x, y, point;

    friend bool operator<(const Molkky &a, const Molkky &b) {
        return a.x != b.x ? a.x < b.x : a.y < b.y;
    }
};

int main() {
    int N;
    scanf("%d", &N);
    unordered_map<double, vector<Molkky>> mp;
    int X, Y, P, total = 0;
    while (N--) {
        scanf("%d%d%d", &X, &Y, &P);
        total += P;
        mp[Y * 1.0 / X].push_back({X, Y, P});
    }
    int count = 0;
    for (const auto &pr : mp) {
        vector<Molkky> v = pr.second;
        sort(v.begin(), v.end());
        for (int i = 0; i < v.size(); i++) {
            count++;
            if (v[i].point == 1) {
                int j = i;
                while (j < v.size() && v[j].point == 1) j++;
                j--;
                i = j;
            }
        }
    }
    printf("%d %d", total, count);

    return 0;
}

7-3 打怪升级

很多游戏都有打怪升级的环节，玩家需要打败一系列怪兽去赢取成就和徽章。这里我们考虑一种简单的打怪升级游戏，游戏规则是，给定有 N 个堡垒的地图，堡垒之间有道路相连，每条道路上有一只怪兽把守。怪兽本身有能量，手里的武器有价值。打败怪兽需要的能量等于怪兽本身的能量，而怪兽一旦被打败，武器就归玩家所有 —— 当然缴获的武器价值越高，玩家就越开心。

你的任务有两件：

帮助玩家确定一个最合算的空降位置，即空降到地图中的某个堡垒，使得玩家从这个空降点出发，到攻下最难攻克（即耗费能量最多）的那个堡垒所需要的能量最小；
从这个空降点出发，帮助玩家找到攻克任意一个其想要攻克的堡垒的最省能量的路径。如果这种路径不唯一，则选择沿途缴获武器总价值最高的解，题目保证这种解是唯一的。

输入格式:

输入第一行给出两个正整数 N (≤1000) 和 M，其中 N 是堡垒总数，M 是怪兽总数。为简单起见，我们将堡垒从 1 到 N 编号。随后 M 行，第 i 行给出了第 i 只怪兽的信息，格式如下：

B1 B2 怪兽能量 武器价值

其中 B1 和 B2 是怪兽把守的道路两端的堡垒编号。题目保证每对堡垒之间只有一只怪兽把守，并且 怪兽能量 和 武器价值 都是不超过 100 的正整数。

再后面是一个正整数 K（≤N）和玩家想要攻克的 K 个目标堡垒的编号。

输出格式:

首先在一行中输出玩家空降的堡垒编号 B0。如果有多种可能，则输出编号最小的那个。

随后依次为玩家想要攻克的每个堡垒 B 推荐最省能量的攻克路径，并列出需要耗费的能量值和沿途缴获武器的总价值。注意如果最省力的路径不唯一，则选择沿途缴获武器总价值最高的解。格式为：

B0->途经堡垒1->...->B
总耗费能量 武器总价值

输入样例:

输出样例:

5
5->2
2 1
5->1->3
12 7
5->4->6
10 7
5
0 0

解题：Floyd算法 Dijkstra算法

思路

空降位置：找出一个顶点，使得该顶点到其他顶点的最远距离最小，是多源最短路问题，所以使用 Floyd 算法求解。然后以该点为目标点，求其他顶点到该点的最短距离（单源最短路问题），直接使用 Dijkstra 算法，过程中维护一个路径数组，方便之后输出路径使用，拿到 dist 数组之后输出题目给出的点即可。

代码

#include <iostream>
#include <stack>

using namespace std;

const int MAX_N = 1001, INF = 0x3f3f3f3f;
struct Node {
    int power = INF, value = 0;
} graph[MAX_N][MAX_N];
int N, M;
int p_graph[MAX_N][MAX_N];
int fp_dist[MAX_N], dp_dist[MAX_N], dv_dist[MAX_N];
int path[MAX_N];
bool visited[MAX_N];

int floyd() {
    for (int k = 1; k <= N; ++k) {
        for (int i = 1; i <= N; ++i) {
            for (int j = 1; j <= N; ++j) {
                p_graph[i][j] = min(p_graph[i][j], p_graph[i][k] + p_graph[k][j]);
            }
        }
    }
    int res, mn = INF;
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= N; ++j) {
            if (p_graph[i][j] != INF) fp_dist[i] = max(fp_dist[i], p_graph[i][j]);
        }
        if (mn > fp_dist[i]) {
            mn = fp_dist[i];
            res = i;
        }
    }
    return res;
}

void dijkstra(int dest) {
    dp_dist[dest] = dv_dist[dest] = 0;
    for (int i = 1; i <= N; ++i) {
        int p_min = INF, v_max = 0, idx = -1;
        for (int j = 1; j <= N; ++j) {
            if (!visited[j] &&
                (p_min > dp_dist[j] || (p_min == dp_dist[j] && v_max < dv_dist[j]))) {
                p_min = dp_dist[j];
                v_max = dv_dist[j];
                idx = j;
            }
        }
        visited[idx] = true;
        for (int j = 1; j <= N; ++j) {
            if (!visited[j] && graph[idx][j].power != INF) {
                if (dp_dist[j] > dp_dist[idx] + graph[idx][j].power) {
                    dp_dist[j] = dp_dist[idx] + graph[idx][j].power;
                    dv_dist[j] = dv_dist[idx] + graph[idx][j].value;
                    path[j] = idx;
                } else if ((dp_dist[j] == dp_dist[idx] + graph[idx][j].power) &&
                           (dv_dist[j] < dv_dist[idx] + graph[idx][j].value)) {
                    dv_dist[j] = dv_dist[idx] + graph[idx][j].value;
                    path[j] = idx;
                }
            }
        }
    }
}

int main() {
    scanf("%d%d", &N, &M);
    for (int i = 1; i <= N; ++i) {
        dp_dist[i] = INF;
        for (int j = 1; j <= N; ++j) {
            p_graph[i][j] = INF;
        }
    }
    int B1, B2, power, value;
    while (M--) {
        scanf("%d%d%d%d", &B1, &B2, &power, &value);
        p_graph[B1][B2] = p_graph[B2][B1] = power;
        graph[B1][B2].power = graph[B2][B1].power = power;
        graph[B1][B2].value = graph[B2][B1].value = value;
    }
    int pos = floyd();
    printf("%d\n", pos);
    dijkstra(pos);
    int K, k, total_power, total_value;
    scanf("%d", &K);
    while (K--) {
        scanf("%d", &k);
        total_power = dp_dist[k];
        total_value = dv_dist[k];
        stack<int> stk;
        while (k != pos) {
            stk.push(k);
            k = path[k];
        }
        printf("%d", pos);
        while (stk.size()) {
            printf("->%d", stk.top());
            stk.pop();
        }
        printf("\n%d %d", total_power, total_value);
        if (K) printf("\n");
    }

    return 0;
}

7-4 疫情防控

疫情尚未结束，严防疫情反复。为了做好疫情防控工作，国内设置了地区风险等级，对于中高风险地区的人员采取限制移动、居家隔离等手段。

为了研究疫情防控对于跨地区交通运输的影响，假设现在有 N 个机场，M 条航线，每天都会新增一个防控地区，一个防控地区会导致一个机场无法正常运作，航线也自然无法正常运行，每天会有 Q_i 对旅客从 X_i 机场前往 Y_i 机场，请计算有多少对旅客会受到影响无法完成行程。

旅客只要能直达或通过若干次中转，且乘坐的所有航线的出发和到达机场都正常运作，即视作可完成行程。

输入格式:

输入第一行是三个整数 N,M,D (1≤N≤5×10⁴, 1≤M≤2×10⁵, 1≤D≤10³), 表示机场数、航线数以及新增防控地区的天数。

接下来首先有 M 行，每行给出空格分隔的两个数字 A 和 B，表示编号为 A 和 B 的机场之间有一条航线。航线是双向的，机场编号从 1 到 N。

然后是 D 块输入，每块输入内第一行为空格分隔的两个整数 C 和 Q （1≤Q≤10³)，表示新增机场编号为 C 所在的城市为防控地区，今天有 Q 段行程。数据保证新增的城市之前一定不是防控地区。

接下来的 Q 行，每行是空格分隔的两个数字 X 和 Y，表示编号为 X 和 Y 的机场的一段行程。行程有可能包括之前就已经成为防控地区的城市。

输出格式:

对于每天的询问，请在一行中输出在新增了一个防控地区后当天的行程有多少不能成行。

输入样例:

输出样例:

1
2
3

解题：并查集栈哈希表

思路

根据题意可以知道：需要维护一个并查集，并且它表示的图支持删除点的操作。

但是在并查集中删除点一般需要重建并查集，那么在数据量大的时候就可能会超时或者超内存。所以不能直接重建并查集。

于是就需要利用栈来把删除的操作反转过来，提前输入数据并推入栈中，然后反向之后就变成了增加点、从栈中弹出数据，增加点的操作就容易很多，算出答案后再推入栈中。直到所有答案算出来再依次弹栈输出即可。

（代码中部分栈操作使用了向量进行替代）

代码

#include<iostream>
#include<stack>
#include<vector>
#include<unordered_map>

using namespace std;

vector<int> root;

int find(int n) {
    return root[n] == n ? n : (root[n] = find(root[n]));
}

void join(int p, int q) {
    root[find(p)] = find(q);
}

int main() {
    int N, M, D;
    scanf("%d%d%d", &N, &M, &D);
    root = vector<int>(N + 1);
    for (int i = 1; i <= N; ++i) root[i] = i;
    int A, B;
    unordered_map<int, vector<int>> graph;
    while (M--) {
        scanf("%d%d", &A, &B);
        graph[B].push_back(A);
        graph[A].push_back(B);
    }
    vector<pair<int, int>> queries;
    vector<int> query_counts, removes;
    vector<bool> is_removed(N + 1, false);
    int C, Q;
    while (D--) {
        scanf("%d%d", &C, &Q);
        is_removed[C] = true;
        removes.push_back(C);
        query_counts.push_back(Q);
        int X, Y;
        for (int j = 0; j < Q; ++j) {
            scanf("%d%d", &X, &Y);
            queries.push_back({X, Y});
        }
    }

    for (int u = 1; u <= N; ++u) {
        if (is_removed[u]) continue;
        for (auto& v : graph[u]) {
            if (!is_removed[v]) join(u, v);
        }
    }
    stack<int> counts;
    for (int i = query_counts.size() - 1; i >= 0; --i) {
        int count = 0;
        int& query_count = query_counts[i];
        for (int j = 0; j < query_count; ++j) {
            auto& query = queries.back();
            if (find(query.first) != find(query.second)) ++count;
            if (queries.size()) queries.pop_back();
        }
        counts.push(count);
        int& u = removes[i];
        is_removed[u] = false;
        for (int& v : graph[u]) {
            if (!is_removed[v]) join(v, u);
        }
    }
    while (!counts.empty()) {
        printf("%d\n", counts.top());
        counts.pop();
    }

    return 0;
}

目录CONTENT

【算法竞赛】2021 RoboCom 世界机器人开发者大赛-本科组（初赛）

2021 RoboCom 世界机器人开发者大赛-本科组（初赛）

7-1 懂的都懂

解题：暴力模拟哈希表

思路

代码

7-2 芬兰木棋

解题：数学哈希表

思路

代码

7-3 打怪升级

解题：Floyd算法 Dijkstra算法

思路

代码

7-4 疫情防控

解题：并查集栈哈希表

思路

代码

评论区

【算法竞赛】2021 RoboCom 世界机器人开发者大赛-本科组（初赛）

2021 RoboCom 世界机器人开发者大赛-本科组（初赛）

7-1 懂的都懂

解题：暴力 模拟 哈希表

思路

代码

7-2 芬兰木棋

解题：数学 哈希表

思路

代码

7-3 打怪升级

解题：Floyd算法 Dijkstra算法

思路

代码

7-4 疫情防控

解题：并查集 栈 哈希表

思路

代码

评论区

解题：暴力模拟哈希表

解题：数学哈希表

解题：并查集栈哈希表