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

AtCoder Beginner Contest 321

时间:2023-09-23 23:11:42浏览次数:46  
标签:AtCoder Beginner int LL cin long 321 using dp

A - 321-like Checker (abc321 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);
    string s;
    cin >> s;
    auto ok = [&]() {
        for (int i = 0; i < s.size() - 1; ++i) {
            if (s[i + 1] >= s[i])
                return false;
        }
        return true;
    };
    if (ok())
        cout << "Yes" << '\n';
    else
        cout << "No" << '\n';

    return 0;
}



B - Cutoff (abc321 B)

题目大意

给定\(n-1\)个数字,问最后一个数字最少是多少,使得你的分数不小于 \(x\)。

数字在 \([0,100]\)之间。分数是去掉最低最高后的和。

解题思路

因为范围不大,直接枚举最后一个数,找最大最小,然后求分数判断即可。时间复杂度是\(O(100^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 n, x;
    cin >> n >> x;
    vector<int> a(n);
    for (int i = 0; i < n - 1; ++i)
        cin >> a[i];
    int ans = 0;
    auto ok = [&]() {
        auto tmp = a;
        sort(tmp.begin(), tmp.end());
        int sum =
            accumulate(tmp.begin(), tmp.end(), 0) - tmp.front() - tmp.back();
        return sum >= x;
    };
    for (; ans <= 100; ++ans) {
        a[n - 1] = ans;
        if (ok())
            break;
    }
    if (ans == 101)
        ans = -1;
    cout << ans << '\n';

    return 0;
}



C - 321-like Searcher (abc321 C)

题目大意

给定\(k\),问\(321-like\)的第 \(k\)小的数是多少。

\(321-like\)就是第一题的定义,从高位到低位逐数字递减。

解题思路

最大的是\(9876543210\),可以猜测数不多,直接搜索全部数出来,然后排序看第\(k\) 个是多少即可。

神奇的代码
#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 k;
    cin >> k;
    LL s = 0;
    vector<LL> ans;
    function<void(int)> dfs = [&](int x) {
        s = s * 10 + x;
        ans.push_back(s);
        for (int i = x - 1; i >= 0; --i)
            dfs(i);
        s /= 10;
    };
    for (int i = 9; i >= 0; --i) {
        dfs(i);
    }
    sort(ans.begin(), ans.end());
    cout << ans[k] << '\n';

    return 0;
}



D - Set Menu (abc321 D)

题目大意

给定两个数组\(a,b\)和一个数\(p\),各从中取一个数\(x,y\),得到贡献 \(\min(x+y, p)\) 。问所有取法的贡献和。

解题思路

对数组\(b\)排序,枚举数组 \(a\),那么小于 \(p-a\)的 \(b\)的贡献是 \(a+b\),其余的贡献是 \(p\),因此二分找到这个界限,分别计算这两类的贡献和即可,前者是个关于\(b\)的前缀和,后者就是一个数组\(b\)中 \(\geq p-a\)的数量的统计。时间复杂度是 \(O(n\log m)\)。

也可以对\(a,b\)都排序,此时\(a\)枚举从大到小, \(b\)枚举从小到大,双指针也行。

神奇的代码
#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;
    LL p;
    cin >> n >> m >> p;
    vector<LL> a(n), b(m);
    vector<LL> sumb(m);
    for (auto& i : a)
        cin >> i;
    for (auto& i : b)
        cin >> i;
    sort(b.begin(), b.end());
    partial_sum(b.begin(), b.end(), sumb.begin());
    LL ans = 0;
    for (auto& i : a) {
        LL r = p - i;
        auto cnt = lower_bound(b.begin(), b.end(), r) - b.begin();
        ans += 1ll * i * cnt + (cnt ? sumb[cnt - 1] : 0) + 1ll * p * (m - cnt);
    }
    cout << ans << '\n';

    return 0;
}



E - Complete Binary Tree (abc321 E)

题目大意

给定一棵完全二叉树,问与点\(x\)的距离为\(k\)的个数。

有 \(t\)组。

解题思路

示例图

考虑点\(5\)距离为 \(k\)的点都在哪。

首先在以该点的子树内,深度为 \(k\)的点有 \(2^k\)(起始为\(0\)), 对应的标号都可以求出来,这样可以判断在\(n\)内的标号有多少个。

然后考虑该点的父亲的另一个节点(点\(4\))的子树内,此时我们要求的深度是 \(2^{k-2}\)的点的个数。

然后考虑该点的父亲的父亲的另一个节点(点\(3\))的子树内,此时我们要求的深度是\(2^{k-3}\)的点的个数。

不断往父亲考虑,因为每次往父亲走,点标号都会除以 \(2\),最多 \(\log\)次就考虑完了。

总的复杂度是 \(O(t\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 t;
    cin >> t;

    auto solve = [&](LL x, LL k, LL n) {
        if (k < 0)
            return 0ll;
        if (k >= 64)
            return 0ll;
        __int128 num = (1ll << k), l = x;
        l = (l << k);
        __int128 r = l + num - 1;
        if (l > n)
            return 0ll;
        LL ret = min(r, (__int128)n) - l + 1;
        return ret;
    };
    while (t--) {
        LL n, x, k;
        cin >> n >> x >> k;
        LL ans = 0;
        if (k)
            ans += solve(x, k, n);
        while (x > 1 && k > 0) {
            --k;
            ans += solve((x ^ 1), k - 1, n);
            x /= 2;
        }
        if (x && k == 0)
            ans++;
        cout << ans << '\n';
    }

    return 0;
}



F - #(subset sum = K) with Add and Erase (abc321 F)

题目大意

箱子,放球,拿球,球上有数,各不相同。

每次操作后,问里面球数和为\(k\)的方案数。

解题思路

不考虑拿走球的操作,每次放球,求方案数,就是一个经典的\(0/1\)背包。

设 \(dp[i]\)表示和为 \(j\)的方案数,考虑选不选这个球(其数字为\(x\)),则有 \(dp[i] = dp[i] + dp[i - x]\)

现在拿走这个球,得从中剔除选了这个球的方案数。

设\(dp2[i]\)表示不选该球,和为 \(i\)的方案数。由于 \(dp[i]\)的方案包括两部分:选了该球和没选该球的。只要减去选了该球的方案数,那就是没选该球的方案数。而选了该球的方案数,其实就是 \(dp2[i-x]\),即选了这个球后,剩下的 \(i-x\)就是由不选该球的方案数组成,这恰好是我们定义的 \(dp2[i-x]\)的定义。

于是 \(dp2[i] = dp[i] - dp2[i - x]\)转移式即可。

时间复杂度是 \(O(qn)\)。

这其实是最经典的退背包问题。

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

const int mo = 998244353;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int q, k;
    cin >> q >> k;
    vector<int> dp(k + 1, 0);
    dp[0] = 1;
    while (q--) {
        string op;
        int x;
        cin >> op >> x;
        if (op[0] == '+') {
            for (int i = k; i >= x; --i) {
                dp[i] += dp[i - x];
                if (dp[i] >= mo)
                    dp[i] -= mo;
            }
        } else {
            vector<int> dp2(k + 1, 0);
            for (int i = 0; i <= k; ++i) {
                if (i < x) {
                    dp2[i] = dp[i];
                } else {
                    dp2[i] = dp[i] - dp2[i - x];
                    if (dp2[i] < 0)
                        dp2[i] += mo;
                }
            }
            dp.swap(dp2);
        }
        cout << dp[k] << '\n';
    }

    return 0;
}



G - Electric Circuit (abc321 G)

题目大意

给定\(n\)个部件和 \(m\)条线。部件有接口,有红蓝两色,数量都是\(m\)。一条线链接的两个接口必须不同颜色,但可以同个部件。

将部件视为点,线视为边,随机连线,问联通块的期望个数。

解题思路

<++>

神奇的代码



标签:AtCoder,Beginner,int,LL,cin,long,321,using,dp
From: https://www.cnblogs.com/Lanly/p/17725350.html

相关文章

  • 题解 AtCoder Beginner Contest 267 A~H
    ABC267solutionhttps://atcoder.jp/contests/abc267/ProblemA.Saturday题目描述输入一个表示星期的英文字符串,输出:还有多少天到星期六?solution依题意模拟。\(O(1)\)。ProblemB.Split?题目描述Robin有十个小球,如图排列成这样,然后Robin将一些球击飞了,他告诉你哪些......
  • AtCoder Beginner Contest 318 ABCDE
    AtCoderBeginnerContest318A-FullMoon思路:等差数列求项数//AConemoretimes//nndbk#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintmod=1e9+7;constintN=2e5+10;intmain(){ios::sync_with_stdio(false);......
  • AtCoder Beginner Contest 320 ABCDE
    AtCoderBeginnerContest320A-LeylandNumber思路:直接快速幂//AConemoretimes//nndbk#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintmod=1e9+7;constintN=2e5+10;llqmi(lla,llb){llans=1;whil......
  • AtCoder Beginner Contest 253 E
    AtCoderBeginnerContest253E-DistanceSequence思路:前缀和优化DP要求$|a[i]-a[i+1]|>=k\(定于\)dp[i][j]:\(前\)i\(个数以\)j\(结尾的合法序列数列\)dp[i][j]+=dp[i-1][1~(j-k)]+dp[i-1][(j+k)~m]$直接写的话复杂度是\(O(nm^2)\)的会TLE,我们发现可以做一个前缀和优化......
  • AtCoder Beginner Contest 313 Ex Group Photo
    洛谷传送门AtCoder传送门考虑若重排好了\(a\),如何判断可不可行。显然只用把\(b\)排序,把\(\min(a_{i-1},a_i)\)也排序(定义\(a_0=a_{n+1}=+\infty\)),按顺序逐个判断是否大于即可。这启示我们将\(\min(a_{i-1},a_i)\)排序考虑。考虑从大到小加入\(a_i\),那么......
  • AtCoder Grand Contest 017
    链接C.SnukeandSpells容易发现合法序列排序后一定是若干段值域连续的部分组成:可以发现最小次数就是重叠/空出的部分大小。每次修改只会对\(O(1)\)个点\(±1\),直接维护即可。#include<iostream>#include<cstdio>#include<cstring>#include<vector>#defineN200010......
  • AtCoder Grand Contest 023 E Inversions
    洛谷传送门AtCoder传送门首先将\(a\)从小到大排序,设\(p_i\)为排序后的\(a_i\)位于原序列第\(p_i\)个位置,\(x_i\)为要填的排列的第\(i\)个数。设\(A=\prod\limits_{i=1}^n(a_i-i+1)\),则\(A\)为排列的总方案数(考虑按\(a_i\)从小到大填即得)。套路地,统......
  • Java8(jdk1.8u321)下载、安装及配置
    jdk1.8的下载、jdk1.8的安装、配置环境变量。一、jdk1.8下载下载官网地址:https://www.oracle.com/java/technologies/downloads/#java8-windows下载版本:jdk-8u381-windows-x64.exe二、jdk1.8的安装双击jdk1.8安装包进行安装:按照安装步骤,直至完成安装。确认是否完成安装:打......
  • Atcoder Regular Contest 165(A~E)
    赛时45min切A~C,降智不会D,罚坐1h,喜提rk70+->rk170+。A-SumequalsLCM可证明结论:若\(N\)只含有一种质因子则无解,否则有解。B-SlidingWindowSort2这么多cornercase的题竟然10min一发入魂,类目了。由于操作是升序排序,且要求最终字典序最大,所以如果存在一个......
  • AtCoder Beginner Contest 320
    A-LeylandNumbera,b=map(int,input().split(''))print(a**b+b**a)B-LongestPalindromes=input()n=len(s)res=0forlinrange(1,n+1):foriinrange(0,n-l):t=q=s[i:i+l]t=t+t[::-1]......