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
// LUOGU_RID: 128285445
#include <bits/stdc++.h>
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 <= n; i++) scanf("%d", &a[i]);
for (int i = 1; i <= m; i++) scanf("%d", &b[i]);
sort(a + 1, a + n + 1, greater<int>());
sort(b + 1, b + m + 1);
for (int i = 1; i <= m; i++) s[i] = s[i - 1] + b[i];
int now = 0;
long long ans = 0;
for (int i = 1; i <= n; i++) {
while (now + 1 <= m && a[i] + b[now + 1] <= p) now++;
ans += s[now] + 1LL * now * a[i] + 1LL * (m - now) * p;
}
printf("%lld", ans);
return 0;
}
其他的题都没做出来,菜鸡一个。
- 321 Beginner AtCoder Contest ABCbeginner atcoder contest 321 321 beginner atcoder contest beginner atcoder contest abc 321 beginner searcher atcoder atcoder笔记abc 321 contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335