AtCoder Beginner Contest 358

A - Welcome to AtCoder Land (abc358 A)

题目大意

给定两个字符串,问是否是AtCoder Land

解题思路

读取后判断即可。

神奇的代码
#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, t;
    cin >> s >> t;
    if (s == "AtCoder" && t == "Land")
        cout << "Yes" << '\n';
    else
        cout << "No" << '\n';

    return 0;
}



B - Ticket Counter (abc358 B)

题目大意

售票厅,\(n\)个人来买票,每个人买票耗时\(a\)。第 \(i\)个人 \(t_i\)时刻来 ,如果此时没人买票则可以立刻买票,否则要排队等买票。

问每个人最终买到票的时间。

解题思路

维护队伍无人的时间\(time\),当第\(i\)个人来时,

  • \(time \leq t_i\),则其可以立刻买票,买完票时间为 \(t_i + a\),此时队伍无人的时间变为 \(time = t_i + a\)
  • \(time > t_i\),则其需要等待至队伍无人时间\(time\),买完票时间为 \(time + a\),此时队伍无人的时间变为 \(time = time + a\)

按照上述方式模拟即可。

神奇的代码
#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, a;
    cin >> n >> a;
    int time = 0;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        if (time <= x) {
            time = x + a;
        } else
            time = time + a;
        cout << time << '\n';
    }

    return 0;
}



C - Popcorn (abc358 C)

题目大意

给定\(n\)个小摊售卖的爆米花种类。

问选择的最少的小摊数量,可以买到所有爆米花种类。

解题思路

由于\(n \leq 10\),直接 \(O(2^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);
    int n, m;
    cin >> n >> m;
    vector<int> a(n, 0);
    for (auto& x : a) {
        string s;
        cin >> s;
        for (auto c : s) {
            x = x * 2 + (c == 'o');
        }
    }
    int ans = n, up = (1 << n);
    for (int i = 0; i < up; i++) {
        int cnt = 0;
        for (int j = 0; j < n; j++) {
            if (i & (1 << j)) {
                cnt |= a[j];
            }
        }
        if (cnt == (1 << m) - 1) {
            ans = min(ans, __builtin_popcount(i));
        }
    }
    cout << ans << '\n';

    return 0;
}



D - Souvenirs (abc358 D)

题目大意

\(n\)个盒子,第 \(i\)个盒子价格 \(a_i\),有 \(a_i\)个糖果。

\(m\)个盒子给 \(m\)个人,其中第 \(i\)个人的盒子的糖果数至少有 \(b_i\)个。

问花费价格的最少值,或告知不可行。

解题思路

考虑每个人,买哪个盒子给他。

由于盒子的糖果数和价格是相当的,那对于每个人的\(b_i\),肯定是选择\(\geq b_i\)的最小的 \(a_i\),二分查找即可。由于每个盒子只能买一次,因此得将其删去,用 multiset维护即可。

下述代码可以解决糖果数与价格不相当的情况,按照\(b_i\)从大到小考虑,那我肯定是贪心地选最小价格的盒子,满足 \(a_i \geq b_i\)。用优先队列维护这个最小值即可,而剩下未选择的盒子都可以满足后续的 \(b_i\)。而按 \(b_i\)从小到大考虑的话,可能会使得不可行。

神奇的代码
#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<int> a(n), b(n);
    for (auto& x : a)
        cin >> x;
    for (auto& x : b)
        cin >> x;
    sort(a.begin(), a.end(), greater<int>());
    sort(b.begin(), b.end(), greater<int>());
    priority_queue<int, vector<int>, greater<int>> q;
    bool ok = true;
    LL ans = 0;
    for (int i = 0, j = 0; i < m; i++) {
        while (j < n && a[j] >= b[i]) {
            q.push(a[j]);
            j++;
        }
        if (q.empty()) {
            ok = false;
            break;
        }
        ans += q.top();
        q.pop();
    }
    if (!ok)
        ans = -1;
    cout << ans << '\n';

    return 0;
}



E - Alphabet Tiles (abc358 E)

题目大意

给定\(k\)\(26\)\(c_i\),问字符串数量,其 长度在\(1 \sim k\)之间,且第 \(i\)个字母的出现次数不超过 \(c_i\)

解题思路

先枚举长度\(len\),然后考虑 \(len\)个字母分别是什么字母。

考虑每个字母使用的数量,可以发现我们只需知道此时剩余字母数,就可以作出转移。

\(dp[i][j]\)表示使用了前 \(i\)类字母,填了\(j\) 个空位的方案数。

枚举当前字母使用的数量\(k\),转移则为\(dp[i][j + k] += dp[i - 1][j] \times C_{len - j}^{k}\),即要从当前剩余的\(len - j\)个空位选 \(k\)个作为当前的字母。

状态数是 \(O(26n)\),转移是 \(O(n)\),加上我们一开始枚举的长度复杂度 \(O(n)\),总的时间复杂度是 \(O(26n^3)\),由于 \((n \leq 10^3\),会超时。

考虑优化,容易发现枚举不同的长度计算每个\(dp[i][j]\),会有很多重复的计算。但是转移代价会依赖总长度\(len\)

考虑我们先计算 \(len = k\)\(dp[i][j]\),即长度为 \(k\)的符合条件的字符串数量,看看能否得到其余 \(len\)的数量。

很显然\(dp[26][k]\)是长度为 \(k\)的字符串数量,而 \(dp[26][k-1],dp[26][k-2],...\)同样是长度为 \(k\)的字符串,但有 \(1,2,...\)个空位上的字母是未确定的,其中空位的位置也有很多种情况。

\(dp[26][k-1]\)为例,它表示考虑了前 \(26\)个字母,填了 \(k-1\)个空位的方案数,此时还有一个空位。它相当于是,原先\(k-1\)个字母的方案数,再插入一个空位。 而空位的位置数量有 \(C_{k}^{1}\)种, 考虑 \(\frac{dp[26][k-1]}{C_{k}^{1}}\),即将空位的情况数去掉,其值就变成了长度为 \(k-1\)的符合条件的字符串数量。

其余情况同理。这就把枚举长度的复杂度优化掉了。

因此答案就是 \(\sum_{i=1}{k} \frac{dp[26][k - i]}{C_{n}^{i}}\),总的时间复杂度是 \(O(26n^2)\)

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

const int mo = 998244353;

long long qpower(long long a, long long b) {
    long long qwq = 1;
    while (b) {
        if (b & 1)
            qwq = qwq * a % mo;
        a = a * a % mo;
        b >>= 1;
    }
    return qwq;
}

long long inv(long long x) { return qpower(x, mo - 2); }

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    array<int, 26> cnt;
    for (auto& x : cnt)
        cin >> x;
    vector<int> dp(n + 1);
    dp[0] = 1;
    vector<int> fac(n + 1, 1), ifac(n + 1, 1);
    for (int i = 1; i <= n; ++i) {
        fac[i] = 1ll * fac[i - 1] * i % mo;
    }
    ifac[n] = inv(fac[n]);
    for (int i = n - 1; i >= 0; --i) {
        ifac[i] = 1ll * ifac[i + 1] * (i + 1) % mo;
    }
    auto C = [&](int n, int m) -> int {
        if (n < m)
            return 0;
        return 1ll * fac[n] * ifac[m] % mo * ifac[n - m] % mo;
    };
    for (int i = 0; i < 26; ++i) {
        vector<int> dp2(n + 1, 0);
        for (int j = 0; j <= n; ++j) {
            for (int k = 0; k <= cnt[i] && j + k <= n; ++k) {
                dp2[j + k] = (dp2[j + k] + 1ll * dp[j] * C(n - j, k) % mo) % mo;
            }
        }
        dp.swap(dp2);
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        ans = (ans + 1ll * dp[i] * inv(C(n, n - i)) % mo) % mo;
    }
    cout << ans << '\n';

    return 0;
}



F - Easiest Maze (abc358 F)

题目大意

给定\(n,m,k\),构造一个 \(n \times m\)的迷宫,从右上走到右下,路径唯一,长度为 \(k\)

解题思路

<++>

神奇的代码



G - AtCoder Tour (abc358 G)

题目大意

给定一个二维网格,格子上有数。

给定起点,重复以下操作\(k\)次。

  • 每次操作,要么不动,要么上下左右四个方向选一个移动一格。操作完后,获得收益,收益为格子上的数。

问最优操作下的收益和的最大值。

解题思路

观察最优情况的特点,一定是从起点出发,到达某一个点,然后一直停留直到操作次数到达\(k\)

因此首先枚举终点\(a_{ij}\),然后计算从起点到终点,怎样走收益最大。

我从起点到达终点时,路径有很多,不同路径下,最终收益不一样,而最终收益关系到两个状态:已经获得的收益值\(presum\),还剩下的操作次数\(cnt\)

收益最大,则要求\(presum + cnt \times a_{ij}\)最大。

观察上述式子,它并不意味着我越短路径到达\(a_{ij}\)是最优的。

考虑一极端情况, \(x \to y\)耗时三步,收益为 \(1,1\)\(a_y=10^6\),而另一个方案,耗时五步,收益为\(10^6-1, 10^6-1, 10^6 - 1,10^6-1\),两种方案,后面的 \(k-4\)操作的收益相同,而前 \(4\)次的收益,显然是后者高:虽然后者耗时5步,但损失很少:只有\(4\),而前者虽然耗时 \(3\)步,但每步的损失高达 \(10^6\)。这启示我们要以最小损失代价到达终点。

换句话说,对上述式子变形,注意到 \(presum = \sum_{k - cnt} a_x\),即 \(k-cnt\)\(a_x\)的和,我们将式子改写成 \(k \times a_{ij} - (k - cnt) a_{ij} + \sum_{k - cnt} a_x\)。注意到后两项的项数相同,合并一下,得到

\[k \times a_{ij} - \sum_{k - cnt}(a_{ij} - a_x) \]

前一项是一个定值,而后一项可以假象在一个新的网格图上走,格子数变为\(b_x = a_{ij} - a_x\)(上述的损失代价),问 从起点到终点的最短路径(损失代价最小)。 这么操作其实就相当于把步数损失放到每一步的计算里,从而消去了棘手的\(cnt\)(这个平均值的处理技巧差不多)

但有个问题是,最短路径里,边权有负(\(x \to y\),边权是 \(b_y\) ),则求起点到终点的最短路,不能用\(dijkstra\),但这是网格图, \(SPFA\)会被卡死了。怎么办呢。

可以先考虑终点取 \(a_{ij}\)最大的,那么 \(b_x\)都是正的,此时可以用 \(dijkstra\)求最短路。然后考虑次大的 \(a_{ij}\),则原本 最大的格子的 \(b_x\)变成负的,此时求最短路怎么办呢?细想会发现,如果最短路会经过这个负格子,那我可以就停留在这个格子上(这样我的损失代价会不断减小),这样最终收益比到达终点更大。

因此会发现这个最短路径中,它不会经过 \(b_x\)是负数的格子。由此实际上就是一个正权的 \(dijkstra\)最短路问题。

由此求出最短路径,即最小损失代价,从而就知道此时终点的最优收益。对所有终点的最优收益取个最大值即为答案。

枚举终点的复杂度是\(O(n^2)\)\(dijkstra\)的复杂度是 \(O(n^2 \log n)\),因此总的时间复杂度为\(O(n^4 \log 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);
    int h, w, k, sx, sy;
    cin >> h >> w >> k >> sx >> sy;
    --sx, --sy;
    vector<vector<int>> a(h, vector<int>(w));
    for (auto& i : a)
        for (auto& j : i)
            cin >> j;
    LL ans = 0;
    array<int, 4> dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};
    auto solve = [&](int ex, int ey) {
        LL sum = 1ll * a[ex][ey] * k;
        vector<vector<int>> cost(h, vector<int>(w));
        for (int i = 0; i < h; ++i)
            for (int j = 0; j < w; ++j)
                cost[i][j] = a[ex][ey] - a[i][j];
        priority_queue<pair<LL, pair<int, int>>> team;
        vector<vector<LL>> dis(h, vector<LL>(w, numeric_limits<LL>::max()));
        team.push({0, {sx, sy}});
        dis[sx][sy] = 0;
        while (!team.empty()) {
            auto [d, p] = team.top();
            team.pop();
            auto [x, y] = p;
            if (dis[x][y] < -d)
                continue;
            for (int i = 0; i < 4; ++i) {
                int nx = x + dx[i], ny = y + dy[i];
                if (nx < 0 || nx >= h || ny < 0 || ny >= w)
                    continue;
                if (cost[nx][ny] < 0)
                    continue;
                if (dis[nx][ny] > -d + cost[nx][ny]) {
                    dis[nx][ny] = -d + cost[nx][ny];
                    team.push({-dis[nx][ny], {nx, ny}});
                }
            }
        }
        return sum - dis[ex][ey];
    };
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            if (a[i][j] >= a[sx][sy]) {
                LL ret = solve(i, j);
                ans = max(ans, ret);
            }
        }
    }
    cout << ans << '\n';

    return 0;
}



热门相关:无敌天下   万里情深不负   隐婚101天:唐少宠妻成瘾   巨星小甜妻:前夫,请出局   极品明君