2024 RoboCom(本科组)

发表于 更新于 分类于 阅读次数： 本文字数： 2.4k 阅读时长 ≈ 9 分钟
Ming due to the circumstances, the knower system according to the matter.

闲来无事水一水今年睿抗
做完之后最大的感受就是比去年简单挺多，不知道线是怎么样的
备注：前五题为省赛题目，后面为国赛题目

RC-u1 热҈热热҈

题目大意：统计 且 的个数

思路：

  • 按照题意模拟即可

时间复杂度：

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
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int N, W;
    std::cin >> N >> W;

    int cnt = 0, sum = 0;
    for (int i = 0; i < N; ++i) {
        int x;
        std::cin >> x;

        W %= 7;

        if (W++ == 4) {
            if (x >= 35) {
                ++cnt;
            }
            continue ;
        }

        if (x >= 35) {
            sum++;
        }
    }
    std::cout << sum << " " << cnt << "\n";
    
    return 0;
}

RC-u2 谁进线下了？

题目大意：按照题目要求，统计 20 个队伍的得分信息并输出结果

思路：

  • 按照题目所给数据模拟，然后排序输出即可

时间复杂度：

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int N;
    std::cin >> N;

    auto check = [&](int x) {
        int res = 0;
        if (x == 0) {
            res = 12;
        } else if (x == 1) {
            res = 9;
        } else if (x == 2) {
            res = 7;
        } else if (x == 3) {
            res = 5;
        } else if (x == 4) {
            res = 4;
        } else if (x == 5 || x == 6) {
            res = 3;
        } else if (x >= 7 && x <= 9) {
            res = 2;
        } else if (x >= 10 && x <= 14) {
            res = 1;
        }
        return res;
    };

    std::vector<int> score(20);
    while (N--) {
        for (int i = 0; i < 20; ++i) {
            int p, k;
            std::cin >> p >> k;
            p--;

            score[i] += check(p) + k;
        }
    }

    std::vector<std::pair<int, int>> vec;
    for (int i = 0; i < 20; ++i) {
        vec.push_back({i, score[i]});
    }

    std::sort(vec.begin(), vec.end(),
        [&](auto i, auto j) {
            return i.first < j.first;
        });

    for (int i = 0; i < 20; ++i) {
        std::cout << vec[i].first + 1 << " " << vec[i].second << "\n";
    }

    return 0;
}

RC-u3 暖炉与水豚

题目大意：在 的图中，找一个点使得剩下的所有的w都可以处于温暖的状态下

思路：

  • 首先，统计所有的w的个数，然后将不合法的w记录下来，然后把所有不合法的w周围的 9 个点统计一下。
  • 然后枚举所有的可能点，同时check整张图，如果合法就把这个可能点加入ans序列。
  • 最后，按照要求将ans序列排序并输出。

时间复杂度：

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
   
    int N, M;
    std::cin >> N >> M;

    std::map<std::pair<int, int>, bool> mp;
    std::vector<std::string> G(N);
    std::vector<std::vector<int>> vis(N, std::vector<int>(M));
    int sum = 0;
    for (int i = 0; i < N; ++i) {
        std::cin >> G[i];
        for (int j = 0; j < M; ++j) {
            if (G[i][j] == 'w') sum++;
            if (G[i][j] == 'c') {
                for (int a = -1; a <= 1; ++a) {
                    for (int b = -1; b <= 1; ++b) {
                        int x = a + i, y = b + j;
                        if (x >= N || y >= M || x < 0 || y < 0) continue ;
                        mp[{x, y}] = true;
                    }
                }
            }
        }
    }
    
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            if (G[i][j] == 'm') {
                for (int a = -1; a <= 1; ++a) {
                    for (int b = -1; b <= 1; ++b) {
                        int x = a + i, y = b + j;
                        if (x >= N || y >= M || x < 0 || y < 0) continue ;
                        if (G[x][y] == 'w') {
                            vis[x][y] = true;
                        }
                    }
                }
            }
        }
    }

    std::vector<std::array<int, 2>> p;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            if (!vis[i][j] && G[i][j] == 'w') {
                for (int a = -1; a <= 1; ++a) {
                    for (int b = -1; b <= 1; ++b) {
                        int x = a + i, y = b + j;
                        if (x >= N || y >= M || x < 0 || y < 0) continue ;
                        if (G[x][y] == '.' && !mp.count({x, y})) {
                            p.push_back({x, y});
                        }
                    }
                }
            }
        }
    }

    std::vector<std::array<int, 2>> ans;
    for (auto [x, y] : p) {
        auto work = [&](int a, int b) {
            std::vector<std::vector<int>> copy = vis;
            std::vector<std::pair<int, int>> now;
            for (int i = -1; i <= 1; ++i) {
                for (int j = -1; j <= 1; ++j) {
                    int x = a + i, y = b + j;
                    if (x >= N || y >= M || x < 0 || y < 0) continue ;
                    if (G[x][y] == 'w' && !vis[x][y]) {
                        vis[x][y] = true;
                        now.push_back({x, y});
                    }
                }
            }

            int res = 0;
            for (int i = 0; i < N; ++i) {
                for (int j = 0; j < M; ++j) {
                    if (vis[i][j] && G[i][j] == 'w') {
                        res++;
                    }
                }
            }

            if (res == sum) {
                ans.push_back({a, b});
            }
            vis = copy;
        };
        work(x, y);
    }

    std::sort(ans.begin(), ans.end(),
        [&](auto i, auto j) {
            if (i[0] == j[0]) return i[1] < j[1];
            return i[0] < j[0];
        });

    if (ans.empty()) {
        std::cout << "Too cold!\n";
        return 0;
    }

    ans.erase(std::unique(ans.begin(), ans.end()), ans.end());
    for (auto [x, y] : ans) {
        std::cout << x + 1 << " " << y + 1 << "\n";
    }

    return 0;
}

RC-u4 章鱼图的判断

题目大意：找到给定无向图 中环的个数，如果 1 个，就输出Yes和环上主要点(度数为 2)的个数

思路：

  • 首先，将这个带一个环的图进行删减，使其只剩下一个主环(所有的点的度数为 2)。
  • 考虑特殊情况：多环共点。通过遍历的方式，将这些特殊的点删除。
  • 最后开始遍历处理好的只剩下主环的图，统计环的个数和点的个数。

时间复杂度：

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
void solve() {
    int N, M;
    std::cin >> N >> M;

    std::vector<int> deg(N + 1);
    std::vector<std::vector<int>> adj(N + 1);
    for (int i = 0; i < M; ++i) {
        int u, v;
        std::cin >> u >> v;
        deg[u]++, deg[v]++;

        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    auto topo = [&]() {
        std::queue<int> q;
        for (int i = 1; i <= N; ++i) {
            if (deg[i] == 1) {
                q.push(i);
            }
        }

        while (!q.empty()) {
            int t = q.front();
            q.pop();
            deg[t]--;

            for (int v : adj[t]) {
                if (--deg[v] == 1) {
                    q.push(v);
                }
            }
        }
    };
    topo();

    int ans = 0, cnt = 0;
    auto dfs = [&](auto self, int u) -> void {
        deg[u] = 0;
        for (int v : adj[u]) {
            if (deg[v]) {
                self(self, v);
                cnt++;
            }
        }
    };

    for (int i = 1; i <= N; ++i) {
        if (deg[i] && deg[i] != 2) {
            dfs(dfs, i);
        }
    }

    ans = cnt = 0;
    for (int i = 1; i <= N; ++i) {
        if (deg[i] == 2) {
            cnt = 1;
            dfs(dfs, i);
            ans++;
        }
    }

    if (ans == 1) {
        std::cout << "Yes " << cnt << "\n";
    } else {
        std::cout << "No " << ans << "\n";
    }
}

RC-u5 工作安排

题目大意：将问题抽象为01背包，问题中的t[i]为物品的体积v，报酬p[i]则为物品的价值w，限制时间d[i]则为装入条件限制

思路：

  • 首先，按照完成日期要求，从小到大排序。
  • 然后直接按照01背包的做法进行求解。

时间复杂度：

附：01背包状态转移方程dp[j] = max(dp[j - v[i]] + w[i], dp[j])

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void solve() {
    int N;
    std::cin >> N;

    std::vector<std::array<int,3>> a(N + 1);
    for (int i = 1; i <= N; ++i) {
        int t, d, p;
        std::cin >> t >> d >> p;

        a[i] = {d, t, p};
    }

    std::sort(a.begin() + 1, a.end());

    std::vector<int> dp(5050);
    for (int i = 1; i <= N; ++i) {
        for (int j = 5000; j >= 0; --j) {
            if (j >= a[i][1] && j <= a[i][0]) {
                dp[j] = std::max(dp[j - a[i][1]] + a[i][2], dp[j]);
            }
        }
    }
    std::cout << *max_element(dp.begin(), dp.end()) << "\n";
}

RC-u1 大家一起查作弊

题目大意：就是让你分割字符串，然后判断这个分割的字符串里的合法字符含量，然后将对应的分数加上即可

思路：

  • 首先，分割所有字符串，将其都分割为单独一个关键词
  • 然后，核对关键词，计算结果
  • 总的来说，就是一个模拟

时间复杂度：

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

int main() {
    std::vector<std::string> vec;

    std::string s;
    while (std::getline(std::cin, s)) {
        s += '&';
        auto work = [&](std::string a, int n) {
            for (int i = 0; i < n; ++i) {
                int j = i;
                bool ok = false;
                while ((isalnum(a[j])) && j < n) {
                    j++;
                    ok = true;
                }
                if (ok) {
                    vec.push_back(s.substr(i, j - i));
                }
                i = j;
            }
        };
        work(s, s.size());
    }

    int cnt = 0;
    int score = 0, length = 0;
    for (auto &v : vec) {
        auto check = [&](std::string s) {
            if (std::find_if(s.begin(), s.end(), [](char v) {
                return isupper(v);
            }) != s.end() && std::find_if(s.begin(), s.end(), [](char v) {
                return islower(v);
            }) != s.end() && std::find_if(s.begin(), s.end(), [](char v) {
                return isdigit(v);
            }) != s.end()) {
                score += 5;
                return true;
            }
            if ((std::find_if(s.begin(), s.end(), [](char v) {
                return isupper(v);
            }) != s.end() || std::find_if(s.begin(), s.end(), [](char v) {
                return islower(v);
            }) != s.end()) && std::find_if(s.begin(), s.end(), [](char v) {
                return isdigit(v);
            }) != s.end()) {
                score += 3;
                return true;
            }
            if (std::find_if(s.begin(), s.end(), [](char v) {
                return isupper(v);
            }) != s.end() && std::find_if(s.begin(), s.end(), [](char v) {
                return islower(v);
            }) != s.end()) {
                score += 1;
                return true;
            }
            return false;
        };
        length += v.size();
        check(v);
    }
    std::cout << score << "\n";
    std::cout << length << " " << vec.size() << "\n";

    return 0;
}

RC-u2 谁进线下了？II

题目大意：按照题目给的表，计算队伍得分

思路：

  • 模拟即可，这个和省赛的一个题目好像

时间复杂度：

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
42
43
44
45
int check(int x) {
    int res;
    if (x == 1) res = 25;
    else if (x == 2) res = 21;
    else if (x == 3) res = 18;
    else res = 20 - x;
    return res;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int N;
    std::cin >> N;

    std::unordered_set<int> vis;
    std::vector<int> score(35);
    while (N--) {
        for (int i = 0; i < 20; i++) {
            int c, p;
            std::cin >> c >> p;
            vis.insert(c);
            score[c] += check(p);
        }
    }

    std::vector<int> rank(35);
    std::iota(rank.begin(), rank.end(), 0);

    std::sort(rank.begin() + 1, rank.end(),
        [&](int i, int j) {
            if (score[i] != score[j]) {
                return score[i] > score[j];
            }
            return i < j;
        });

    for (int i = 1; i <= 30; i++) {
        if (!vis.count(rank[i])) continue ;
        std::cout << rank[i] << " " << score[rank[i]] << "\n";
    }

    return 0;
}

RC-u3 势均力敌

题目大意：将 个数平分为两组，求一半的平方和与另一半相等的任意一组解

思路：

  • 这个做法有问题，暴力求解，拿了 14 分，后续会加正解

时间复杂度：

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    std::cin >> n;

    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }

    std::sort(a.begin(), a.end());

    i64 sum = 0;
    std::vector<i64> b;
    do {
        int x = 0;
        for (int i = 0; i < n; i++) {
            x = x * 10 + a[i];
        }
        b.push_back(1LL * x * x);
        sum += 1LL * x * x;
    } while (std::next_permutation(a.begin(), a.end()));
        
    int limit = (n == 3 ? 3 : 12);

    std::vector<int> c;
    std::vector<int> vis(b.size() + 1);
    auto dfs = [&](auto self, int x, int cnt, std::vector<int> path, i64 s) -> bool {
        if (cnt == limit) {
            if (s == sum / 2) {
                c = path;
                return true;
            }
        }
        for (int i = x; i < b.size(); i++) {
            if (!vis[i]) {
                if (s + b[i] <= sum / 2) {
                    vis[i] = true;
                    path.push_back(sqrt(b[i]));
                    self(self, x + 1, cnt + 1, path, s + b[i]);
                    path.pop_back();
                    vis[i] = false;
                }
            }
        }
        return false;
    };
    dfs(dfs, 0, 0, c, 0);

    for (int v : c) {
        std::cout << v << "\n";
    }

    return 0;
}

RC-u4 City 不 City

题目大意：找一个权值和最小，记录沿途的热度最大的城市

思路：

  • 这个图是一个稀疏图，所以跑一遍朴素版 算法即可

时间复杂度：

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
constexpr int inf = 0x3f3f3f3f;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, m, s, t;
    std::cin >> n >> m >> s >> t;

    std::vector<int> w(n + 1);
    for (int i = 1; i <= n; i++) {
        std::cin >> w[i];
    }

    w[s] = w[t] = 0;
    std::vector<std::vector<int>> G(1005, std::vector<int>(1005, inf));
    for (int i = 0; i < m; i++) {
        int u, v, w;
        std::cin >> u >> v >> w;

        G[u][v] = w;
        G[v][u] = w;
    }

    std::vector<int> val(n + 1);
    std::vector<int> dist(n + 1, inf), vis(n + 1);
    auto dijkstra = [&]() {
        for (int i = 1; i <= n; i++) {
            dist[i] = G[s][i];
            if (G[s][i] != inf) {
                val[i] = w[i];
            }
        }
        vis[s] = true;

        for (int i = 0; i + 1 < n; i++) {
            int t = -1;
            for (int j = 1; j <= n; j++) {
                if (!vis[j] && (t == -1 || dist[t] > dist[j]))
                    t = j;
            }

            vis[t] = 1;
            for (int j = 1; j <= n; j++) {
                if (!vis[j] && dist[j] > dist[t] + G[t][j]) {
                    dist[j] = dist[t] + G[t][j];
                    val[j] = std::max(val[t], w[j]);
                } else if (!vis[j] && dist[j] == dist[t] + G[t][j] && val[j] > std::max(val[t], w[j])) {
                    dist[j] = dist[t] + G[t][j];
                    val[j] = std::max(val[t], w[j]);
                }
            }
        }
    };

    dijkstra();

    if (dist[t] == inf) {
        std::cout << "Impossible\n";
    } else {
        std::cout << dist[t] << " " << val[t] << "\n";
    }

    return 0;
}