ToB企服应用市场:ToB评测及商务社交产业平台

标题: AtCoder Beginner Contest 321(ABC321) [打印本页]

作者: 熊熊出没 时间: 2023-11-25 23:28
标题: AtCoder Beginner Contest 321(ABC321)
A. 321-like Checker

直接模拟。
Code

B. Cutoff

直接暴力枚举 \([0\sim100]\)，每次把第 \(n\) 个数当作当前枚举的 \(i\)，然后看看条件是否满足。
Code

C. 321-like Searcher

Description

给你一个 \(K\)，求出 \([1 \sim K]\) 区间内有多少个 321-like Number。
321-like Number 的定义：

每一位上的数字从左到右严格单调递减。
或者说，若它有 \(d\) 位，对于 \(\forall i\in[1,d-1]\)，从左到右第 \(i\) 位上的数大于从左到右第 \(i+1\) 位上的数。

Solution

预处理出所有的 321-like Number，枚举的时候类似枚举集合的做法。
存到 vector 数组里，排序后输出第 \(K\) 大的。
本题需要开 \(\text{long long}\)。
Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; // 开long long
ll k;
int main() {
scanf("%lld", &k);
k--;
vector<ll> v; // vector 存放枚举的结果
for (int i = 2; i < (1 << 10); i++) {
ll t = 0;
for (int j = 9; j >= 0; j--) {
if ((i >> j) & 1) { // 这一位为不为0
t *= 10, t += j; // 加到结果里
}
}
v.push_back(t);
}
sort(v.begin(), v.end()); // 排序
printf("%lld", v[k]); // 输出结果
return 0;
}

复制代码

D. Set Menu

Description

有两个数列 \(A, B\)，并给定一个常数 \(P\)，现在 \(A_i\) 和 \(B_j\) 的配对总花费为：\(\min(A_i + B_j, P)\)。
现在求：所有可能的配对方式的总和。
\(N, M \le 2 \times 10 ^ 5\)。
Solution

这道题显然不能用暴力，\(O(4 \times 10 ^ {10})\)，严重超时。
考虑如何优化。
可以将 \(B\) 从小到大排序，则对于每一个 \(A_i\)，满足 \(A_i + B_j \le P\) 的 \(j\) 是一段前缀。
设 \(B_t\) 为最后一个满足 \(A_i + B_j \le P\) 的 \(B_j\)，则对应的贡献为 \(tA_i + S_t + (n - t)P\)。其中 \(S_i\) 代表 \(B\) 数组前 \(i\) 个数的前缀和。
对于每一个 \(A_i\)，双指针/二分都可求解。
注：在双指针情况下必须先将 \(A\) 数列降序排序。
Code

[code]// LUOGU_RID: 128285445#include using namespace std;const int N = 200005;int a[N], b[N], m, n, p;long long s[N];int main() { cin >> n >> m >> p; for (int i = 1; i

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)