AtCoder Beginner Contest 320

A - Leyland Number (abc320 A)

题目大意

给定\(a,b\),输出 \(a^b + b^a\)

解题思路

因为数不超过\(10\),可以直接用 pow计算然后转成\(int\)。不会有精度损失。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int a, b;
    cin >> a >> b;
    cout << int(pow(a, b) + pow(b, a)) << '\n';

    return 0;
}



B - Longest Palindrome (abc320 B)

题目大意

给定一个字符串\(s\),求长度最长的回文串。

解题思路

因为长度只有\(100\),可以直接枚举子串,然后暴力判断是不是回文串(翻转后是否和自身相同),复杂度为 \(O(n^3)\)

数据范围大的话可以用Manachar算法\(O(n)\)

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    string s;
    cin >> s;
    int ans = 0;
    auto ok = [&](int l, int r) {
        string a = s.substr(l, r - l + 1);
        string b = a;
        reverse(b.begin(), b.end());
        return a == b;
    };
    for (int i = 0; i < s.size(); ++i)
        for (int j = i; j < s.size(); ++j) {
            if (ok(i, j))
                ans = max(ans, j - i + 1);
        }
    cout << ans << '\n';

    return 0;
}



C - Slot Strategy 2 (Easy) (abc320 C)

题目大意

给定\(n=3\)排灯,以及三个长度都为\(m\)的数字串,表示每一时刻,每盏灯依次循环地显示这些数字。

对于某一时刻,你最多只能按一个按钮,从而让一盏灯停下来。当然你可以什么都不操作。

问最终让三盏灯停下来时显示的数字都一样,需要的最短时间。

解题思路

考虑最朴素的做法,首先枚举最终情况下,显示的数字是什么,有\(10\)种情况。

然后考虑这三排灯按按钮的顺序,同样枚举这个顺序,有 \(3!\)种情况。

确定了数字和按按钮的顺序,剩下的就是模拟,只看一盏灯,然后出现这个数字时就按按钮,时间复杂度是 \(O(m)\)

最终的时间复杂度是\(O(n! \times 10nm)\)

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const int inf = 1e9;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int m;
    cin >> m;
    array<string, 3> s;
    for (auto& i : s)
        cin >> i;
    int ans = 1e9;
    for (int i = 0; i <= 9; ++i) {
        array<int, 3> id{};
        iota(id.begin(), id.end(), 0);
        do {
            int cur = 0;
            int tot = 0;
            for (auto& j : id) {
                if (s[j].find(i + '0') == string::npos) {
                    tot = inf;
                    break;
                }
                while (s[j][cur] - '0' != i) {
                    cur = (cur + 1) % m;
                    ++tot;
                }
                cur = (cur + 1) % m;
                ++tot;
            }
            ans = min(ans, tot);

        } while (next_permutation(id.begin(), id.end()));
    }
    if (ans == inf)
        ans = 0;
    cout << ans - 1 << '\n';

    return 0;
}



D - Relative Position (abc320 D)

题目大意

二维平面,有\(n\)个人,其中第一个人在原点。

给定 \(m\)条信息 \((a,b,x,y)\),表示第 \(b\)个人的位置是 \(a_x + x, a_y + y\)。其中\(a_x,a_y\)表示第 \(a\)个人的位置。

问每个人的位置,或告知不确定。

解题思路

初始只有第一个人的位置确定。那么所有与第一个人相关的信息的其他人的位置都能确定。

有更多的人的位置确定了,那么与这些人相关的信息的更多的人的位置都可以确定。

这感觉上就像是一个关系网,从第一个人往外传播,遍及到能遍及到的人。

这就是一张图,我们根据这些信息建立一张无向图,然后从\(1\)号点开始 \(BFS\),确定中间每个人的位置。

未遍历到的点就是位置不确定的人。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    vector<vector<array<int, 3>>> edge(n);
    for (int i = 0; i < m; ++i) {
        int a, b, x, y;
        cin >> a >> b >> x >> y;
        --a, --b;
        edge[a].push_back({b, x, y});
        edge[b].push_back({a, -x, -y});
    }
    queue<int> team;
    vector<int> ok(n);
    vector<array<LL, 2>> pos(n, {0, 0});
    ok[0] = 1;
    team.push(0);
    while (!team.empty()) {
        auto u = team.front();
        team.pop();
        for (auto& [v, x, y] : edge[u]) {
            if (!ok[v]) {
                pos[v] = {pos[u][0] + x, pos[u][1] + y};
                ok[v] = 1;
                team.push(v);
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        if (ok[i])
            cout << pos[i][0] << ' ' << pos[i][1] << '\n';
        else
            cout << "undecidable" << '\n';
    }

    return 0;
}



E - Somen Nagashi (abc320 E)

题目大意

给定\(n\)个人,从左到右。

\(q\)个事件,每个事件形如 \((t, w, s)\),表示第 \(t\)时刻,当前最左边的人可以获得 \(w\)的分数,然后离开,直到 \(t+s\)时刻回来。

问最后每个人的分数。

解题思路

朴素的思想就是每一时刻迭代,但时刻高达\(10^9\)。注意到有很多时刻都是无事发生的,因此我们只用考虑有事件发生的,即有人离开和有人回来。

问题需要维护两个信息,一个是最左边的人的标号(就是当前最小的标号),以及何时会有人回来这一事件的发生。

注意到每次都是剔除标号最小的人,以及获取的标号最小的人,因此可以用一个优先队列维护当前还在的人的标号,是个小根堆。

至于维护有人何时会回来这一事件,注意到这个事件是有一个发生时间\(t+s\),而我们是按照时间流逝依次处理的,因此我们可以用另一个优先队列维护这些时间,这样就可以动态插入新的事件,通过时间从小到大排序,以及当前时刻就能判断事件是否发生。

两个优先队列模拟这个过程即可。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    priority_queue<int> team;
    for (int i = 0; i < n; ++i)
        team.push(-i);
    priority_queue<array<int, 2>> event;
    vector<LL> ans(n);
    for (int i = 0; i < m; ++i) {
        int t, w, s;
        cin >> t >> w >> s;
        while (!event.empty() && -event.top()[0] <= t) {
            auto [_, u] = event.top();
            event.pop();
            team.push(-u);
        }

        if (!team.empty()) {
            int u = -team.top();
            team.pop();
            ans[u] += w;
            event.push({-(t + s), u});
        }
    }
    for (auto& i : ans)
        cout << i << '\n';

    return 0;
}



F - Fuel Round Trip (abc320 F)

题目大意

一维数轴,从\(0\)出发到 \(x_n\),再折返回来。

开车,油箱容量 \(h\),一距离消耗一单位汽油,有 \(n-1\)个加油站 ,对于第\(i\)个加油站,其位于 \(x_i\),可花\(p_i\)元加油 \(f_i\)单位汽油,但不能超过\(h\),超过部分则不要了,且花费价格不变 。

问出发再折返回来,消耗的最小钱数。注意一个加油站只能使用一次,这意味着如果过去用了,折返回来时不能再用了。

解题思路

本题有几个特别的地方,一个是油箱有上限,一个是加油是全加,另一个是有折返,加油站只能用一次。

如果没有加油站只能用一次的情况,注意到\(n\)\(h\)只有 \(300\)

考虑爆搜时的状态信息,我们可以保留 \(dp[i][j]\)表示到达第 \(i\)个加油站,此时还剩下 \(j\)升汽油的最小花费。然后枚举在第 \(i-1\) 个加油站时的汽油状态,考虑当前加油站是否加油,转移即可。

但是这个状态在返程时会有问题,因为对于第\(i\)个加油站能否加油,取决于去时是否加油,但这在状态里,这一信息没有保留下来。而记录每个加油站的使用状态,这是个指数级的状态,不行。

考虑棘手的地方,就是返程时到达了第\(i\)个加油站,此时无法做决策,因为我不知道来时,在第 \(i\)个加油站的状态。而如果我能一次就考虑第\(i\)个加油站,来回这两次的加油状态,就不会有上述问题。

思考如何一次就能考虑来回两次的状态 :即来时到达第\(i\)个加油站,此时有一个油箱量,回时到达第 \(i\)个加油站 ,也有一个油箱量。

\(dp[i][j][k]\)表示从\(i\)个加油站 出发,此时油箱量为\(j\),回来时油箱量为 \(k\)的最小费用。发现可以转移,枚举第\(i+1\)个加油站时的状态,以及考虑当前加油站来回时是否加油即可。

最后答案就是 \(dp[0][h][*]\)的最小值。初始条件为 \(dp[n][i][i] = 0\),其余为无穷大。

上述是 \(dp\)的整体方向,下述是一些实现细节,主要是由于油箱的上限和时间复杂度的优化。

代码里第一维是压缩掉了,实际维护的 \(dp[i][j][k][0/1]\)表示,在第 \(i\)个加油站,出发时 油箱量为\(j\),回来时为 \(k\),且回来时没加油/加了油的最小费用。注意这里的油箱量都是加油前的量,比如我选择出发时加了油,那么实际我转移时,容量起始为 \(min(j + f, h)\),如果我选择回来时加了油,那么实际转移时,容量起始为 \(min(k + f, h)\)

循环枚举的 \(j\)是从第 \(i\)个加油站出发时的油量, \(k\)是从第 \(i+1\)个加油站回来时的油量。

这样在转移时直接通过路程来计算 去到\(i+1\)时 油量和回到\(i\)时的油量,不然如果枚举的都是第 \(i\)个加油站的状态的话,如果回来时加油了,且 \(k\)\(h\),要从\(i+1\)转移过来,这要考虑它的加油前的状态 ,分别有\(h, h - 1, h - 2, ..., h - f\),这又会有 \(O(h)\)的状态要枚举。

新增的 \(0/1\)状态也是为了能够转移而加上的。

于是代码看着就比较复杂了(但是大方向是上述的三维\(dp\),应该会有更优美的实现方式。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const int inf = 1e9;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, h;
    cin >> n >> h;
    vector<int> pos(n + 1, 0);
    for (int i = 1; i <= n; ++i)
        cin >> pos[i];
    vector<array<int, 2>> info(n + 1, {0, 0});
    for (int i = 1; i < n; ++i) {
        cin >> info[i][0] >> info[i][1];
    }
    vector<vector<array<int, 2>>> dp(h + 1,
                                     vector<array<int, 2>>(h + 1, {inf, inf}));
    for (int i = 0; i <= h; ++i)
        dp[i][i][0] = 0;
    for (int i = n - 1; i >= 0; --i) {
        vector<vector<array<int, 2>>> dp2(
            h + 1, vector<array<int, 2>>(h + 1, {inf, inf}));
        int dis = pos[i + 1] - pos[i];
        auto [p, f] = info[i];
        auto [np, nf] = info[i + 1];
        for (int j = 0; j <= h; ++j) {
            for (int k = 0; k <= h; ++k) {

                if (j - dis >= 0 && k - dis >= 0)
                    dp2[j][k - dis][0] =
                        min(dp2[j][k - dis][0], dp[j - dis][k][0]);

                if (j - dis >= 0 && min(k + nf, h) - dis >= 0)
                    dp2[j][min(k + nf, h) - dis][0] =
                        min(dp2[j][min(k + nf, h) - dis][0], dp[j - dis][k][1]);

                if (min(j + f, h) - dis >= 0 && k - dis >= 0)
                    dp2[j][k - dis][0] = min(dp2[j][k - dis][0],
                                             dp[min(j + f, h) - dis][k][0] + p);

                if (min(j + f, h) - dis >= 0 && min(k + nf, h) - dis >= 0)
                    dp2[j][min(k + nf, h) - dis][0] =
                        min(dp2[j][min(k + nf, h) - dis][0],
                            dp[min(j + f, h) - dis][k][1] + p);

                if (j - dis >= 0 && k - dis >= 0)
                    dp2[j][k - dis][1] =
                        min(dp2[j][k - dis][1], dp[j - dis][k][0] + p);

                if (j - dis >= 0 && min(k + nf, h) - dis >= 0)
                    dp2[j][min(k + nf, h) - dis][1] = min(
                        dp2[j][min(k + nf, h) - dis][1], dp[j - dis][k][1] + p);
            }
        }
        dp.swap(dp2);
    }

    int ans = inf;
    for (int i = 0; i <= h; ++i)
        ans = min(ans, dp[h][i][0]);
    if (ans == inf)
        ans = -1;
    cout << ans << '\n';

    return 0;
}



G - Slot Strategy 2 (Hard) (abc320 G)

题目大意

给定\(n\)排灯,以及长度都为\(m\)的数字串,表示每一时刻,每盏灯依次循环地显示这些数字。

对于某一时刻,你最多只能按一个按钮,从而让一盏灯停下来。当然你可以什么都不操作。

问最终让\(n\)盏灯停下来时显示的数字都一样,需要的最短时间。

解题思路

<++>

神奇的代码



热门相关:神秘总裁小小妻   魔神狂后   网游三国之城市攻略   魔神狂后   楚氏赘婿