侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 674 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

AtCoder Beginner Contest 321

GabrielxD
2023-10-10 / 0 评论 / 0 点赞 / 173 阅读 / 1,508 字
温馨提示:
本文最后更新于 2023-10-15,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

Tasks - SuntoryProgrammingContest2023(AtCoder Beginner Contest 321)

A - 321-like Checker

方法一:模拟

思路

枚举 NN 的每一位,按照题意模拟。

代码

#include <cstdio>

using namespace std;

int n;

int main() {
    scanf("%d", &n);
    int prev = -1;
    while (n) {
        if (n % 10 <= prev) {
            puts("No");
            return 0;
        }
        prev = n % 10;
        n /= 10;
    }
    puts("Yes");

    return 0;
}

B - Cutoff

方法一:枚举

思路

在已知的回合分数中,除了最高分和最低分,其他分数无论什么情况下都会被算在总分中。

由于最后一回合的分数只会是 [0,100][0, 100] 之间的整数,所以直接从小到大枚举最后一回合分数:

  • 如果最后一回合分数 <{}<{} 最低分,则最终分数要加上最低分;
  • 如果最后一回合分数 >{}>{} 最高分,则最终分数要加上最高分;
  • 都则最终分数要加上最后一回合分数。

此时如果最终分数 X\ge{X} 则满足要求,直接当前枚举到的最后一回合分数。

如果直到枚举完都没找到合法的答案,则输出 -1

代码

#include <cstdio>
#include <algorithm>

using namespace std;

int n, x;

int main() {
    scanf("%d%d", &n, &x);
    int mn = 101, mx = -1;
    int sum = 0;
    for (int i = 1; i < n; ++i) {
        int a; scanf("%d", &a);
        mn = min(mn, a);
        mx = max(mx, a);
        sum += a;
    }
    sum = sum - mn - mx;
    int tot;
    for (int i = 0; i <= 100; ++i) {
        if (i < mn) tot = sum + mn;
        else if (i > mx) tot = sum + mx;
        else tot = sum + i;
        if (tot >= x) {
            printf("%d\n", i);
            return 0;
        }
    }
    puts("-1");

    return 0;
}

C - 321-like Searcher

方法一:DFS

思路

所有的 321-like Number 并不多,最大也就是 98765432109876543210 ,所以直接 DFS 把所有数搜索出来排个序找出第 kk 大的输出即可。

代码

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long LL;

int k;
vector<LL> vec;

void dfs(LL x, int d) {
    if (d < 0) return;
    if (x) vec.push_back(x);
    for (int i = d - 1; i >= 0; --i) dfs(x * 10 + i, i);
}

int main() {
    scanf("%d", &k);
    dfs(0LL, 10);
    sort(vec.begin(), vec.end());
    printf("%lld\n", vec[k - 1]);

    return 0;
}

D - Set Menu

方法一:二分查找 前缀和

思路

把数组 BB 排序,枚举数组 AA

  • 二分查找,找到最后一个使得 Ai+Bj<PA_i + B_j < P 成立的数 BrB_r,以其为分割线,其中:
    • 前半部分 B1rB_{1\dots r} 对答案的贡献是 j=1r(Ai+Bj)=rAij=1rBj\sum_{j = 1}^{r}(A_i + B_j) = r \cdot A_i \cdot \sum_{j = 1}^{r}{B_j},这部分可以提前维护数组 BB 的前缀和,直接 O(1)O(1) 算出来;
    • 后半部分 Br+1mB_{r+1 \dots m} 对答案的贡献是 (mr)×P(m - r) \times P

注意:计算过程中及答案都可能爆 int

代码

#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 2e5 + 10;
int n, m, p;
int a[N], b[N];
LL s[N];

int main() {
    scanf("%d%d%d", &n, &m, &p);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    for (int i = 1; i <= m; ++i) scanf("%d", &b[i]);
    sort(b + 1, b + m + 1);
    for (int i = 1; i <= m; ++i) s[i] = s[i - 1] + b[i];
    puts("");
    LL ans = 0LL;
    for (int i = 1; i <= n; ++i) {
        int l = 1, r = m;
        while (l < r) {
            int m = l + r + 1 >> 1;
            if (a[i] + b[m] < p) l = m;
            else r = m - 1;
        }
        if (a[i] + b[r] >= p) --r;
        ans += s[r] + 1LL * r * a[i] + 1LL * (m - r) * p;
    }
    printf("%lld\n", ans);

    return 0;
}

E - Complete Binary Tree

方法一:枚举

思路

由题可得这棵树是一棵完全二叉树,节点 uu 的左子节点为 u×2u \times 2 ,右子节点为 u×2+1u \times 2 + 1。最大有 101810^{18} 个节点,也就是说该树最高也就约 64 层,所以若输入的 K>64K > 64 可以直接输出 00

离节点 XX 距离为 KK 的节点可以分为两部分:

  1. 以节点 XX 为根节点的子树中符合该条件的节点;
  2. 其它节点。

第一部分的节点:可以向下找到离 XX 距离为 KK 的那一层节点的左右边界,那么这部分节点的数量即为 min(r,n)l+1\min(r, n) - l + 1(注意:在迭代查找的过程中如果 l>nl > n 则说明不存在这一部分节点)。

第二部分的节点:迭代枚举 XX 的父节点,设枚举到的节点 PP 距离 XXDD,则按照第一种方法查找以 PP 为根节点的子树中离 PP 的距离为 KDK - D 的那层节点的数量(计算这一部分时,由于 PPXX 的祖宗节点,所以很有可能枚举到 XX 那一部分,导致这一部分被重复计算,所以要减去离 XXP1P-1 个祖先距离为 KP1K - P - 1 的节点的数量)。

代码

#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long LL;

int t;

LL count(LL n, LL u, LL k) {
    if (k < 0 || k >= 64) return 0LL;
    LL l = u, r = u;
    while (k-- > 0) {
        l = l << 1;
        r = r << 1 | 1;
        if (l > n) return 0LL;
    }
    return min(r, n) - l + 1;
}

int main() {
    scanf("%d", &t);
    LL n, x, k;
    while (t--) {
        scanf("%lld%lld%lld", &n, &x, &k);
        LL ans = count(n, x, k);
        while (x >> 1 && k--) {
            ans += count(n, x >> 1, k) - count(n, x, k - 1);
            x >>= 1;
        }
        printf("%lld\n", ans);
    }

    return 0;
}

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

暂无

G - Electric Circuit

暂无

0

评论区