巅峰赛#19

hopebetter

2025-05-24 16:21:41

发布于：江苏

122阅读

0回复

0点赞

ACGO 巅峰赛#19 题解

本场巅峰赛的所有题目的难度评级为：

题目编号	题目标题	难度
T1	变色龙	入门
T2	打印机	入门
T3	机器人	普及-
T4	公告	普及+/提高-
T5	登塔	普及+/提高-
T6	24点	普及+/提高

题目解析

A - 变色龙

模拟

题目描述，给定两个 $n \times n$ 的矩阵，求两个矩阵中的有多少个相同位置的大小为 $m \times m$ 的二维矩阵是不同的,由于n,m比较小，因此可以直接枚举左上角的点，然后枚举两个矩阵相应位置的 $m \times m$ 矩阵的点，如果有不同就加入统计。
时间复杂度 O( $n^2m^2$ )

代码

#include<bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<string> v1(n + 1), v2(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> v1[i];
        v1[i] = " " + v1[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> v2[i];
        v2[i] = " " + v2[i];
    }

    int t = 0;
    //枚举左上角点的位置；
    for (int i = 1; i <= n - m + 1; i++) {
        for (int j = 1; j <= n - m + 1; j++) {
            bool f = false;
            for (int k = i; k <= i + m - 1; k++) {
                for (int l = j; l <= j + m - 1; l++) {
                    if (v1[k][l] != v2[k][l]) t++, f = true;
                    if (f) break;
                }
                if (f) break;
            }
        }
    }
    cout << t << endl;
}

B - 打印机

模拟
在处理试卷打印时，仅需考虑单面打印和双面打印这两种情形。对于双面打印，需要留意的是，若某页纸的正面或反面任意一面需要彩色打印，那么这一整张纸都要采用彩色打印。我们可以运用集合（set）来对最终结果加以统计。
时间复杂度 O( $m\log(m) +n$ )

代码

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using i32 = int32_t;

void solve() {

    i64 a, b, c, d;
    cin >> a >> b >> c >> d;
    i64 n, m;
    cin >> n >> m;
    i64 mins = a * m + (n - m) * c;
    set<int> s;
    set<int> s2;

    for (int i = 1; i <= m; i++) {
        int x;
        cin >> x;
        s2.emplace(x);
        x++;
        s.emplace(x / 2);
    }
    mins = min(mins, (i64) (b * s.size() + ((n + 1) / 2 - s.size()) * d));
    cout << mins << endl;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);

    int t = 1;

    while (t--) {
        solve();
    }
}

C- 机器人
二分
首先，机器人仅能沿横坐标与纵坐标方向移动。基于这一特性，我们可以分别按横坐标和纵坐标，对柱子的信息进行存储。考虑到坐标数值可能较大，使用map进行存储较为合适。

对于横、纵坐标上每个可能出现的点，我们将其存入对应的数组。完成数据存储后，每次机器人移动时，通过二分查找的方法，就能判断机器人当前位置与目标位置之间是否存在柱子。
时间复杂度 (O( $(n + q )\log(n)$ )

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, m;

    cin >> n >> m;
    map<i64, vector<i64> > mpx;
    map<i64, vector<i64> > mpy;
    for (int i = 1; i <= n; i++) {
        int x, y;
        cin >> x >> y;
        mpx[x].emplace_back(y);
        mpy[y].emplace_back(x);
    }
    for (auto &i: mpx) {
        auto &[_,v] = i;
        sort(v.begin(), v.end());
    }
    for (auto &i: mpy) {
        auto &[_,v] = i;
        sort(v.begin(), v.end());
    }
    i64 nowx = 0, nowy = 0;

    auto sub = [&](vector<i64> &v, i64 x, i64 to) {
        if (v.empty() || v.back() < x - to || v.front() > x) return x - to;
        int l = 0, r = v.size() - 1;
        while (l < r) {
            int mid = (l + r + 1) / 2;
            if (v[mid] <= x) l = mid;
            else r = mid - 1;
        }
        if (v[l] >= x - to ) return v[l] + 1;
        return x - to;
    };

    auto add = [&](vector<i64> &v, i64 x, i64 to) {
        if (v.empty() || v.front() > x + to || v.back() < x) return x + to;
        int l = 0, r = v.size() - 1;
        while (l < r) {
            int mid = (l + r) / 2;
            if (v[mid] >= x) r = mid;
            else l = mid + 1;
        }
        if (v[l] <= x + to) return v[l] - 1;
        return x + to;
    };
    for (int i = 1; i <= m; i++) {
        char c;
        i64 z;
        cin >> c >> z;
        if (c == 'r') {
            nowx = add(mpy[nowy], nowx, z);
        } else if (c == 'l') {
            nowx = sub(mpy[nowy], nowx, z);
        } else if (c == 'w') {
            nowy = add(mpx[nowx], nowy, z);
        } else {
            nowy = sub(mpx[nowx], nowy, z);
        }
    }
    cout << nowx << " " << nowy << endl;
}

D-公告

并查集
在解决当前问题时，正向处理存在较大难度，往往需要多次断边，才能成功去除某一连通块。既然直接删边操作复杂，不妨尝试采用离线算法来简化计算。

我们可以逆向思考，将删边操作转换为加边操作。从最后一次删边开始倒序处理，这样问题就转化为：给定一个图，逐步向图中添加边，并在每次加边后确定班长能够通知到的学生集合。我们可以通过并查集解决这个问题。

时间复杂度 O(n)

// #include <testlib.h>
// #include <testlib.h>
#include<bits/stdc++.h>
using namespace std;
const int limit = 1e9 + 1;

class DSU {
public:
    DSU(int n, int m) : n(n), fa(n + 1), siz(n + 1) {
        iota(fa.begin(), fa.end(), 0);
        for (int i = 1; i <= m; i++)siz[i] = 1;
    }

    int find(int x) {
        if (fa[x] != x)fa[x] = find(fa[x]);
        return fa[x];
    }

    void merge(int x, int y) {
        x = find(x), y = find(y);
        if (x != y) {
            fa[x] = y;
            siz[y] += siz[x];
        }
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }

    bool ishead(int x) {
        return x == find(x);
    }

    int size(int x) {
        return siz[find(x)];
    }

private:
    int n;
    vector<int> fa;
    vector<int> siz;
};

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, m, q;
    cin >> n >> m >> q;
    vector<set<int> > edge(n + 1);
    for (int i = 1; i <= m; i++) {
        int k;
        cin >> k;
        for (int j = 1; j <= k; j++) {
            int s;
            cin >> s;
            edge[s].emplace(i);
        }
    }
    vector<pair<int, int> > ask(q);
    for (auto &[i, j]: ask) {
        cin >> i >> j;
        edge[i].erase(j);
    }
    stack<int> ans;
    DSU d(n + m + 1 , n);
    for (int i = 1; i <= n; i++) {
        for (const auto j: edge[i]) d.merge(i, j + n);
    }
    for (int i = q; i; i--) {
        ans.emplace(n - d.size(1));
        auto [u,v] = ask[i - 1];
        d.merge(u, v + n);
    }
    while (!ans.empty()) {
        auto t = ans.top();
        ans.pop();
        cout << t << endl;
    }
}

E-登塔

动态规划

对于本题，我们先从常规思路入手，考虑从第 $i$ 层向第 $i + 1$ 层的状态转移。设 $f[i][j]$ 表示处于第 $i$ 层的第 $j$ 个房间时所能取得的最大值。那么状态转移方程为 $f[i + 1][k] = \max(f[i][j]) + a[i + 1][k]$ ，其中 $j \in \{1, 2, \cdots, n\}$ 且 $j \neq k$ 。

从这个转移方程可以看出， $f[i + 1][j]$ 的转移核心在于找出第 $i$ 层除第 $j$ 个房间之外能取得的最大价值。假设第 $i$ 层价值最大的房间编号为 $j$ ，那么在第 $i + 1$ 层中，除了第 $j$ 号房间外，其他房间都可以从第 $i$ 层的 $j$ 号房间移动过来，从而获取最大价值。而第 $i + 1$ 层的 $j$ 号房间，则可以从第 $i$ 层价值次大的房间转移到达。

基于此，我们发现只需记录每一层价值最大的两个房间的编号，就能实现向下一层的状态转移。这种方法的时间复杂度为 $O(nm)$ 。

注意 m == 1的状况他会被困在第一层

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;

int main() {
   ios::sync_with_stdio(0),cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector<vector<i64> > arr(n + 1, vector<i64>(m + 1));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> arr[i][j];
        }
    }
    vector<priority_queue<pair<i64, int>, vector<pair<i64, int> >, greater<> > > f(n + 1);
    f[0].emplace(0, 0);
    for (int i = 1; i <= n; i++) {
        if (f[i - 1].empty()) continue;
        for (int j = 1; j <= m; j++) {
            auto t = f[i - 1].top();
            f[i - 1].pop();
            if (!f[i - 1].empty() && f[i - 1].top().second != j) {
                f[i].emplace(arr[i][j] + f[i - 1].top().first, j);
            } else {
                if (t.second != j)
                    f[i].emplace(arr[i][j] + t.first, j);
            }
            f[i - 1].emplace(t);
            while (f[i].size() > 2) f[i].pop();
        }
    }
    i64 maxs = 0;
    for (int i = 1; i <= n; i++) {
        while (!f[i].empty()) {
            maxs = max(maxs, f[i].top().first);
            f[i].pop();
        }
    }
    cout << maxs << endl;
}

F-24点

抽屉原理

许多同学尝试通过模拟的方法来解决这道题，然而在模拟实现的过程中，一个明显的问题浮现出来：一旦出现错误，检查和调试都极为困难。那么，我们能否通过深入观察题目的性质，来降低模拟的复杂程度呢？

首先，让我们思考这样一个问题：给定任意两个数，我们是否能够通过一定的运算构造出一个 3 的倍数呢？

假设这两个数为 $a$ 和 $b$ 。如果其中一个数本身就是 3 的倍数，那么将这两个数相乘即可得到 3 的倍数，这种情况较为简单，我们暂不深入讨论。接下来考虑两个数都不是 3 的倍数的情况，此时它们除以 3 的余数（即模 3 的结果）共有 4 种组合： $\{1, 1\}$ 、 $\{1, 2\}$ 、 $\{2, 1\}$ 、 $\{2, 2\}$ 。经过分析不难发现，对于这四种组合，我们都可以通过加法或者减法运算，使它们得到的结果成为 3 的倍数。由此，我们证明了任意两个数都能够通过适当的运算得到 3 的倍数。

已知 $24 \div 3 = 8$ ，此时问题就转化为：给定 4 个数，我们能否从中选取两个数，通过运算构造出 8 的倍数呢？为了简化问题，我们先排除这 4 个数中本身就包含 8 的倍数的情况。那么，当这 4 个数分别除以 8 取余数（即模 8 ）后，结果只会是 1、2、3、4、5、6、7 这 7 种情况。接下来我们思考，这 7 种余数情况中，哪些组合可以构成 8 的倍数呢？

通过计算可知， $1 + 7 = 8$ ， $3 + 5 = 8$ ， $2 \times 4 = 8$ ， $2 + 6 = 8$ ， $4 \times 6 = 24$ （24 也是 8 的倍数）。基于这些组合，我们可以将这 7 种余数情况划分成 3 个集合： $\{1, 7\}$ ， $\{3, 5\}$ ， $\{2, 4, 6\}$ 。在这三个集合中，任意选取集合内的两个数，都可以通过相应的运算构成 8 的倍数。

由于我们一共有 4 个数，根据抽屉原理，这 4 个数中必然会有至少两个数的余数属于同一个集合。所以，我们可以先从这 4 个数中选取 2 个数，构造出 8 的倍数，再通过前面证明的方法构造出 3 的倍数，最后将得到的 8 的倍数和 3 的倍数相乘，就可以得到满足条件的结果。

综上所述，该算法的时间复杂度为 $O(T)$ 。

#include<bits/stdc++.h>
using namespace std;

string get(int a, int b, int x) {
    if ((a + b) % x == 0) {
        return "(" + to_string(a) + "+" + to_string(b) + ")";
    }
    if ((a - b) % x == 0) {
        return "(" + to_string(a) + "-" + to_string(b) + ")";
    } {
        return "(" + to_string(a) + "*" + to_string(b) + ")";
    }
};

string get(queue<int> &q, int x) {
    int a = q.front();
    q.pop();
    int b = q.front();
    q.pop();
    if ((a + b) % x == 0) {
        return "(" + to_string(a) + "+" + to_string(b) + ")";
    }
    if ((a - b) % x == 0) {
        return "(" + to_string(a) + "-" + to_string(b) + ")";
    } {
        return "(" + to_string(a) + "*" + to_string(b) + ")";
    }
};

void solve() {
    vector<int> a(4);
    string ans;
    for (auto &i: a) {
        cin >> i;
    }
    queue<int> q1, q2, q3, q4, q5;
    for (auto i: a) {
        if (i % 8 == 0)q1.emplace(i);
        else if (i % 8 == 1 || i % 8 == 7) {
            q2.emplace(i);
        } else if (i % 8 == 2 || i % 8 == 4 || i % 8 == 6) {
            q3.emplace(i);
        } else
            q4.emplace(i);
    }
    if (!q1.empty()) {
        ans = to_string(q1.front());
        q1.pop();
    } else if (q2.size() >= 2) {
        ans = get(q2, 8);
    } else if (q3.size() >= 2) {
        ans = get(q3, 8);
    } else {
        ans = get(q4, 8);
    }
    while (!q1.empty()) {
        q5.emplace(q1.front());
        q1.pop();
    }
    while (!q2.empty()) {
        q5.emplace(q2.front());
        q2.pop();
    }
    while (!q3.empty()) {
        q5.emplace(q3.front());
        q3.pop();
    }
    while (!q4.empty()) {
        q5.emplace(q4.front());
        q4.pop();
    }
    ans = ans + "*" + get(q5, 3);
    while (!q5.empty()) {
        ans = ans + "*" + to_string(q5.front());
        q5.pop();
    }
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}