0%

CF Round 619 (Div. 2)

并不顺心的一场 CF。。

开场又被 B 卡住了,死活 WA,耽误了有 20 分钟,最后下定决心弃掉 B 去看 C,看了会发现 C 是水题,很快写完了,然而这时已经过去 50 多分钟了。

敲完 C 去看了下 D,发现不怎么可做,就又回过头去调 B,结果一看,是数组没有清空。。。就只是因为一个下标会越界。。真实训练赛打多了,忘记多组数据该怎么写了。。以后多组数据一定要记得清空数组,也一定要避免下标越界访问,尤其是像 $a[n+1]$ 这样的位置。

过了 B,迷茫了一会,发现 E, F 没什么人做,就去搞 D 了。看了会,发现 D 就是个 SB 构造,随便构造下就行了。。结果最后时间太赶,想错了一些细节,而且代码实现的也极其混乱,最终还是没能过。。

还是太菜,写个几十行的垃圾代码能出一万个 bug。

这场比赛也暴露了些问题:

  1. 多组数据一定记得清空数组,尽量避免不必要的越界;
  2. 卡题了就赶紧换题,不要在上面耽误太多时间;
  3. 即使在比赛中,写代码前也一定要理清思路;比赛代码不要写的太混乱,时刻保持代码可读、易修改。

下面是题解

A

Code

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
#include <bits/stdc++.h>
using namespace std;

int main()
{
int T;
cin >> T;
while (T--)
{
string a, b, c;
cin >> a >> b >> c;
int n = a.size(), ok = 1;
for (int i = 0; i < n; i++)
{
if (c[i] != a[i] && c[i] != b[i])
{
ok = 0;
break;
}
}
if (ok) cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}

B

又被 B 卡了。。下次交题之前一定要好好检查下有没有很蠢的错误。

Code

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
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 100000 + 5;

int n;
LL a[N];

int main()
{
int T;
scanf("%d", &T);
while (T--)
{
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
LL ml = 1e18, mx = -1, k = 0, ans = 0;
for (int i = 1; i <= n; i++)
{
if (a[i] != -1)
{
if (i != n && a[i + 1] != -1)
{
ans = max(ans, abs(a[i + 1] - a[i]));
}
if (a[i + 1] == -1 || a[i - 1] == -1)
{
ml = min(ml, a[i]);
mx = max(mx, a[i]);
}
}
}
if (mx == -1)
{
printf("%d %d\n", 0, 0);
}
else
{
k = (ml + mx) / 2;
ans = max(ans, max(abs(mx - k), abs(ml - k)));
printf("%lld %lld\n", ans, k);
}
for (int i = 1; i <= n; i++) a[i] = 0;
}
return 0;
}

C

思维题,不难。

显然把 $m$ 个 $1$ 均匀放置时的答案最大。

$m$ 个 $1$ 会形成 $m + 1$ 个间隔,每个间隔大小为 $\lfloor\dfrac{n-m}{m+1}\rfloor$ 或 $\lfloor\dfrac{n-m}{m+1}\rfloor + 1$,答案为所有子串数量减去所有间隔形成的全 $0$ 子串数量。

Code

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
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

LL f(LL x)
{
return x * (x + 1) / 2;
}

int main()
{
int T;
scanf("%d", &T);
while (T--)
{
LL n, m;
scanf("%lld%lld", &n, &m);
if (!m)
{
printf("%d\n", 0);
continue;
}
LL p = (n - m) / (m + 1), q = (n - m) % (m + 1);
LL x = q, y = m + 1 - x;
LL ans = f(n) - y * f(p) - x * f(p + 1);
printf("%lld\n", ans);
}
return 0;
}

D

显然能构造出遍历完所有边的解。

从左上开始,奇数行输出 ($m - 1, \texttt{“DUR”}$),偶数行输出 ($m-1, \texttt{“DUL”}$),然后输出一个 ($1, \texttt{“D”}$),持续 $n-1$ 次。

然后直接原路返回就行了。

一共 $n\times 4-2$ 个操作,小于 $3000$。

比赛时候 WA 的原因是没有考虑 $n,m=1$ 的情况。。而且正解的构造好写也好想,我也不知道为什么我要这么构造。

Code

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
//这份代码又长又难看,可是它过了
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
using namespace std;

typedef long long LL;
typedef pair<int, string> pii;

int n, m, k;
vector<pii> v;

void print()
{
printf("%d\n", v.size());
for (int i = 0; i < v.size(); i++)
cout << v[i].first << " " << v[i].second << endl;
}

int main()
{
cin >> n >> m >> k;
int sum = 4 * n * m - 2 * n - 2 * m;
if (k > sum)
{
puts("NO");
return 0;
}
puts("YES");
if (n == 1)
{
cout << 2 << endl;
if (k <= m - 1)
{
cout << k << " " << "R" << endl;
return 0;
}
cout << m - 1 << " " << "R" << endl;
cout << k - (m - 1) << " " << "L" << endl;
return 0;
}
if (m == 1)
{
cout << 2 << endl;
if (k <= n - 1)
{
cout << k << " " << "D" << endl;
return 0;
}
cout << n - 1 << " " << "D" << endl;
cout << k - (n - 1) << " " << "U" << endl;
return 0;
}
int x = 0;
string s;
for (int i = 1; i <= n - 1; i++)
{
if (i % 2 == 1) s = "DUR";
else s = "DUL";
int now = 3 * (m - 1);
if (x + now >= k)
{
int p = (k - x) / 3, q = (k - x) % 3;
if (p > 0) v.pb(mp(p, s));
if (q > 0) v.pb(mp(1, s.substr(0, q)));
print();
return 0;
}
v.pb(mp(m - 1, s));
x += now;
s = "D";
v.pb(mp(1, s));
if (x + 1 == k)
{
print();
return 0;
}
x++;
}

int f = n % 2;
if (f == 1) s = "R";
else s = "L";
int now = m - 1;
if (x + now >= k)
{
v.pb(mp(k - x, s));
print();
return 0;
}
x += now;
v.pb(mp(m - 1, s));

for (int i = n; i >= 1; i--)
{
if (f == 0) s = "R";
else s = "L";
{
int now = m - 1;
if (x + now >= k)
{
v.pb(mp(k - x, s));
print();
return 0;
}
x += now;
v.pb(mp(m - 1, s));
}
s = "U";
if (i != 1)
{
v.pb(mp(1, s));
if (x + 1 == k)
{
print();
return 0;
}
x++;
}
f ^= 1;
}
return 0;
}

E & F

没看