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;
}
#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;
}
#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;
}
// 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;
}
// 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; }

其他的题都没做出来,菜鸡一个。

原文链接:AtCoder Beginner Contest 321(ABC321)

© 版权声明
THE END
喜欢就支持一下吧
点赞11 分享
Nothing is more terrible than ignorance in action.
最可怕的事莫过于无知而行动
评论 抢沙发

请登录后发表评论

    暂无评论内容