Codeforces Round #715 (Div. 2) 题解

勉强四题,尴尬。。

A - Average Height

将长为 $n$ 的序列重新排列,使得有尽可能多的相邻两数,满足它们的奇偶性相同。

把所有奇数放在前面,所有偶数放在后面即可。。

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
/* Code Information
* Author: little_skqliao
* Time: 2021-05-18 14:10:12
* Source: CF 1509 A
* Problem: https://codeforces.com/contest/1509/problem/A
**/

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fir first
#define sec second
template<class T, class G> bool chkMax(T &x, G y) {return y > x ? x = y, 1 : 0;}
template<class T, class G> bool chkMin(T &x, G y) {return y < x ? x = y, 1 : 0;}

int T, N;
vector<int> v;

int main() {
cin >> T;
while (T--) {
cin >> N;
v.resize(N);
for (auto &x : v) cin >> x;
for (auto x : v) if (x & 1) cout << x << " ";
for (auto x : v) if (!(x & 1)) cout << x << " ";
cout << endl;
}
return 0;
}

B - TMT Document

给定一个长为 $3n$ 的字符串 $s$,$s$ 仅由 TM 构成。求 $s$ 能否分成 $n$ 个子序列,每个子序列都是 TMT

$n\leq 10^5$

从左往右遍历 $s$,做带撤销的匹配。

如果当前字符是 M,若前面有未配对的T,则配对成TM。否则,若前面已有匹配完成的TMT,则将它拆成 TMT,后者的T与当前的M又配对成TM,若没有匹配完成的TMT则无解。

如果当前字符是T,若前面有配对好的TM,则匹配成TMT,否则记为一个单独的T

因此一共记录三个量,依次是单独的T、配对好的TM和匹配完成的TMT 的个数。

复杂度 $O(n)$。

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
/* Code Information
* Author: little_skqliao
* Time: 2021-05-18 14:10:12
* Source: CF 1509 B
* Problem: https://codeforces.com/contest/1509/problem/B
**/

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fir first
#define sec second
template<class T, class G> bool chkMax(T &x, G y) {return y > x ? x = y, 1 : 0;}
template<class T, class G> bool chkMin(T &x, G y) {return y < x ? x = y, 1 : 0;}

int T, N;
string s;

int main() {
cin >> T;
while (T--) {
cin >> N >> s;
int a = 0, b = 0, c = 0;
for (auto ch : s) {
if (ch == 'T') {
if (b) --b, ++c;
else ++a;
} else {
++b;
if (!a) {
if (!c) break;
else --c, ++b;
} else --a;
}
}
if (!a && !b) puts("YES");
else puts("NO");
}
return 0;
}

C - The Sports Festival

将长为 $n$ 的序列 $v$ 重新排列,记 $d_i=\max\limits_{j=1}^{i}{v_j}-\min\limits_{j=1}^{i}{v_j}$,求 $\sum\limits_{i=1}^{n}{d_i}$ 的最小值。

$n\leq 2000$

将 $v$ 排序后记为 $t$。

想要 $\sum{d_i}$ 小,显然对于任意排列后的 $v$,其任意一个前缀,都是 $t$ 中的一段子区间。

记 $f_{i,j,k}$ 为 新 $v$ 的长为 $i$ 的前缀中,最大值为 $t_j$,最小值为 $t_k$,$\sum\limits_{p=1}^{i}{d_p}$ 的最小值。

由以上结论得 $j-k+1=i$。

转移方程为 $f_{i,j,k}=\min(f_{i-1,j-1,k},f_{i-1,j,k+1})+t_j-t_k$。

因为区间长度在递增,因此 $f_i$ 中的点对 $(j,k)$ 在 $f_1\sim f_{i-1}$ 中从未出现过,此后 $f_{i+1}\sim f_n$ 中也不会再出现。

因此可以省略这一维,只留下 $f_{j,k}$。

复杂度 $O(n^2)$。

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
/* Code Information
* Author: little_skqliao
* Time: 2021-05-18 14:10:12
* Source: CF 1509 C
* Problem: https://codeforces.com/contest/1509/problem/C
**/

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fir first
#define sec second
template<class T, class G> bool chkMax(T &x, G y) {return y > x ? x = y, 1 : 0;}
template<class T, class G> bool chkMin(T &x, G y) {return y < x ? x = y, 1 : 0;}

int N;
vector<int> v;
vector<vector<ll>> f;

int main() {
scanf("%d", &N);
v.resize(N);
for (auto &x : v) scanf("%d", &x);
sort(v.begin(), v.end());
f.resize(N);
for (int i = 0; i < N; ++i) {
f[i].resize(N, 1e18);
f[i][i] = 0;
}
for (int i = 2, t = 0; i <= N; ++i, t ^= 1) {
for (int j = i - 1; j < N; ++j) {
chkMin(f[j][j - i + 1], f[j][j - i + 2] + v[j] - v[j - i + 1]);
chkMin(f[j][j - i + 1], f[j - 1][j - i + 1] + v[j] - v[j - i + 1]);
}
}
printf("%lld\n", f[N - 1][0]);
return 0;
}

D - Binary Literature

给定三个长为 $2n$ 的 $01$ 串,构造出长为 $3n$ 的 $01$ 字符串,使得其中至少两个字符串是它的子序列。

可以证明答案一定存在。

$n\leq 10^5$

一个直观的思路是在某个 $01$ 串的基础上增加一些 $0$ 和 $1$,使它的子序列组成另一个 $01$ 串。

但是这样一来最多只能增加 $n$ 个字符了。

考虑为什么说答案一定存在。

对于每个 $01$ 串,$0$ 和 $1$ 的数量之和为 $2n$,这就以为着 $0$ 或 $1$ 至少有一个的出现次数在 $n$ 次以上。

而一共有三个 $01$ 串,则其中必然存在两个 $01$ 串,它们的 $0$ 或 $1$ 的出现次数都在 $n$ 次以上。

假设 $s_1$ 和 $s_2$ 分别有 $a$ 和 $b$ 个 $1$( $0$ 同理),其中 $a\geq b\geq n$。

则 $s_2$ 的所有 $1$ 在 $s_1$ 中已经存在,只需要补上缺失的 $0$ 即可。又因为 $b\geq n$,因此需要增加的 $0$ 的个数最大不超过 $n$。

于是在 $s_1$ 中补上 $s_2$ 的所有 $0$,就得到了包含 $s_1,s_2$ 作为子序列的 $01$ 串了。

它的长度可能还没有 $3n$,在末尾用 $0$ 补齐即可。

复杂度 $O(n)$。

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
/* Code Information
* Author: little_skqliao
* Time: 2021-05-18 14:10:12
* Source: CF 1509 D
* Problem: https://codeforces.com/contest/1509/problem/D
**/

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fir first
#define sec second
template<class T, class G> bool chkMax(T &x, G y) {
return y > x ? x = y, 1 : 0;
}
template<class T, class G> bool chkMin(T &x, G y) {
return y < x ? x = y, 1 : 0;
}

int T, N;
string s[3], ans;
vector<int> v;
int f[3][2];
bool flag;

void get(int x, int y, int t) {
if (flag) return ;
if (f[x][t] < f[y][t]) {
swap(s[x], s[y]);
}
v.clear();
ans.clear();
int num = 0, cur = 0;
for (int i = 0; i < 2 * N; ++i) {
if (s[y][i] == t + '0') ++num;
else v.push_back(num);
}
num = 0;
while (cur < v.size() && v[cur] == 0) {
ans += char('0' + (t ^ 1));
++cur;
}
for (auto c : s[x]) {
ans += c;
if (c == t + '0') {
++num;
while (cur < v.size() && v[cur] == num) {
ans += char('0' + (t ^ 1));
++cur;
}
}
}
while (ans.size() < N * 3) ans += '0';
cout << ans << endl;
flag = 1;
}

int main() {
cin >> T;
while (T--) {
cin >> N;
for (int i = 0; i < 3; ++i) {
cin >> s[i];
f[i][0] = f[i][1] = 0;
for (auto c : s[i]) f[i][c == '1']++;
}
flag = 0;
for (int i = 0; i < 3; ++i) {
for (int j = i + 1; j < 3; ++j) {
if (f[i][1] >= N && f[j][1] >= N) {
get(i, j, 1);
} else if (f[i][0] >= N && f[j][0] >= N) {
get(i, j, 0);
}
}
}
}
return 0;
}