AtCoder Beginner Contest 326

Posted on 2023年10月29日

A – 2UP3DOWN (abc326 A)

题目大意

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

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

解题思路

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

神奇的代码 
#include 
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

B – 326-like Numbers (abc326 B)

题目大意

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

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

解题思路

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

神奇的代码 
#include 
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

C – Peak (abc326 C)

题目大意

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

解题思路

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

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

当然也可以双指针。

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

神奇的代码 
#include 
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 a(n);
    for (auto& i : a)
        cin >> i;
    ranges::sort(a);
    int ans = 0;
    for (int i = 0; i

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 
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> ans(n, vector(n, -1));
    vector top(n, 1);
    vector left(n, 1);
    vector row(n);
    vector col(n);
    auto not_have = [&](int x, int y) { return ((~x >> y) & 1); };
    function 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

E – Revenge of “The Salary of AtCoder Inc.” (abc326 E)

题目大意

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

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

  • 如果(x ，则获得 (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 
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 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

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 
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, 2> a;
    for (int i = 0; i > x;
        a[i & 1].push_back(x);
    }
    auto dfs = [&](auto self, const vector& a, int pos, int sum, int sol,
                   int l, int r, vector>& 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 & a, int val) {
        int mid = a.size() / 2;
        vector> l, r;
        dfs(dfs, a, 0, 0, 0, 0, mid, l);
        dfs(dfs, a, 0, 0, 0, mid, a.size(), r);
        vector 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]  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])  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  ans;
        for (int i = 0; i > i) & 1);
            if (i > i) & 1);
        }
        int dir = 0;
        for (int i = 0; i

G – Unlock Achievement (abc326 G)

题目大意

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

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

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

解题思路

神奇的代码

机房租用，北京机房托管，大带宽租用，IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net

相关文章：

  1. 联通托管服务器：稳定高效的数据存储方案
  2. 甘肃地区专业Win10服务器托管服务
  3. 开年不利，谁能拯救半导体企业的2023？
  4. k8s ingress nginx 504 gateway timeout 问题
  5. 多场景 PAI-Diffusion 中文模型家族大升级，12个模型、2个工具全部开源

机房租用，北京机房托管，大带宽租用，IDC机房租用托管服务器

服务器托管

咨询：董先生

电话13051898268 QQ/微信93663045！

上一篇:
下一篇:

©2023 机房租用，北京机房托管，大带宽租用，IDC机房服务器主机租用托管-价格及服务咨询 京ICP备13047091号