ACGO巅峰赛#19题解简评

‌

2025-04-05 23:27:56

发布于：北京

9阅读

0回复

0点赞

T1 - 变色龙

完整代码

#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; break; }
            if (f) break;
        }
    cout << t << endl;
}

深度分析

关键公式
子矩阵枚举范围：
[
i \in [1, n - m + 1], \quad j \in [1, n - m + 1]
]

常见错误

子矩阵范围错误：写成 i <= n 导致越界。
字符比较错误：直接比较 v1[k][l] 和 v2[k][l] 的 ASCII 值而非字符。

改进建议

哈希优化：预处理每个子矩阵的哈希值，比较哈希值而非逐字符。
提前终止：当子矩阵左上角不同时，跳过整个区域。
输入验证：添加 if (m > n) 处理无效输入。

T2 - 打印机

完整代码

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

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

    for (int i=1; i<=m; i++) {
        int x; cin >> x;
        s2.insert(x);
        x++;
        s.insert(x/2);
    }
    mins = min(mins, 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();
}

深度分析

关键公式
双面打印纸张数：
[
\text{pages} = \left\lceil \frac{m}{2} \right\rceil
]

常见错误

奇数页处理错误：x/2 未考虑向上取整。
边界条件遗漏：未处理 m=0 或 n=0。

改进建议

数学简化：直接计算 (m + 1) // 2 代替集合操作。
逻辑优化：比较单面和双面成本时，统一使用整数运算。
测试用例：添加 m=0、n=0 和 m=1 的测试。

T3 - 机器人

完整代码

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

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, m; cin >> n >> m;
    map<long long, vector<long long>> mpx, mpy;
    for (int i=1; i<=n; i++) {
        int x, y; cin >> x >> y;
        mpx[x].push_back(y);
        mpy[y].push_back(x);
    }
    for (auto &[_,v]: mpx) sort(v.begin(), v.end());
    for (auto &[_,v]: mpy) sort(v.begin(), v.end());

    auto sub = [&](vector<long long> &v, long long x, long long to) {
        if (v.empty() || v.back() < x - to) 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;
        }
        return v[l] >= x - to ? v[l]+1 : x - to;
    };

    auto add = [&](vector<long long> &v, long long x, long long to) {
        if (v.empty() || v.front() > x + to) 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;
        }
        return v[l] <= x + to ? v[l]-1 : x + to;
    };

    long long nowx=0, nowy=0;
    for (int i=1; i<=m; i++) {
        char c; long long 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;
}

深度分析

关键公式
移动后的坐标：
[
\text{new_x} = \begin{cases}
\text{障碍物右侧第一个空位} & \text{向右} \
\text{障碍物左侧第一个空位} & \text{向左} \
\text{障碍物上侧第一个空位} & \text{向上} \
\text{障碍物下侧第一个空位} & \text{向下}
\end{cases}
]

常见错误

二分查找方向错误：add 函数中未正确比较 v[mid] >= x。
坐标越界：未处理移动后超出网格范围的情况。

改进建议

二分优化：使用 lower_bound 和 upper_bound 替代手写二分。
边界限制：添加 nowx 和 nowy 的范围约束。
代码复用：合并 add 和 sub 函数为通用移动逻辑。

T4 - 公告

完整代码

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

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]; }
    int size(int x) { return siz[find(x)]; }
private:
    int n;
    vector<int> fa, 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].insert(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 (auto j: edge[i]) d.merge(i, j + n);

    for (int i=q; i; i--) {
        ans.push(n - d.size(1));
        auto [u,v] = ask[i-1];
        d.merge(u, v + n);
    }
    while (!ans.empty()) cout << ans.top() << endl, ans.pop();
}

深度分析

关键公式
并查集合并：
[
\text{size}[y] += \text{size}[x]
]

常见错误

节点编号混淆：学生和边的编号未正确区分。
逆向处理错误：未正确恢复边的状态。

改进建议

节点编号设计：将学生和边的编号范围明确划分（如学生 1~n，边 n+1~n+m）。
离线处理优化：使用栈记录合并操作，逆向时撤销合并。
空间优化：改用 vector<vector<int>> 存储边。

T5 - 登塔

完整代码

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

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, m; cin >> n >> m;
    vector<vector<long long>> arr(n+1, vector<long long>(m+1));
    for (int i=1; i<=n; i++)
        for (int j=1; j<=m; j++)
            cin >> arr[i][j];

    vector<priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>>> f(n+1);
    f[0].push({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].push({arr[i][j] + f[i-1].top().first, j});
            else if (t.second != j)
                f[i].push({arr[i][j] + t.first, j});
            f[i-1].push(t);
            while (f[i].size() > 2) f[i].pop();
        }
    }

    long long 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[i][k] = \max_{j \neq k} f[i-1][j] + a[i][k]
]

常见错误

极值维护错误：优先队列未正确维护前两大值。
特殊情况处理：未处理 m=1 时无法移动的情况。

改进建议

极值优化：直接记录每一层的最大值和次大值，而非依赖优先队列。
边界处理：在 m=1 时，直接输出 arr[1][1]。
动态规划优化：将状态压缩为两个数组（当前层和前一层）。

T6 - 24点

完整代码

#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) + ")";
}

void solve() {
    vector<int> a(4);
    for (auto &i: a) cin >> i;
    queue<int> q1, q2, q3, q4, q5;

    for (auto i: a) {
        if (i % 8 == 0) q1.push(i);
        else if (i % 8 == 1 || i % 8 == 7) q2.push(i);
        else if (i % 8 == 2 || i % 8 == 4 || i % 8 == 6) q3.push(i);
        else q4.push(i);
    }

    string ans;
    if (!q1.empty()) ans = to_string(q1.front()), q1.pop();
    else if (q2.size() >= 2) ans = get(q2.front(), q2.back(), 8), q2.pop(), q2.pop();
    else if (q3.size() >= 2) ans = get(q3.front(), q3.back(), 8), q3.pop(), q3.pop();
    else ans = get(q4.front(), q4.back(), 8), q4.pop(), q4.pop();

    while (!q1.empty()) q5.push(q1.front()), q1.pop();
    while (!q2.empty()) q5.push(q2.front()), q2.pop();
    while (!q3.empty()) q5.push(q3.front()), q3.pop();
    while (!q4.empty()) q5.push(q4.front()), q4.pop();

    ans += "*" + get(q5, 3);
    while (!q5.empty()) 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();
}