ABC369(A-F)

A - 369 ¶

题目大意

给你两个数字 \(A\) 和 \(B\)，求出有多少个数字 \(x\) 满足以下条件：

对于数字 \(A\)，\(B\) 和 \(x\)，存在一种重排的方式使其成为等差数列。

参考代码

C++

#include <iostream>

using namespace std;

int main()
{
    int a, b;
    cin >> a >> b;
    if (a > b)
        swap(a, b);
    if (a == b)
        cout << 1 << endl;
    else if ((a + b) % 2 != 0)
        cout << 2 << endl;
    else
        cout << 3 << endl;
    return 0;
}

有一个钢琴有 \(100\) 个按键。你打算演奏一首具有 \(N\) 个音符的歌曲。你打算用左手或者右手按第 \(i\) 个音符，第 \(i\) 个音符是钢琴上从左到右数的第 \(A_i\) 个按键，同时，如果 \(S_i\) 是 L，表示你打算用左手按这个按键，如果 \(S_i\) 是 R，表示你打算用右手按这个按键。当你将某只手从第 \(x\) 个按键移动到第 \(y\) 个按键时，你将积累 \(|x-y|\) 的疲劳值。在演奏开始前，你可以将两只手放置在任意按键上。

问：演奏完成后，至少会积累多少疲劳值？

解题思路

将左手放在第一个 \(S_i\) 是 L 的位置，右手放在第一个 \(S_i\) 是 R 的位置，得到的结果一定是最小的。

参考代码

C++

#include <iostream>

using namespace std;

int main()
{
    int n;
    cin >> n;
    int l = 0, r = 0, ans = 0;
    while (n--)
    {
        int a;
        char s;
        cin >> a >> s;
        if (s == 'L')
        {
            if (l == 0)
                l = a;
            ans += abs(l - a);
            l = a;
        }
        else
        {
            if (r == 0)
                r = a;
            ans += abs(r - a);
            r = a;
        }
    }
    cout << ans << endl;
    return 0;
}

C - Count Arithmetic Subarrays ¶

题目大意

给你一个包含 \(N(1 \le N \le 2 \times 10^5)\) 个数字的数组 \(A = (A_1, A_2, \cdots, A_N)\)，求出 \(A\) 中有多少个子数组是等差数列。（注：长度为 \(1\) 或 \(2\) 的子数组也认为是等差数列）

解题思路

做一遍差分，差分数组中连续相等差值就会形成长度大于等于 \(2\) 的等差数列。

参考代码

C++

#include <iostream>
#include <vector>

using namespace std;
using LL = long long;

int main()
{
    int n;
    cin >> n;
    vector<int> d(n);
    for (int i = 0; i < n; i++)
        cin >> d[i];
    for (int i = n - 1; i; i--)
        d[i] -= d[i - 1];
    LL ans = n;
    for (int i = 0; i < n - 1;)
    {
        int j = i + 1, t = d[j];
        while (j + 1 < n && d[j+1] == t)
            j++;
        LL k = j - i + 1;
        ans += k * (k - 1) / 2;
        i = j;
    }
    cout << ans << endl;
    return 0;
}

D - Bonus EXP ¶

题目大意

有 \(N(1 \le N \le 2 \times 10^5)\) 只怪物，第 \(i\) 只怪物的力量是 \(A_i\)。从第 \(1\) 只怪物开始，对于每一只怪物，你可以选择击败这只怪物或者逃走。如果你逃走了，你不会获得任何经验值。如果你选择击败这只的怪物，你会获得 \(A_i\) 的经验值，此外，如果这是你击败的第偶数只怪物，你将额外获得 \(A_i\) 的经验值。问：最多能获得多少经验值？

解题思路

定义 \(dp[i][j]\) 表示处理完前 \(i\) 只怪物，且累计击败怪物数量的奇偶性为 \(j\) 的所有方案中，能获得的经验值的最大值。转移的时候，只需要考虑是否击败第 \(i\) 只怪物，按照奇偶性转移即可。

参考代码

C++

#include <iostream>
#include <limits>

using namespace std;
using LL = long long;

int main()
{
    int n;
    cin >> n;
    LL dp[2][2], *now = dp[0], *pre = dp[1];
    now[0] = 0, now[1] = numeric_limits<LL>::min() / 2;
    while (n--)
    {
        swap(now, pre);
        int a;
        cin >> a;
        now[0] = max(pre[0], pre[1] + 2 * a);
        now[1] = max(pre[1], pre[0] + a);
    }
    cout << max(now[0], now[1]) << endl;
    return 0;
}

E - Sightseeing Tour ¶

题目大意

给你一个 \(N(1 \le N \le 400)\) 个点，\(M(N-1 \le M \le 2 \times 10^5)\) 条边的无向有权图。图中没有自环，但可能有重边。给你 \(Q(1 \le Q \le 3000)\) 个询问，每个询问给你 \(K(1 \le K \le 5)\) 条边的编号 \(B_{i, 1}, B_{i,2}, \cdots, B_{i, K_i}\)，你需要找到一条从以点 \(1\) 为起点，以点 \(N\) 为终点，且包含这 \(K\) 条边的最短路，输出这条路的长度。

解题思路

由于 \(N \le 400\)，可以用 Floyd 算法求出任意两点的距离。又因为 \(K \le 5\)，直接暴力的枚举 \(K\) 条路的全排列代表顺序，再枚举每条路实际走的方向，然后按照任意两点的距离求和就能算出答案，时间复杂度 \(O(N^3 + Q2^KK!)\)

参考代码

C++

#include <algorithm>
#include <iostream>
#include <limits>
#include <vector>

using namespace std;
using LL = long long;

const int MAXK = 5;
const LL INF = numeric_limits<LL>::max() / 2;

int main()
{
    int n, m;
    cin >> n >> m;
    vector<vector<LL>> dis(n + 1, vector<LL>(n + 1, INF));
    vector<int> u(m + 1), v(m + 1);
    vector<LL> t(m + 1);
    for (int u = 1; u <= n; u++)
        dis[u][u] = 0;
    for (int i = 1; i <= m; i++)
    {
        cin >> u[i] >> v[i] >> t[i];
        dis[u[i]][v[i]] = dis[v[i]][u[i]] = min(t[i], dis[u[i]][v[i]]);
    }
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
    int q;
    cin >> q;
    int b[MAXK];
    while (q--)
    {
        int k;
        cin >> k;
        int len = 1 << k;
        for (int i = 0; i < k; i++)
            cin >> b[i];
        LL ans = INF;
        do
        {
            for (int s = 0; s < len; s++)
            {
                LL sum = 0;
                int now = 1;
                for (int i = 0; i < k; i++)
                {
                    int e = b[i];
                    if (s >> i & 1)
                    {
                        sum += dis[now][u[e]] + t[e];
                        now = v[e];
                    }
                    else
                    {
                        sum += dis[now][v[e]] + t[e];
                        now = u[e];
                    }
                }
                ans = min(ans, sum + dis[now][n]);
            }
        } while (next_permutation(b, b + k));
        cout << ans << endl;
    }
    return 0;
}

F - Gather Coins ¶

题目大意

有一个 \(H \times W(1 \le H, W \le 2 \times 10 ^5)\) 的网格，网格中有 \(N(1 \le N \le \min(HW-2, 2 \times 10 ^ 5))\) 个硬币，第 \(i\) 个硬币的位置是 \((R_i, C_i)\)。初始的时候你在 \((1, 1)\)，目的地是 \((H, W)\)，每一步可以向右或者向下走。当你走到一个有硬币的格子时，你会捡起硬币。问：最多能捡起多少个硬币？输出从起点到终点能获得最多硬币的路径。

解题思路

因为每一步只能向右或者向下走，假设当前的位置是 \((R_x, C_x)\)，对于另一个位置 \((R_y, C_y)\)，仅当 \(R_x \le R_y\) 且 \(C_x \le C_y\) 时，才可以从 \((R_x, C_x)\) 走到 \((R_y, C_y)\)。于是问题等价于求出一个最长且可行的硬币序列。只需要对 \(R_i\) 排序，然后求出 \(C_i\) 的最长上升子序列即可。

参考代码

C++

#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>

using namespace std;

int main()
{
    int h, w, n;
    cin >> h >> w >> n;
    vector<pair<int, int>> coin(n);
    for (int i = 0; i < n; i++)
    {
        cin >> coin[i].first >> coin[i].second;
        coin[i].first--;
        coin[i].second--;
    }
    sort(coin.begin(), coin.end());
    vector<int> dp(n), col;
    dp[0] = 1;
    col.push_back(coin[0].second);
    for (int i = 1; i < n; i++)
    {
        int c = coin[i].second;
        if (c >= col.back())
        {
            col.push_back(c);
            dp[i] = col.size();
        }
        else
        {
            int pos = upper_bound(col.begin(), col.end(), c) - col.begin();
            col[pos] = c;
            dp[i] = pos + 1;
        }
    }
    int id = 0;
    for (int i = 1; i < n; i++)
        if (dp[i] > dp[id])
            id = i;
    auto print_ans = [&dp, &coin](auto &self, int id) -> void
    {
        auto [r, c] = coin[id];
        if (dp[id] == 1)
        {
            while (r--)
                cout << "D";
            while (c--)
                cout << 'R';
            return;
        }
        for (int pre = id - 1; pre >= 0; pre--)
            if (coin[pre].second <= c && dp[pre] + 1 == dp[id])
            {
                self(self, pre);
                int dr = r - coin[pre].first;
                int dc = c - coin[pre].second;
                while (dr--)
                    cout << "D";
                while (dc--)
                    cout << 'R';
                return;
            }
    };
    cout << dp[id] << endl;
    print_ans(print_ans, id);
    int dr = h - coin[id].first - 1;
    int dc = w - coin[id].second - 1;
    while (dr--)
        cout << "D";
    while (dc--)
        cout << 'R';
    return 0;
}

最后更新: 2024-12-03
创建日期: 2024-12-03

ABC369(A-F)

A - 369¶

B - Piano 3¶

C - Count Arithmetic Subarrays¶

D - Bonus EXP¶

E - Sightseeing Tour¶

F - Gather Coins¶

A - 369 ¶

B - Piano 3 ¶

C - Count Arithmetic Subarrays ¶

D - Bonus EXP ¶

E - Sightseeing Tour ¶

F - Gather Coins ¶