Codeforces Round #608 (Div. 2) 题解

Codeforces Round #608 (Div. 2)

Suits

枚举。

int main() {
	ll a, b, c, d, e, f, ans = 0;
	cin >> a >> b >> c >> d >> e >> f;
	for (ll i = 0; i <= d; i++) {
		ans = max(ans, min(a, i) * e + min(min(b, c), d - i) * f);
	}
	cout << ans << endl;
	return 0;
}

Blocks

贪心。

const int N = 207;
int n;
char s[N];

int main() {
	rd(n), rds(s, n);
	vi p;
	for (int i = 2; i < n; i++)
		if (s[i] != s[1]) p.pb(i), s[i] = s[i] == 'B' ? 'W' : 'B', s[i+1] = s[i+1] == 'B' ? 'W' : 'B';
	if (s[1] != s[n]) {
		if (n & 1) {
			for (int i = 1; i < n; i += 2) p.pb(i);
		} else return print(-1), 0;
	}
	print(p.size());
	for (ui i = 0; i < p.size(); i++)
		print(p[i], ' ');
	return 0;
}

Shawarma Tent

贪心。

const int N = 2e5 + 7;
int n, a, b, c[4];

int main() {
	rd(n), rd(a), rd(b);
	for (int i = 1, x, y; i <= n; i++) {
		rd(x), rd(y);
		if (x < a) c[2]++;
		if (x > a) c[3]++;
		if (y < b) c[1]++;
		if (y > b) c[0]++; 
	}
	int o = 0;
	for (int i = 1; i <= 3; i++)
		if (c[i] > c[o]) o = i;
	print(c[o]);
	if (o == 0) print(a, ' '), print(b + 1);
	if (o == 1) print(a, ' '), print(b - 1);
	if (o == 2) print(a - 1, ' '), print(b);
	if (o == 3) print(a + 1, ' '), print(b);
	return 0;
}

Portals

按贡献从大到小贪心，能选就选，用堆维护，判断是否能选时前缀和即可。

const int N = 5e3 + 7;
int n, m, a[N], b[N], p[N], ans;
pq< pi > q;

int main() {
	rd(n), rd(m), rd(b[0]);
	for (int i = 1, x; i <= n; i++)
		rd(a[i-1]), rd(b[i]), b[i] += b[i-1], rd(x), q.push(mp(x, i)), p[i] = i;
	for (int i = n - 1; ~i; i--) b[i] = min(b[i+1], b[i] - a[i]);
	if (b[0] < 0) return print(-1), 0;
	for (int i = 1, x, y; i <= m; i++) rd(x), rd(y), p[y] = max(p[y], x);
	while (q.size()) {
		int x = p[q.top().se], o = q.top().fi;
		q.pop();
		if (b[x]) {
			ans += o;
			for (int i = x; i <= n; i++) --b[i];
			for (int i = x - 1; ~i; i--) b[i] = min(b[i], b[i+1]);
		}
	}
	print(ans);
	return 0;
}

Common Number

把所有有可能的值都算一遍就好了，代码太丑了不贴了。

Divide The Students

题目太长了，不想读。