Codeforces Round 585 (Div. 2)

16 September 2019 | duanyll | Tags: OI 题解

一场罕见的国人时间的cf比赛，在学校机房的许多巨佬的带领下总算上蓝了，真是妙不可言。

A. Yellow Cards

最少罚下场：尽量把每个人都罚到只剩一张牌就下场

最多罚下场：先全部罚k值小的一队，再罚大的一对。

#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

从左到右$O(n)$扫一遍，记录遇到的正数负数的数量，代码中cntn和cntp表示从之前的位置到现在有几个位置开始乘到现在的数是正（负），遇到负数就交换这两个值（想一想为什么）。记得全程int64，身边好多人没开完被叉掉了。

#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

首先，本来相等的位置不用管，考虑以下两种不相等的情况

A: ...a...b...     ...b...b...     ...b...a...
      |        ==>      /      ==>
B: ...b...a...     ...a...a...     ...b...a...

因此，方向相同的一对可以一步解决，方向相反的要先一步变成相同的。那么贪就是了，'a'的数量为奇数时无解。

#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时相等的人胜。

#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

看到$a_i<20$其实就可以想到是个状压。经过几次模拟可以发现，把$a_i$和$a_j$互相分离的成本是和移动顺序无关的，所以可以抽象成一个TSP，要把20种颜色全部分开，就是要遍历20个点。

#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 体验。。。