AtCoder Beginner Contest 321

题目

Tasks - SuntoryProgrammingContest2023（AtCoder Beginner Contest 321）

A - 321-like Checker

方法一：模拟

思路

枚举 $N$ 的每一位，按照题意模拟。

代码

#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]$ 之间的整数，所以直接从小到大枚举最后一回合分数：

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

此时如果最终分数 $\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 并不多，最大也就是 $9876543210$ ，所以直接 DFS 把所有数搜索出来排个序找出第 $k$ 大的输出即可。

代码

#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

方法一：二分查找 前缀和

思路

把数组 $B$ 排序，枚举数组 $A$ ：

• 二分查找，找到最后一个使得 $A_i + B_j < P$ 成立的数 $B_r$，以其为分割线，其中：
  • 前半部分 $B_{1\dots r}$ 对答案的贡献是 $\sum_{j = 1}^{r}(A_i + B_j) = r \cdot A_i \cdot \sum_{j = 1}^{r}{B_j}$，这部分可以提前维护数组 $B$ 的前缀和，直接 $O(1)$ 算出来；
  • 后半部分 $B_{r+1 \dots m}$ 对答案的贡献是 $(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

方法一：枚举

思路

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

离节点 $X$ 距离为 $K$ 的节点可以分为两部分：

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

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

第二部分的节点：迭代枚举 $X$ 的父节点，设枚举到的节点 $P$ 距离 $X$ 为 $D$，则按照第一种方法查找以 $P$ 为根节点的子树中离 $P$ 的距离为 $K - D$ 的那层节点的数量（计算这一部分时，由于 $P$ 是 $X$ 的祖宗节点，所以很有可能枚举到 $X$ 那一部分，导致这一部分被重复计算，所以要减去离 $X$ 的 $P-1$ 个祖先距离为 $K - 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

暂无