警告

本 Blog 仅供蒟蒻 tiger0132 复习用。本蒟蒻

不对其内容正确性做任何保证。

若发现 Bug 请在评论区反馈。本蒟蒻欢迎一切形式的贡献。

点击屏幕以关闭。

「赛后总结」Codeforces Round #464 (Div. 2) (+1)

传送门:Codeforces Round #464 (Div. 2)

今天的状态差到一种境界>_<。然后估计这几次比赛会炼成 High Frequency Rating

本来可以做出 CD 的,顿时感觉被出题人坑了。

原来坑题不止中国出,俄罗斯也出。

A

比赛时竟然写了个 dfs……

然后获得了

# When Who Problem Lang Verdict Time Memory
2018-02-17 13:27:26 A - Love Triangle GNU C++ Time limit exceeded on pretest 4 1000 ms 2200 KB
2018-02-17 13:23:57 A - Love Triangle GNU C++ Wrong answer on pretest 7 15 ms 2200 KB
2018-02-17 13:22:58 A - Love Triangle GNU C++ Wrong answer on pretest 7 15 ms 2200 KB
2018-02-17 13:19:46 A - Love Triangle GNU C++ Wrong answer on pretest 7 15 ms 2000 KB
2018-02-17 13:15:25 A - Love Triangle GNU C++ Memory limit exceeded on pretest 6 140 ms 262100 KB

直到我发现只要判断 a[a[a[i]]] == i 是否成立就可以通过。

然后我终于……

# When Who Problem Lang Verdict Time Memory
2018-02-17 14:21:19 A - Love Triangle GNU C++ Pretests Passed 30 ms 2000 KB

然而那时我已经早就 AC 了 B 题……

最后 A 我只拿了 \(150\) 分。然并卵

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;

int a[5003];
int n;

int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", a+i);
}
for (int i = 1; i <= n; i++) {
if (a[a[a[i]]] == i) {
puts("YES");
return 0;
}
}
puts("NO");
}

教训

不要想多!不要想多!!不要想多!!!

这堆数据发现了你的想多。

我是这堆数据中的一个超级水数据,我先发现你的想多是你 Rating 的幸运。警告你:不要想多!不要想多!!不要想多!!!

你的的方向上有千万个参赛者,只要不想多,这堆数据就无法定位想多者。

如果想多,想多者将被定位,你的 Rank 将会遭到打击,你的 Rating 将会被降低!

不要想多!不要想多!!不要想多!!!

B

因为我没考虑到无解时全部输出 \(0\) 的情况,所以我又 WA 了一发。还有一发是我没判断仓鼠数量。

然后我一直没调到错误。

直到我发现我在 if 中的判断少写了个 =

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;

long long n, x, ax, bx, cx;
int k;

int main() {
scanf("%I64d%d", &n, &k);
for (int i = 1; i <= k; i++) {
scanf("%I64d", &x);
if (n - n % x >= cx) {
ax = i;
bx = n / x;
cx = n - n % x;
}
}
printf("%I64d %I64d", ax, bx);
}

教训

小心无解情况。如果允许输出多组解中的任意一个,请不要使用 < 或者 >,用 <=>= 替代它们。如果不允许,则将当前答案设置成无解。

C

\(f-s=k\)

最开始我写了个前缀和,然后在最后追加 \(k\) 个数,把每个长度为 \(k\) 的子段算出来然后取个 max

无数次 Wrong answer on test 20 之后还是没有发现错在哪里。

然后我比赛时就没过这题……

比赛结束后,我改成了另外一种写法,又无数次 Wrong answer on test 9 后也没有发现问题。

最后我写了个 尺取法two-pointer,然后还是 Wrong answer on test 9

在我砸键盘前的那一刻,我提交了一份骗数据的代码。于是……

Output

1
2
3
20280: 500722912
99717
99717: 500722912

Answer

1
20280

卧槽(上这么难你是人吗)答案一样为什么是 \(20280\) ?百思不得姐。

直到我看见了这句话:

If there are many answers, output the smallest among them.

mmp。

更错

上面这 \(3\) 个算法,虽然是正着枚举,但是时间是反的。

于是就 Wrong answer on test 9了。

估计是 LJ 出题人不想写太长的 SPJ,然后就在 Output 最后写了这句话。

前缀和算法的最后

我的前缀和还是莫名其妙的 Wrong answer on test 20 了,估计算法还是有问题。

代码(双指针)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
#ifdef LOCAL
#define lld "%lld"
#else
#define lld "%I64d"
#endif
using namespace std;

long long arr[200005];
long long ax, ai, cur;
int n, s, f, t;

int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%lld", arr+i);
}
scanf("%d%d", &s, &f);
s--; f -= 2;
for (int i = s; i <= f; i++) {
cur += arr[i];
}
for (int i = 1; i <= n; i++) {
if (cur >= ax) {
ai = t + 1;
ax = cur;
}
f = (f + 1) % n;
cur += arr[f] - arr[s];
s = (s + 1) % n;
t = (t + n - 1) % n;
}
printf(lld, ai);
}

教训

防被坑最好的方法是多读题。

D

第一感图论,然后写了个枚举。如果 a[i] == b[i] 那么 gph[ax][bx] = 1,然后把所有连边输出。

然后挂在了这个数据上:

1
2
3
3
abc
bca

接下来我写了个初始化为 \(0\) 的并查集,然后因为有 \(0\) 点,与初始值矛盾,于是第二个样例挂了。

最后我写了个把所有字母替换成一个字符串中存在的字符的代码,于是 Wrong answer on pretest 4。类似这样:

1
2
3
2
ab
cd

比赛完我才发现,(卧槽上这么难你是人吗)我把并查集的初始值设矛盾了,于是我把初始值设为\(-1\),然后就 Accepted 了!

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
using namespace std;

char a[100005], b[100005];
int par[31];
int n, ans;

int find(int x) {
return ~par[x] ? par[x] = find(par[x]) : x;
}
void merge(int x, int y) {
if ((x = find(x)) != (y = find(y))) par[x] = y, ans++;
}

int main() {
memset(par, -1, sizeof par);
scanf("%d\n", &n);
gets(a + 1);
gets(b + 1);
for (int i = 1; i <= n; i++) {
if (a[i] != b[i]) {
int ax = a[i] - 'a';
int bx = b[i] - 'a';
merge(ax, bx);
}
}
printf("%d\n", ans);
for (int i = 0; i < 26; i++) {
find(i);
if (par[i] != -1) printf("%c %c\n", i + 'a', par[i] + 'a');
}
}

教训

乱初始化的后果是很严重的。写并查集前先想想有没有0号点。

E

二分三分不会写不好写,于是来优化暴力。

\(f(x,i)\)代表选择最大的数\(x\)和前\(i\)个数时的\(max-mean\)

显然添加数字之后并不会影响以前的答案。

于是可以\(O(n)\) Accepted 这道题。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// mmp为什么只有C++14及以上可以通过编译?详见下一篇底层博客————坑爹的编译器。

#include <bits/stdc++.h>
#ifdef LOCAL
#define lld "%lld"
#else
#define lld "%I64d"
#endif
using namespace std;

typedef long long ll;
typedef long double ld;

int q, l, n, op, ptr;
ll arr[500005];
ld ans;

ld f(ll x, int i) {
return (x * i - arr[i]) / ld(i + 1);
}

int main() {
scanf("%d", &q);
ll x;
while (q--) {
scanf("%d", &op);
if (op & 1) {
scanf(lld, &x);
while (ptr < n && f(x, ptr) <= f(x, ptr + 1)) ptr++;
ans = max(ans, f(x, ptr));
arr[n+1] = arr[n] + x; n++;
} else {
printf("%.10Lf\n", ans);
}
}
}