Codeforces Round #623 (Div. 1, based on VK Cup 2019-2020 – Elimination Round, Engine) 题解

Codeforces Round #623 (Div. 1, based on VK Cup 2019-2020 - Elimination Round, Engine)

Recommendations

用堆贪心。

const int N = 2e5 + 7;
int n;
ll s, ans;
pair<ll, ll> p[N];

int main() {
	rd(n);
	for (int i = 1; i <= n; i++) rd(p[i].fi);
	for (int i = 1; i <= n; i++) rd(p[i].se);
	sort(p + 1, p + n + 1);
	pq<ll> q;
	q.push(p[1].se), s += p[1].se;
	for (int i = 2; i <= n; i++) {
		while (p[i-1].fi < p[i].fi && q.size())
			++p[i-1].fi, s -= q.top(), q.pop(), ans += s;
		q.push(p[i].se), s += p[i].se;
	}
	while (q.size()) s -= q.top(), q.pop(), ans += s; 
	print(ans);
	return 0;
}

Double Elimination

不知道哪儿来的屑题。

Au Pont Rouge

题目太神仙了，先咕咕咕着。

Tourism

无奇环就想到二分图染色，随机染色即可，碰到正解的概率应该是 $\frac {1}{512}$，卡时即可。

赛后加了一组 Hack 数据好像卡了随机，偷懒面向数据编程了。

const int N = 81, K = 11, inf = 1e9;
int n, k, a[N][N], c[N], f[K][N], ans;

inline int solve() {
	for (int i = 1; i <= n; i++) {
		c[i] = rand() & 1;
		for (int j = 0; j < k; j++) f[j][i] = inf;
	}
	f[0][1] = 0;
	for (int i = 1; i < k; i++)
		for (int j = 1; j <= n; j++)
			for (int k = 1; k <= n; k++)
				if (c[j] ^ c[k]) f[i][j] = min(f[i][j], f[i-1][k] + a[k][j]);
	int ret = inf;
	for (int i = 1; i <= n; i++)
		if (c[1] ^ c[i]) ret = min(ret, f[k-1][i] + a[i][1]);
	return ret;
}

int main() {
	srand(time(0));
	double st = clock();
	rd(n), rd(k), ans = inf;
	for (int i = 1; i <= n; i++) rda(a[i], n);
	while ((clock() - st) / CLOCKS_PER_SEC < 2.9) ans = min(ans, solve());
	print(ans == 200000000 ? 0 : ans);
	return 0;
}

Strange Function

题目太神仙了，先咕咕咕着。

Bad Cryptography

题目太神仙了，先咕咕咕着。