比赛链接：https://codeforces.com/contest/1525

题意

开始时有一口空的大锅，每次操作可以向锅中加入 (1) 升魔法精华或 (1) 升水，问使魔法精华的比例为 (k \%) 最少需要操作多少次。

题解

(k \% = frac{k}{100}) ，分子分母同除以公因子后比例不变，操作次数减少，最少操作次数即除以最大公因子，即 (gcd(k, 100)) 。

代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int k;
        cin >> k;
        cout << 100 / gcd(k, 100) << "
";
    }
    return 0;
}

B. Permutation Sort

题意

给出一个大小为 (n) 的排列，每次操作可以将一个大小小于 (n) 的连续子数组重新排列，问将原排列变为升序至少需要操作多少次。

题解

• (0) 次：初始时为升序
• (1) 次：存在一个区间排序后整个数组为升序
• (2) 次： (1) 和 (n) 不同时位于尾部和首部
• (3) 次： (1) 和 (n) 同时位于尾部和首部

代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        if (is_sorted(a.begin(), a.end())) {
            cout << 0 << "
";
        } else {
            bool once = false;
            for (int l = 0; l < n; l++) {
                for (int r = l + 1; r <= n; r++) {
                    if (l == 0 and r == n) {
                        continue;
                    }
                    vector<int> b(a);
                    sort(b.begin() + l, b.begin() + r);
                    if (is_sorted(b.begin(), b.end())) {
                        once = true;
                    }
                }
            }
            cout << (once ? 1 : (a[0] == n and a[n - 1] == 1 ? 3 : 2)) << "
";
        }
    }
    return 0;
}

C. Robot Collisions

题意

有一数轴 (x) ，在 (0) 和 (m) 处有两面墙，两面墙内有 (n) 个机器人，坐标均为整数且两两不同。

机器人速度恒为 (1) 单位长度/秒，碰到墙后会向相反方向移动，若两个机器人同时到达某一整数坐标，则二者相撞并爆炸。

给出 (n) 个机器人的初始坐标和运动方向，计算每个机器人的相撞时间。

题解

首先只有初始时坐标奇偶性相同的机器人才有可能相撞。

其次最先相撞的是相邻且相向运动的两个机器人，即较小坐标向右，较大坐标向左的情况。

然后剩下的机器人运动状况为同时向左或同时向右且无交叉，以一前一后同时向左的情况为例：二者的相对距离在前者到达点 (0) 处之前是不变的，在前者到达点 (0) 处后二者开始相向运动。向右的情况同理。

最后一种可能相撞的情况是向左和向右运动的都还剩一个，这种情况可以看作二者从左右墙外对称点相向移动。

代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        vector<pair<int, char>> v(n);
        for (int i = 0; i < n; i++) {
            cin >> v[i].first;
        }
        for (int i = 0; i < n; i++) {
            cin >> v[i].second;
        }
        map<int, int> ans;
        auto solve = [&](const auto& v, int filter) {
            vector<pair<int, char>> vec;
            for (auto [x, dir] : v) {
                if (x % 2 == filter) {
                    vec.emplace_back(x, dir);
                }
            }
            sort(vec.begin(), vec.end());
            vector<int> L, R;
            for (auto [x, dir] : vec) {
                if (dir == 'L') {
                    if (R.size()) {
                        int y = R.back(); R.pop_back();
                        ans[x] = ans[y] = (x - y) / 2;
                    } else {
                        L.push_back(x);
                    }
                } else {
                    R.push_back(x);
                }
            } 
            reverse(L.begin(), L.end());
            while (L.size() > 1) {
                int x = L.back(); L.pop_back();
                int y = L.back(); L.pop_back();
                ans[x] = ans[y] = x + (y - x) / 2;
            }
            while (R.size() > 1) {
                int x = R.back(); R.pop_back();
                int y = R.back(); R.pop_back();
                ans[x] = ans[y] = (m - x) + (x - y) / 2;
            }
            if (L.size() and R.size()) {
                int x = L.back(); L.pop_back();
                int y = R.back(); R.pop_back();
                ans[x] = ans[y] = (x + (m - y) + m) / 2;
            }
        };
        solve(v, 0), solve(v, 1);
        for (auto [x, dir] : v) {
            cout << (ans.count(x) ? ans[x] : -1) << ' ';
        }
        cout << "
";
    }
    return 0;
}

D. Armchairs

题意

给出一个大小为 (n) ，由 (0,1) 构成的数组 (a) 。

把位于 (j) 的 (1) 移到位置 (i) 处的花费为 (abs(i - j)) ，一个位置只能放一个 (1) 。

问把所有 (1) 移动到初始为 (0) 处的最小花费。

题解

设 (dp_{ij}) 为前 (i) 个位置放前 (j) 个 (1) 的最小花费，则状态转移方程为：

(dp_{ij} = min(dp_{i-1 j},dp_{i-1 j-1} + abs(i - pos_j))) ，且后者仅当时当前位置初始为 (0) 才可取得。

Tips

不能贪心

8
0 0 1 1 0 1 1 0

代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<int> pos;
    for (int i = 0; i < n; i++) {
        if (a[i] == 1) {
            pos.push_back(i);
        }
    }
    vector<vector<int>> dp(n + 1, vector<int> (pos.size() + 1, 1e9));
    for (int i = 0; i <= n; i++) {
        dp[i][0] = 0;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= (int)pos.size(); j++) {
            dp[i][j] = min(dp[i - 1][j], (a[i - 1] == 0 ? dp[i - 1][j - 1] + abs(i - 1 - pos[j - 1]) : INT_MAX));
        }
    }
    cout << dp[n][pos.size()] << "
";
    return 0;
}