\(\mathtt{rank:1119th}\)
| \(\mathtt{problem}\) | \(\mathtt{A}\) | \(\mathtt{B}\) | \(\mathtt{C}\) | \(\mathtt{D}\) | \(\mathtt{E}\) | \(\mathtt{F}\) | \(\mathtt{G}\) | \(\mathtt{Ex}\) | \(\mathtt{All}\) |
|---|---|---|---|---|---|---|---|---|---|
| \(\mathtt{score}\) | \(\mathtt{\color{green}{100}}\) | \(\mathtt{\color{green}{200}\color{red}{(1)}}\) | \(\mathtt{\color{green}{300}}\) | \(\mathtt{\color{green}{400}\color{red}{(3)}}\) | \(\mathtt{\color{green}{500}}\) | \(\mathtt{\color{gray}-}\) | \(\mathtt{\color{gray}-}\) | \(\mathtt{\color{gray}-}\) | \(\mathtt{\color{blue}{1500}\color{red}{(4)}}\) |
| \(\mathtt{time}\) | \(\mathtt{\color{gray}{1:02}}\) | \(\mathtt{\color{gray}{11:30}}\) | \(\mathtt{\color{gray}{18:29}}\) | \(\mathtt{\color{gray}{47:50}}\) | \(\mathtt{\color{gray}{84:04}}\) | \(\mathtt{\color{gray}-}\) | \(\mathtt{\color{gray}-}\) | \(\mathtt{\color{gray}-}\) | \(\mathtt{\color{gray}{104:04}}\) |
A - Count Down
输入一个数 \(n\)，从大到小输出 \(n\sim 0\)。
它对标 CSP-J A 一直可以的喔这次还更简单。
模拟即可。
// Problem: A - Count Down
// Contest: AtCoder - AtCoder Beginner Contest 281
// URL: https://atcoder.jp/contests/abc281/tasks/abc281_a
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
int main () {
int n;
scanf ("%d", &n);
while (~ n) {
printf ("%d\n", n --);
}
return 0;
}
B - Sandwich Number
一个字符串如果是以 [A~Z][100000~999999][A-Z] 的格式且长度为 \(8\) 是合法的。给出一个字符串，问是否合法。
不读题的后果：罚时 \(\times1\)。丢大脸。
按格式判断即可。
// Problem: B - Sandwich Number
// Contest: AtCoder - AtCoder Beginner Contest 281
// URL: https://atcoder.jp/contests/abc281/tasks/abc281_b
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
const int N = 15;
char s [N];
int main () {
scanf ("%s", s + 1);
int n = strlen (s + 1);
if (isupper (s [1]) && isupper (s [n]) && n == 8) {
for (int i = 2; i < n; i ++) {
if (! isdigit (s [i])) {
printf ("No\n");
return 0;
}
}
int x = 0;
for (int i = 2; i < n; i ++) {
x = x * 10 + s [i] - '0';
if (x > 999999) {
printf ("No\n");
return 0;
}
}
if (x < 100000) {
printf ("No\n");
}
else {
printf ("Yes\n");
}
}
else {
printf ("No\n");
}
return 0;
}
C - Circular Playlist
有 \(n\) 首歌，长度为 \(a_i\ \mathtt{s}\)，一共放 \(t\ \mathtt{s}\)，问此时应该在放哪首歌，这首歌放了多少了。
这 C 怎么比 B 简单啊（bushi。
很容易发现 \(n\) 首歌是个周期，于是可以提前把前面去用的循环去掉 \(t\to t\bmod\sum_{i=1}^na_i\)。
然后就可以快乐的枚举啦，时间复杂度 \(O(n)\)。
// Problem: C - Circular Playlist
// Contest: AtCoder - AtCoder Beginner Contest 281
// URL: https://atcoder.jp/contests/abc281/tasks/abc281_c
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
const int N = 100100;
long long a [N];
int main () {
int n;
long long t;
scanf ("%d%lld", &n, &t);
for (int i = 1; i <= n; i ++) {
scanf ("%lld", &a [i]);
a [i] += a [i - 1];
}
t %= a [n];
for (int i = 1; i <= n; i ++) {
if (t < a [i]) {
printf ("%d %lld\n", i, t - a [i - 1]);
return 0;
}
}
return 0;
}
D - Max Multiple
\(n\) 个数 \(a_i\)，你要选 \(k\) 个数使得和为 \(s\)，且需 \(s\bmod d = 0\)，输出最大的 \(s\)。
首先看到选数这种就不难想到背包，先考虑按照背包的方式求，设 \(dp_{i,j}\) 为选 \(i\) 个数和为 \(j\) 可行性。
但是容易发现 \(a_i\) 过大，时间，空间都不够，又发现 \(d\) 很小，且需满足的条件是 \(\bmod d\)，便考虑转化 \(dp_{i,j}\) 为选 \(i\) 个数 \(s \bmod d=j\) 的最大的 \(s\)。
转移方程：\(dp_{i,j}=\max\{ dp_{i-1,(j-a_h+d)\bmod d}+a_h\}(1\le i\le k,0\le j<d,1\le h\le n)\)。
// Problem: D - Max Multiple
// Contest: AtCoder - AtCoder Beginner Contest 281
// URL: https://atcoder.jp/contests/abc281/tasks/abc281_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int K = 110, D = 110;
long long dp [K] [D];
signed main () {
int n, k, d;
scanf ("%lld%lld%lld", &n, &k, &d);
memset (dp, -1, sizeof (dp));
dp [0] [0] = 0; // 初始化，其他不能设为 0
for (int i = 1, a; i <= n; i ++) {
scanf ("%lld", &a);
int c = a % d;
for (int j = k; j; j --){
for (int h = 0; h < d; h ++) {
if (~ dp [j - 1] [(h - c + d) % d]) {
dp [j] [h] = max (dp [j] [h], dp [j - 1] [(h - c + d) % d] + a);
}// 转移
}
}
}
// for (int i = 0; i <= k; i ++) {
// for (int j = 0; j < d; j ++) {
// printf ("%lld ", dp [i] [j]);
// }
// printf ("\n");
// }
printf ("%lld", dp [k] [0]);
return 0;
}
E - Least Elements
\(n\) 个数 \(a_i\)，你需要按序输出 \(m\le i\le n\) 中 \(a_{i - m + 1}\sim a_i\) 中 较小的 \(k\) 个数的和。
这 E 比平常的水些啊。
不难想到可以先处理前 \(m\) 个 \(a_i\) 的答案 \(ans\)，后面就可以每次删除 \(a_{i-m}\) 加入 \(a_i\) 动态维护 \(ans\)。
令 \(t\) 是此时的 \(m\) 个数的序列，且已排好序。
删除 \(a_{i-m}\)（以下操作是在删除后操作）：
- 若 \(a_{i-m}\) 是前 \(k\) 小的，则去掉此点贡献，加入递补进来的贡献，\(ans\to ans - a_{i-m}+t_k\)。
- 不是则无影响。
同理，加入 \(a_i\)（加入后操作）：
- \(a_i\) 是前 \(k\) 个小的，加入该点贡献，去掉被挤出的点的贡献，\(ans\to ans+a_i-t_{k+1}\)。
- 不是则无影响。
维护即可，因为 set 不能快速找到排名，用扩展库 pb_ds 的 tree 维护（注意编译器要有扩展库才能过编译）。因为 tree 和 set 一样不支持重复，再加一个序号使其不重复。
当 \(m=k\) 时查询 \(t_{k+1}\) 会寄，需特判。
#include <bits/extc++.h>
using namespace __gnu_cxx;
using namespace __gnu_pbds;
using namespace std;
const int N = 200100;
long long a [N];
tree <pair <long long, int>, null_type, less <pair <long long, int> >, rb_tree_tag, tree_order_statistics_node_update> st;
int main () {
int n, m, k;
scanf ("%d%d%d", &n, &m, &k);
if (m == k) {
long long ans = 0;
for (int i = 1; i <= m; i ++) {
scanf ("%lld", &a [i]);
ans += a [i];
}
printf ("%lld ", ans);
for (int i = m + 1; i <= n; i ++) {
ans -= a [i - m];
scanf ("%lld", &a [i]);
ans += a [i];
printf ("%lld ", ans);
}
return 0;
}// 特判
for (int i = 1; i <= m; i ++) {
scanf ("%lld", &a [i]);
st .insert ({a [i], i});
}
long long ans = 0;
for (int i = 1; i <= k; i ++) {
ans += (* st .find_by_order (i - 1)) .first;
}// 先处理前 m 个
printf ("%lld ", ans);
for (int i = m + 1; i <= n; i ++) {
scanf ("%lld", &a [i]);
int w = st .order_of_key({a [i - m], i - m}) + 1;
st .erase ({a [i - m], i - m});
if (w <= k) {
ans -= a [i - m];
ans += (* st .find_by_order (k - 1)) .first;
}// 删除
st .insert ({a [i], i});
w = st .order_of_key({a [i], i}) + 1;
if (w <= k) {
ans += a [i];
ans -= (* st .find_by_order (k)) .first;
}// 加入
printf ("%lld ", ans);
}
return 0;
}