Codeforces Round 585 (Div. 2)
题解
OI
一场罕见的国人时间的cf比赛，在学校机房的许多巨佬的带领下总算上蓝了，真是妙不可言。
A. Yellow Cards
最少罚下场：尽量把每个人都罚到只剩一张牌就下场
最多罚下场：先全部罚k值小的一队，再罚大的一对。
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
| #include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
const int INF = 0x3f3f3f3f;
int main() {
int a1, a2, k1, k2, n;
cin >> a1 >> a2 >> k1 >> k2 >> n;
if (k1 > k2) {
swap(k1, k2);
swap(a1, a2);
}
int mn, mx;
if (n <= a1 * (k1 - 1) + a2 * (k2 - 1)) {
mn = 0;
} else {
mn = n - (a1 * (k1 - 1) + a2 * (k2 - 1));
}
if (n <= a1 * k1) {
mx = n / k1;
} else {
mx = a1 + (n - a1 * k1) / k2;
}
cout << mn << ' ' << mx << endl;
}
|
B. The Number of Products
从左到右扫一遍，记录遇到的正数负数的数量，代码中cntn和cntp表示从之前的位置到现在有几个位置开始乘到现在的数是正（负），遇到负数就交换这两个值（想一想为什么）。记得全程int64，身边好多人没开完被叉掉了。
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
| #include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long int64;
const int MAXN = 2e5 + 10;
const int INF = 0x3f3f3f3f;
int a[MAXN];
#include <cctype>
#include <cstdio>
template <typename T = int>
inline T read() {
T X = 0, w = 0;
char ch = 0;
while (!isdigit(ch)) {
w |= ch == '-';
ch = getchar();
}
while (isdigit(ch)) {
X = (X << 3) + (X << 1) + (ch ^ 48);
ch = getchar();
}
return w ? -X : X;
}
int main() {
int n = read();
for (int i = 1; i <= n; i++) {
int x = read();
a[i] = (x > 0) ? 1 : -1;
}
int64 cntn = 0, cntp = 0;
int64 ansn = 0, ansp = 0;
int64 totn = 0, totp = 0;
for (int i = 1; i <= n; i++) {
if (a[i] < 0) {
ansn += cntp;
ansp += cntn;
swap(cntn, cntp);
cntn++;
totn++;
} else {
ansn += cntn;
ansp += cntp;
cntp++;
totp++;
}
}
cout << ansn + totn << ' ' << ansp + totp << endl;
}
|
C. Swap Letters
首先，本来相等的位置不用管，考虑以下两种不相等的情况
1
2
3
| A: ...a...b... ...b...b... ...b...a...
| ==> / ==>
B: ...b...a... ...a...a... ...b...a...
|
因此，方向相同的一对可以一步解决，方向相反的要先一步变成相同的。那么贪就是了，'a'的数量为奇数时无解。
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
| #include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
using namespace std;
const int MAXN = 2e5 + 10;
const int INF = 0x3f3f3f3f;
char a[MAXN], b[MAXN];
int main() {
int n;
cin >> n >> (a + 1) >> (b + 1);
int cnta = 0;
for (int i = 1; i <= n; i++) {
if (a[i] == 'a') cnta++;
if (b[i] == 'a') cnta++;
}
if (cnta % 2 == 1) {
cout << -1 << endl;
return 0;
}
vector<int> aabb, abba;
for (int i = 1; i <= n; i++) {
if (a[i] == 'a' && b[i] == 'b') {
aabb.push_back(i);
} else if (a[i] == 'b' && b[i] == 'a') {
abba.push_back(i);
}
}
vector<pair<int, int>> ans;
for (int i = 0; i < aabb.size(); i += 2) {
if (i + 1 == aabb.size()) break;
ans.push_back(make_pair(aabb[i], aabb[i + 1]));
}
for (int i = 0; i < abba.size(); i += 2) {
if (i + 1 == abba.size()) break;
ans.push_back(make_pair(abba[i], abba[i + 1]));
}
if (aabb.size() % 2 == 1 && abba.size() % 2 == 1) {
ans.push_back(make_pair(aabb[aabb.size() - 1], aabb[aabb.size() - 1]));
ans.push_back(make_pair(aabb[aabb.size() - 1], abba[abba.size() - 1]));
}
cout << ans.size() << endl;
for (int i = 0; i < ans.size(); i++) {
cout << ans[i].first << ' ' << ans[i].second << endl;
}
}
|
再次吐槽辣鸡 dev-cpp，我没有#include <vector>你还能编译?!
D. Ticket Game
简单博弈论，两边问号和相等的值可以约掉（希望不相等的人先走，另一个人复读机就行），剩下的当且仅当数和问号在异侧且两个问号对应一个9时相等的人胜。
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
| #include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 2e5 + 10;
char s[MAXN];
int main() {
int n;
cin >> n >> s;
int q = 0, sum = 0;
for (int i = 0; i < n / 2; i++) {
if (s[i] == '?')
q++;
else
sum += s[i] - '0';
}
for (int i = n / 2; i < n; i++) {
if (s[i] == '?')
q--;
else
sum -= s[i] - '0';
}
if (q * 9 == -sum * 2) {
cout << "Bicarp" << endl;
} else {
cout << "Monocarp" << endl;
}
}
|
E. Marbles
没有 @ywh666 巨佬提醒我真想不到这东西是个TSP
看到其实就可以想到是个状压。经过几次模拟可以发现，把和互相分离的成本是和移动顺序无关的，所以可以抽象成一个TSP，要把20种颜色全部分开，就是要遍历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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
| #include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long int64;
const int MAXN = 4e5 + 10;
const int MAXA = 25;
const int INF = 0x3f3f3f3f;
int a[MAXN];
int64 dis[MAXA][MAXA];
int64 dp[(1 << 20) + 10], now[MAXA];
int64 tsp() {
memset(dp, INF, sizeof dp);
dp[0] = 0;
for (int i = 0; i < (1 << 20); i++) {
memset(now, 0, sizeof now);
for (int j = 1; j <= 20; j++) {
if (i & (1 << (j - 1))) {
for (int k = 1; k <= 20; k++) {
now[k] += dis[j][k];
}
}
}
for (int j = 1; j <= 20; j++) {
if (i & (1 << (j - 1))) continue;
dp[i | (1 << (j - 1))] = min(dp[i | (1 << (j - 1))], dp[i] + now[j]);
}
}
return dp[(1 << 20) - 1];
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i <= 20; i++) {
for (int j = 1; j <= 20; j++) {
if (i == j) continue;
int cnt = 0;
for (int k = n; k >= 1; k--) {
if (a[k] == i)
cnt++;
else if (a[k] == j)
dis[i][j] += cnt;
}
}
}
cout << tsp() << endl;
}
|
F题题面太长，看都不想看，结果我那个房就我一个活人，毫无 hack 体验。。。
