# # Codeforces Round 661 (CF1399) 题解

## # Problem A - Remove Smallest

### # 题解

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}

class Solution {
public:
void solve() {
int n;
vector<int> a(n);
for (int i = 0; i < n; ++i)
sort(a.begin(), a.end());
for (int i = 0; i + 1 < n; ++i)
if (a[i + 1] - a[i] > 1) {
printf("NO\n");
return;
}
printf("YES\n");
}
};

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
while (t--) {
Solution solution = Solution();
solution.solve();
}
}

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

import Control.Monad
import Data.Bool
import Data.List

solve :: IO ()
solve = do
getLine
as <- map read . words <$> getLine putStrLn$ bool "NO" "YES" $all (<= 1)$ zipWith subtract <*> tail $sort as main :: IO () main = do getLine >>= flip replicateM_ solve . read  1 2 3 4 5 6 7 8 9 10 11 12 13 ## # Problem B - Gifts Fixing ### # 题目描述 $n$个盒子，每个盒子里有$a_i$个A，$b_i$个B，每次操作可以从任意盒子里去除一个A或一个B或一对A+B，问至少多少次操作，可以让所有盒子中的A和B数量都相等？ ### # 题解 所有盒子的A都要以最少的A为准，所有盒子的B都要以最少的B为准。对于某一个盒子，需要的总操作次数等于A的差量和B的差量中较大的那一个。 参考代码（C++） #include <cstdio> #include <iostream> #include <vector> #define INF 0x3f3f3f3f using namespace std; typedef long long ll; template <typename T> void read(T &x) { x = 0; char c = getchar(); T sig = 1; for (; !isdigit(c); c = getchar()) if (c == '-') sig = -1; for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - '0'; x *= sig; } class Solution { public: void solve() { int n; read(n); vector<int> a(n); vector<int> b(n); int la = INF, lb = INF; for (int i = 0; i < n; ++i) read(a[i]), la = min(la, a[i]); for (int i = 0; i < n; ++i) read(b[i]), lb = min(lb, b[i]); ll ans = 0; for (int i = 0; i < n; ++i) ans += max(a[i] - la, b[i] - lb); printf("%lld\n", ans); } }; int main() { ios::sync_with_stdio(false); cin.tie(0); int t; read(t); while (t--) { Solution solution = Solution(); solution.solve(); } }  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 这题的FP相对来说是比较容易实现的。 参考代码（Haskell） import Control.Monad solve :: IO () solve = do getLine as <- map read . words <$> getLine
bs <- map read . words <$> getLine let moves = zip (subtract (minimum as) <$> as) (subtract (minimum bs) <$> bs) print$ sum $(\(a, b) -> a + b - min a b) <$> moves

main :: IO ()
main = do
getLine >>= flip replicateM_ solve . read

1
2
3
4
5
6
7
8
9
10
11
12
13

## # Problem C - Boats Competition

### # 题目描述

$n$$n\leq50$）个体重分别为$w_i$$w_i\leq n$）的人两两组队，要求每一组的体重总和相等，最多能分多少组？

### # 题解

#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}

class Solution {
public:
void solve() {
int n;
vector<int> cnt(n + 1);
for (int i = 0; i < n; ++i) {
int a;
cnt[a]++;
}
int ans = 0;
for (int s = 2; s <= n * 2; ++s) {
int tot = 0;
for (int i = max(1, s - n); i * 2 <= s; ++i) {
int j = s - i;
if (j != i)
tot += min(cnt[i], cnt[j]);
else
tot += cnt[i] / 2;
}
ans = max(ans, tot);
}
printf("%d\n", ans);
}
};

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
while (t--) {
Solution solution = Solution();
solution.solve();
}
}

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

FP就递归处理就好了。

import Control.Monad
import Data.List

teamsWithSum :: Int -> [Int] -> Int
teamsWithSum s ws = f ws (reverse ws) div 2
where
f (a : as) (b : bs)
| a + b < s = f as (b : bs)
| a + b == s = 1 + f as bs
| otherwise = f (a : as) bs
f _ _ = 0

solve :: IO ()
solve = do
n <- read <$> getLine ws <- sort . map read . words <$> getLine
print $maximum [teamsWithSum s ws | s <- [2 .. 2 * n]] main :: IO () main = do getLine >>= flip replicateM_ solve . read  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 ## # Problem D - Binary String To Subsequences ### # 题目描述 有一个二进制串，问最少要将其分成多少个子序列，才能保证每个子序列都为$0$-$1$交替的形式？ 输出需要的子序列的个数，以及每个元素所属子序列的编号。 ### # 题解 记录下一个待使用的编号，以及当前结尾为$0$的子序列的编号和当前结尾为$1$的子序列的编号。对于每一个元素，如果没有能与其匹配的子序列，就要申请一个新的子序列；否则就将其进行匹配，并将对应的子序列移入另一组（$0$$1$$1$$0$）。 参考代码（C++） #include <cstdio> #include <iostream> #include <stack> #include <vector> using namespace std; template <typename T> void read(T &x) { x = 0; char c = getchar(); T sig = 1; for (; !isdigit(c); c = getchar()) if (c == '-') sig = -1; for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - '0'; x *= sig; } class Solution { public: void solve() { int n; read(n); string s; cin >> s; stack<int> a, b; vector<int> color(n); int idx = 1; for (int i = 0; i < n; ++i) { char c = s[i]; if (c == '0') { if (a.empty()) { color[i] = idx++; } else { color[i] = a.top(); a.pop(); } b.push(color[i]); } else { if (b.empty()) { color[i] = idx++; } else { color[i] = b.top(); b.pop(); } a.push(color[i]); } } printf("%d\n", idx - 1); for (int i : color) printf("%d ", i); printf("\n"); } }; int main() { int t; read(t); while (t--) { Solution solution = Solution(); solution.solve(); } } 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 FP通过递归进行处理。 参考代码（Haskell） import Control.Monad rec :: Int -> [Int] -> [Int] -> [Bool] -> [Int] rec next (z : zs) os (False : s) = z : rec next zs (z : os) s rec next [] os (False : s) = next : rec (succ next) [] (next : os) s rec next zs (o : os) (_ : s) = o : rec next (o : zs) os s rec next zs [] (_ : s) = next : rec (succ next) (next : zs) [] s rec _ _ _ _ = [] solve :: IO () solve = do getLine s <- map (== '1') <$> getLine
let a = rec 1 [] [] s
print $maximum a putStrLn$ unwords \$ map show a

main :: IO ()
main = do
getLine >>= flip replicateM_ solve . read

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

## # Problem E1 - Weights Division (easy version)

### # 题解

#include <cstdio>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;
typedef long long ll;

template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}

struct Node {
ll reward;
int w, n;
bool operator<(const Node &other) const { return reward < other.reward; }
};

class Solution {
vector<int> leaves;
ll sum = 0;
priority_queue<Node> pq;
void dfs(int u, int p, ll c) {
bool leaf = true;
for (auto &[v, w] : adj[u]) {
if (v == p)
continue;
leaf = false;
dfs(v, u, c + w);
pq.push(Node{(ll)(w - w / 2) * leaves[v], w, leaves[v]});
leaves[u] += leaves[v];
}
if (leaf) {
sum += c;
leaves[u] = 1;
}
}

public:
void solve() {
int n;
ll s;
adj = vector<vector<pair<int, int>>>(n + 1);
leaves = vector<int>(n + 1);
for (int i = 1; i < n; ++i) {
int u, v, w;
}
dfs(1, 0, 0);
ll ans = 0;
while (sum > s) {
ans++;
Node top = pq.top();
pq.pop();
sum -= top.reward;
int w = top.w / 2;
pq.push(Node{(ll)(w - w / 2) * top.n, w, top.n});
}
printf("%lld\n", ans);
}
};

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
while (t--) {
Solution solution = Solution();
solution.solve();
}
}
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

## # Problem E2 - Weights Division (hard version)

### # 题解

• 情形一：使用一条成本为$1$的边就可以满足要求，此时显然应该选择这条边。
• 情形二：比较对成本为$1$的优先队列连续操作两次的回报，与对成本为$2$的优先队列操作一次的回报。如果前者大于后者，则对优先队列$1$进行一次操作；否则对优先队列$2$进行一次操作。要注意，这里不能对优先队列$1$连续进行两次操作，因为第二和第三次操作的总回报可能小于对优先队列$2$操作一次的回报。

#include <cstdio>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;
typedef long long ll;

template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}

struct Edge {
int to, w, c;
};

struct Node {
ll reward;
int w, n;
bool operator<(const Node &other) const { return reward < other.reward; }
};

class Solution {
vector<int> leaves;
ll sum = 0;
priority_queue<Node> pqa, pqb;
void dfs(int u, int p, ll c) {
bool leaf = true;
for (auto &[v, w, t] : adj[u]) {
if (v == p)
continue;
leaf = false;
dfs(v, u, c + w);
Node node{(ll)(w - w / 2) * leaves[v], w, leaves[v]};
if (t == 1)
pqa.push(node);
else
pqb.push(node);
leaves[u] += leaves[v];
}
if (leaf) {
sum += c;
leaves[u] = 1;
}
}

public:
void solve() {
int n;
ll s;
leaves = vector<int>(n + 1);
for (int i = 1; i < n; ++i) {
int u, v, w, c;
}
dfs(1, 0, 0);
ll ans = 0;
while (sum > s) {
if (pqa.empty()) {
ans += 2;
Node top = pqb.top();
pqb.pop();
sum -= top.reward;
int w = top.w / 2;
pqb.push(Node{(ll)(w - w / 2) * top.n, w, top.n});
} else if (pqb.empty()) {
ans++;
Node top = pqa.top();
pqa.pop();
sum -= top.reward;
int w = top.w / 2;
pqa.push(Node{(ll)(w - w / 2) * top.n, w, top.n});
} else {
Node ta = pqa.top();
pqa.pop();
if (sum - ta.reward <= s) {
ans++;
break;
}
ll am = ta.reward, am1 = 0;
int w = ta.w / 2;
am += (ll)(w - w / 2) * ta.n;
if (!pqa.empty())
am1 = ta.reward + pqa.top().reward;
ll bm = pqb.top().reward;
if (max(am, am1) <= bm) {
ans += 2;
Node top = pqb.top();
pqb.pop();
sum -= top.reward;
int wb = top.w / 2;
pqb.push(Node{(ll)(wb - wb / 2) * top.n, wb, top.n});
pqa.push(ta);
} else {
ans++;
sum -= ta.reward;
pqa.push({(ll)(w - w / 2) * ta.n, w, ta.n});
}
}
}
printf("%lld\n", ans);
}
};

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
while (t--) {
Solution solution = Solution();
solution.solve();
}
}
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
124
125
126

## # Problem F - Yet Another Segments Subset

### # 题目描述

$n$$n\leq3000$）个区间$[l_i,r_i]$，要求从中选出尽可能多的区间，使得选出的区间中任意两个均相离或相含，问最多能选出多少个区间。

### # 题解

DP的顺序自然是从短的区间到长的区间，因为长的可以覆盖短的。接下来的问题是如何进行转移。

• 如果存在一个对应的区间，显然应该将其选中
• 如果不使用从$L$开始的区间，那么最优的显然是$[L+1,R]$
• 如果使用从$L$开始的区间，那么我们需要枚举所有从$L$开始且右端点小于$R$的区间，假设当前枚举到的区间为$[L,R']$，我们能够得到的额外区间数就是$[L,R']+[R'+1,R]$

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <set>
#include <vector>

using namespace std;

template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}

class Solution {
public:
void solve() {
int n;
vector<int> l(n), r(n);
set<int> s;
for (int i = 0; i < n; ++i)
int m = s.size();
map<int, int> d;
int idx = 0;
for (int i : s)
d[i] = idx++;
for (int i = 0; i < n; ++i)
l[i] = d[l[i]], r[i] = d[r[i]];
vector<vector<int>> dp(m, vector<int>(m));
vector<vector<bool>> exist(m, vector<bool>(m));
vector<vector<int>> lr(m);
for (int i = 0; i < n; ++i)
lr[l[i]].emplace_back(r[i]), exist[l[i]][r[i]] = true;
for (int i = 0; i < m; ++i)
sort(lr[i].begin(), lr[i].end());
for (int k = 0; k < m; ++k)
for (int i = 0; i + k < m; ++i) {
int j = i + k;
if (exist[i][j])
dp[i][j] = 1;
int extra = 0;
if (i < j)
extra = dp[i + 1][j];
for (int rr : lr[i]) {
if (rr >= j)
break;
extra = max(extra, dp[i][rr] + dp[rr + 1][j]);
}
dp[i][j] += extra;
}
printf("%d\n", dp[0][m - 1]);
}
};

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
while (t--) {
Solution solution = Solution();
solution.solve();
}
}
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