0%

Codeforces Round 574 (Div. 2)

Codeforces Round 574 (Div. 2)解题报告

A. Drinks Choosing 2s/256MB

题意

给定a[i],每次选出一个x,在集合中删去两个和x相等的数,最多做n/2上取整次,问最多划掉多少个。

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 <iostream>

const int N = 1001;

int cnt[N];

int main () {
register int i, j;
int n, m, x;

std::cin >> n >> m;
for (i = 1; i <= n; ++ i) {
std::cin >> x;
++ cnt[x];
}

int ans = 0;
for (i = 1; i <= m; ++ i) {
ans += (cnt[i] % 2);
}

std::cout << n - ans / 2;

return 0;
}

B. Sport Mafia 2s/256MB

题意

有一个盒子,每次操作可以放入或吃掉盒子里若干个糖果(第一次操作必须放入一个糖果)。给定操作数和盒子里最终剩余的糖果,求吃掉了多少个糖果。

解法

推一元二次方程的求根公式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
#include <cmath>

typedef long long ll;

int main () {
ll n, k, m, d;

std::cin >> n >> k;
m = (n + k) * 2;
d = std::round(std::sqrt(9 + 4 * m));
std::cout << n - (d - 3) / 2 << "\n";

return false;
}

C. Basketball Exercise

题意

给2*n个数组,选取若干上下左右不相邻的数,使得和最大,求这个和

解法

简单DP,令f[i][0/1/2]分别为第i列中,不取,取第一个数,取第二个数三种情况的累加和

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
#include <iostream>

typedef long long ll;
const int N = 1e5+1;

ll a[N][3], f[N][3];

inline ll max(ll x, ll y) {
return x > y ? x : y;
}

int main () {
register int i, j;
ll n;

std::cin >> n;
for (i = 1; i <= n; ++ i) std::cin >> a[i][0];
for (i = 1; i <= n; ++ i) std::cin >> a[i][1];

for (i = 1; i <= n; ++ i) {
f[i][0] = max(f[i - 1][1], f[i - 1][2]) + a[i][0];
f[i][1] = max(f[i - 1][0], f[i - 1][2]) + a[i][1];
f[i][2] = max(f[i - 1][0], max(f[i - 1][1], f[i - 1][2]));
}

std::cout << max(f[n][0], max(f[n][1], f[n][2]));

return 0;
}

D1. Submarine in the Rybinsk Sea (easy edition) &

D2. Submarine in the Rybinsk Sea (hard edition)