首页 > 其他分享 >AtCoder Beginner Contest 326

AtCoder Beginner Contest 326

时间：2023-10-28 23:12:22浏览次数：32  
标签：AtCoder return Beginner int auto cin long vector 326

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\)的奖励，达成条件为，对于每个技能要达到指定等级或以上。

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

解题思路

<++>

神奇的代码

标签：AtCoder,return,Beginner,int,auto,cin,long,vector,326
From： https://www.cnblogs.com/Lanly/p/17794865.html

相关文章

  • ABC326
    上次说我的写法low的人的AT号在这里！！（我又来提供low算法了。从D开始。T4我们把\(\text{A}\)看成\(1\)，把\(\text{B}\)看成\(2\)，把\(\text{C}\)看成\(3\)。那么就可以想到状压，然后把每一行和每一列的情况状态即可。#include<bits/stdc++.h>usingnamespacestd;......
  • AtCoder Beginner Contest 326 题解
    首先，\(\text{HappyBirthdaytome!}\)A-2UP3DOWN常规ABCA...//If,oneday,Ifinallymanagetomakemydreamsareality...//Iwonder,willyoustillbetherebymyside?#include<bits/stdc++.h>#defineIOSios::sync_with_stdio(false)#defineTI......
  • 【杂题乱写】AtCoder-ARC114
    AtCoder-ARC114_ANotcoprime\(50\)内的质数只有\(15\)个，可能的答案也就只有\(2^{15}\)个，直接枚举。提交记录：Submission-AtCoderAtCoder-ARC114_BSpecialSubsets就是\(i\)与\(f_i\)连边，每个连通块都是基环树，一定能剥叶子变成环，所以答案就是连通块非空子集个数。......
  • AtCoder Beginner Contest(abc) 310
    B-StrictlySuperior难度:⭐题目大意给定n个商品的价格,每个商品还有若干个属性,请问是否存在一个商品是另外一个商品的上位品;上位品的定义分两种,一是价格相同,但是商品A的属性不仅包括了商品B的属性,还比商品B多了至少一个属性;二是如果两商品的属性相同,但是......
  • AtCoder Beginner Contest 325
    感觉错失了上分机会A-Takahashisan(abc325A)题目大意给定姓和名，输出尊称，即姓+san。解题思路按照题意模拟即可。神奇的代码#include<bits/stdc++.h>usingnamespacestd;usingLL=longlong;intmain(void){ios::sync_with_stdio(false);cin.tie(......
  • AtCoder Beginner Contest 216 H Random Robots
    洛谷传送门AtCoder传送门下文令\(n\)为原题中的\(K\)，\(m\)为原题中的\(N\)。首先概率转方案数，最后除\(2^{nm}\)即可。考虑一个指数级暴力：枚举每个bot的终点\(y_i\)（因为存在不能相交的限制，需要满足\(y_1<y_2<\cdots<y_n\)），相当于为每个bot选一个\((0,x_i)......
  • AtCoder Regular Contest 164 F Subtree Reversi
    洛谷传送门AtCoder传送门非常好题目。发现每个点颜色被反转的次数是固定的，为其深度（根结点深度为\(0\)）。于是可以看作是，一放棋子就得到分数。那么先手取偶数层和后手取奇数层都会使先手得分，所以双方的目标都是尽可能多取偶数层的结点。考虑若一开始有偶数层的叶子，那么当前的......
  • AtCoder Beginner Contest(abc) 309
    B-Rotate题目大意给定一个n*n的矩阵,要求把矩阵的最外围按照顺时针转动一个数据,输出转动后的矩阵;解题思路数据不大,暴力即可;神秘代码#include<bits/stdc++.h>#defineintlonglong#defineIOSios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#def......
  • 76th 2023/10/10 Atcoder 10/8-ARC-T3
    这道题题目很有意思，看上去是很简单明显的计数，但一思考会发现要死很多重复状态因为标记的线很容易让人从一个方框开始思考起，所以很容易带入关于重复考虑的误区观察到线是斜着的，思考影响到的范围若涂上一个格子或左一个格子的右下，则该格子不能填涂左上观察到影响范围是一个个斜......
  • 华为S2326TP-EI交换机端口汇聚（划分vlan做汇聚）
    批量创建Vlan11-20,并将交换机端口1-10分别加入到Vlan中，设置为ass口，[Quidway]system-view     //进入配置视图[Quidway]sysnameSwitchA //给交换机命名[SwitchA]vlanbatch11to20     //同时创建vlan11到vlan20[SwitchA]interfaceethernet0/0/1......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99