526互联

AtCoder Beginner Contest 326

发布时间 2023-10-28 23:06:26作者: ~Lanly~

A - 2UP3DOWN (abc326 A)

题目大意

100楼层，一次可以上最多两层，或下最多三层。

给定两楼层，问能否一次到达。

解题思路

比较大小，然后判断其差是是不是在\(2\)或 \(3\)内即可。

神奇的代码 
#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 x, y;
    cin >> x >> y;
    if (x > y && x - y <= 3)
        cout << "Yes" << '\n';
    else if (x <= y && y - x <= 2)
        cout << "Yes" << '\n';
    else
        cout << "No" << '\n';

    return 0;
}

B - 326-like Numbers (abc326 B)

题目大意

给定一个\(n\)，问不小于 \(n\)的形如 \(326\)的数字是多少。

形如 \(326\)的数字，即数位有 \(3\)，且百位 \(\times\)十位 \(=\)个位。

解题思路

只有\(1000\)个数，枚举判断即可。

神奇的代码 
#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;
    cin >> n;
    auto is_326 = [](int x) {
        auto s = to_string(x);
        return (s[0] - '0') * (s[1] - '0') == (s[2] - '0');
    };
    while (!is_326(n))
        ++n;
    cout << n << '\n';

    return 0;
}

C - Peak (abc326 C)

题目大意

给定一维数轴上的\(n\)个礼物点，问长度为\(M\)的左闭右开的区间最多有多少个点。

解题思路

注意到最好情况下，其区间的左端点一定是礼物点。

因此我们可以枚举左端点所在的礼物点，然后看看到右端点时包含了多少个礼物。这个可以先对礼物点排序然后二分找到右端点礼物，作差得到数量。

当然也可以双指针。

ranges::的用法是c++20的特性。

神奇的代码 
#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);
    for (auto& i : a)
        cin >> i;
    ranges::sort(a);
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        ans = max(ans, int(ranges::lower_bound(a, a[i] + m) - a.begin() - i));
    }
    cout << ans << '\n';

    return 0;
}

D - ABC Puzzle (abc326 D)

题目大意

给定两个仅包含ABC的长度为\(n\)的串\(a,b\)，要求构造一个\(n \times n\)的矩阵，要求：

  • 每行每列包含恰好一个ABC
  • 每行最左边的字母组成字符串\(a\)
  • 每列最顶部的字母组成字符串\(a\)

解题思路

因为\(n\)只有 \(5\)，考虑朴素搜索。

每行ABC的排列情况只有\(5 \times 4 \times 3 = 60\)种， \(5\)行的总情况为 \(60^5 = 7e9\)，但如果中间剪枝的话其合法情况数远远小于该数。

具体来说，考虑当前位置 \((x,y)\)放什么，我们需要第 \(x\)行的放置情况 \(row[x]\)，第 \(y\)列的放置情况 \(col[y]\)，以决定该位置能否放该字母（代码里是二进制压缩的状态）。还需要 \(left[x]\)表示第 \(x\)行的是否放过字母，以决定是否和字符串 \(a\)比较，同理也需要 \(top[y]\)表示第 \(y\)列是否放过字母，以决定是否和字符串 \(b\)比较。这里的剪枝可以减去大部份合法情况。

在考虑完一行后，可以看看 \(row[x]\)是否放了ABC三个字母，没放满则直接剪枝。

感觉写的很复杂。

神奇的代码 
#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;
    string a, b;
    cin >> n >> a >> b;
    vector<vector<int>> ans(n, vector<int>(n, -1));
    vector<int> top(n, 1);
    vector<int> left(n, 1);
    vector<int> row(n);
    vector<int> col(n);
    auto not_have = [&](int x, int y) { return ((~x >> y) & 1); };
    function<bool(int, int)> dfs = [&](int x, int y) {
        if (x == n) {
            for (auto& i : row)
                if (i != 7)
                    return false;
            for (auto& i : col)
                if (i != 7)
                    return false;
            return true;
        }

        for (int i = 0; i < 3; ++i) {
            if (not_have(row[x], i) && not_have(col[y], i)) {
                if (top[y] && b[y] - 'A' != i)
                    continue;
                if (left[x] && a[x] - 'A' != i)
                    continue;
                row[x] |= (1 << i);
                col[y] |= (1 << i);
                ans[x][y] = i;

                int ttop = top[y], lleft = left[x];
                top[y] = 0;
                left[x] = 0;
                if (y == n - 1) {
                    if (row[x] == 7 && dfs(x + 1, 0))
                        return true;
                } else {
                    if (dfs(x, y + 1))
                        return true;
                }
                row[x] ^= (1 << i);
                col[y] ^= (1 << i);
                ans[x][y] = -1;
                top[y] = ttop;
                left[x] = lleft;
            }
        }

        if (y == n - 1) {
            if (row[x] != 7)
                return false;

            if (dfs(x + 1, 0))
                return true;
        } else {
            if (dfs(x, y + 1))
                return true;
        }

        return false;
    };
    if (dfs(0, 0)) {
        cout << "Yes" << '\n';
        for (auto& i : ans) {
            for (auto& j : i) {
                if (j == -1)
                    cout << '.';
                else
                    cout << char(j + 'A');
            }
            cout << '\n';
        }
    } else
        cout << "No" << '\n';

    return 0;
}

E - Revenge of "The Salary of AtCoder Inc." (abc326 E)

题目大意

给定包含\(n\)个数字的数组 \(a\)，以及一个等概率的 \(n\)面骰子。进行以下游戏：

初始\(x=0\)，投掷一次骰子，得到 \(y\)

  • 如果\(x < y\)，则获得 \(a_y\)元，同时令 \(x=y\)
  • 否则游戏结束

问期望获得的钱数。

解题思路

期望题，根据定义，一个状态的期望，它是所有后继状态的期望的加权平均，这里的权重是概率。

当前状态是\(x\)，则设\(dp[x]\)表示当前掷出的值为 \(x\)，继续游戏至游戏结束，这期间获得的期望钱数。

很显然初始条件 \(dp[n] = 0\)，即 \(x=n\)时，无论怎么骰，始终有 \(y \leq n\)，游戏总是会结束。

考虑一般情况，当前状态是\(x\)，考虑投掷一次骰子的后继状态：

  • 有\(\frac{x}{n}\)的概率投掷出\(y \leq x\)，此时游戏结束，后继状态的期望收入为 \(0\)。
  • 有\(\frac{1}{n}\)的概率投掷出\(y = x + 1\)，此时进入后继状态\(dp[x+1]\)，获得收益\(a_{x+1}\)
  • 有\(\frac{1}{n}\)的概率投掷出\(y = x + 2\)，此时进入后继状态\(dp[x+2]\)，获得收益\(a_{x+2}\)
  • 有\(\frac{1}{n}\)的概率投掷出\(y = x + 3\)，此时进入后继状态\(dp[x+3]\)，获得收益\(a_{x+3}\)
  • ...
  • 有\(\frac{1}{n}\)的概率投掷出\(y = n\)，此时进入后继状态\(dp[n]\)，获得收益\(a_{n}\)

由此可以写出转移式子：

\[dp[x] = \frac{x}{n} \times 0 + \sum_{i=x+1}^{n}\frac{1}{n} (dp[i] + a[i]) = \frac{1}{n}\sum_{i=x+1}^{n}(dp[i] + a[i]) \]

这是一个后缀和，求\(dp\)的时候维护一下就可以了。观察到\(dp\)数组和后缀和的关系，代码里直接把\(dp\)数组省掉了。

神奇的代码 
#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;
    vector<int> a(n);
    for (auto& i : a)
        cin >> i;
    int presum = 0, invn = inv(n);
    for (int i = n - 1; i >= 0; --i) {
        presum = (0ll + presum + 1ll * presum * invn % mo + a[i]) % mo;
    }
    cout << 1ll * presum * invn % mo << '\n';

    return 0;
}

F - Robot Rotation (abc326 F)

题目大意

二维平面，机器人初始 \((0,0)\)，面向\(x\)轴正方向。给定\(n\)次移动的距离数组\(d\)，每次移动前，你需要指定机器人顺时针或逆时针转 \(90\)度，随后移动。

问能否移动到达目标点 \((x,y)\)，能移动到则给出一个可行的旋转序列。

解题思路

注意到\(n\)只有\(80\)，且每次必须旋转机器人，这意味着机器人有一半是上下移动，一半是左右移动，最多 \(40\)次。

横纵坐标的移动我们是可以分开考虑的，因此我们就分别考虑横坐标移动的 \(40\)次操作和纵坐标移动的 \(40\)次操作。

而操作，事实上就是决定移动距离的正负性。注意到 \(40\)其实是个很微妙的性质，它的一半 \(20\)是可以承受指数的复杂度的。即采用折半搜索的策略。

即对于这 \(40\)次操作，我们要对它们赋予正负号，看它们的和能否成为 目标移动距离\(x\)(或 \(y\))。

我们可以分别对前\(20\)个数和后\(20个数\)，花 \(O(2^{20})\)枚举它们的正负号，记录它们的和。

然后再把这两部份的结果合并：能否从左右两边的结果各挑一个数，它们的和\(=x\)。这是一个非常简单的子问题，对两边排序后一个双指针就可以解决了。这里的时间复杂度是 \(O(2^{20} \log)\)。

分别对\(x,y\)方向进行一次折半搜索，就可以搜到结果了。

由于要输出方案，因此我们得记录该结果的每一项的正负号，下面代码是通过二进制压缩的形式记录的，最后还要通过每一项的正负号，以及当前机器人的朝向决定向左向右转。

神奇的代码 
#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, x, y;
    cin >> n >> x >> y;
    array<vector<int>, 2> a;
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        a[i & 1].push_back(x);
    }
    auto dfs = [&](auto self, const vector<int>& a, int pos, int sum, int sol,
                   int l, int r, vector<array<int, 2>>& tmp) {
        if (pos + l == r) {
            tmp.push_back({sum, sol});
            return;
        }
        self(self, a, pos + 1, sum + a[pos + l], sol, l, r, tmp);
        self(self, a, pos + 1, sum - a[pos + l], (sol | (1 << pos)), l, r, tmp);
    };
    auto solve = [&](const vector<int>& a, int val) {
        int mid = a.size() / 2;
        vector<array<int, 2>> l, r;
        dfs(dfs, a, 0, 0, 0, 0, mid, l);
        dfs(dfs, a, 0, 0, 0, mid, a.size(), r);
        vector<int> lid(l.size()), rid(r.size());
        iota(lid.begin(), lid.end(), 0);
        iota(rid.begin(), rid.end(), 0);
        ranges::sort(lid, [&](int x, int y) { return l[x][0] < l[y][0]; });
        ranges::sort(rid, [&](int x, int y) { return r[x][0] > r[y][0]; });
        auto lp = lid.begin(), rp = rid.begin();
        while (lp != lid.end() && rp != rid.end()) {
            if (l[*lp][0] + r[*rp][0] == val) {
                return l[*lp][1] + ((1ll * r[*rp][1]) << mid);
            } else if (l[*lp][0] + r[*rp][0] < val) {
                lp = next(lp);
            } else if (l[*lp][0] + r[*rp][0] > val) {
                rp = next(rp);
            }
        }
        return -1ll;
    };
    auto dy = solve(a[0], y); // 0 => +, 1 => -
    auto dx = solve(a[1], x);
    if (dy == -1 || dx == -1)
        cout << "No" << '\n';
    else {
        cout << "Yes" << '\n';
        vector<int> ans;
        for (int i = 0; i <= n / 2; ++i) {
            ans.push_back((dy >> i) & 1);
            if (i < n / 2)
                ans.push_back((dx >> i) & 1);
        }
        int dir = 0;
        for (int i = 0; i < n; ++i) {
            cout << "LR"[ans[i] ^ dir ^ (i & 1)];
            dir = ans[i];
        }
        cout << '\n';

    }

    return 0;
}

G - Unlock Achievement (abc326 G)

题目大意

给定\(n\)个技能和 \(m\)个成就。对于第 \(i\)个技能，升一级花费 \(c_i\)。

达成第 \(i\)个成就， 有\(a_i\)的奖励，达成条件为，对于每个技能要达到指定等级或以上。

问最大的收益，即奖励\(-\)花费的最大值。

解题思路

<++>

神奇的代码