Codeforces Round (2021-04-29)

Educational Codeforces Round 108 (Rated for Div. 2)

A. Red and Blue Beans

题目链接

题意

有 $r$ 个红豆和 $b$ 个蓝豆，要全部分进若干袋。每袋至少各有一个，两种豆子的数量差不能超过 $d$ ，问能不能分。

思路

先让 $r\le b$ 。红豆每袋至少放一个，所以最多分 $r$ 袋；每袋最多多放 $d$ 个蓝豆，总共就要求 $b-r\le dr$ ，也就是 $b\le(d+1)r$ 。

满足时把红豆一个一袋，再把蓝豆分进去就够了。乘法用 long long。

代码

#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

int main() {
	int t;
	cin >> t;
	while(t--) {
		int r, b, d;
		cin >> r >> b >> d;
		if(r > b) swap(r, b);
		if(r <= b &&  1ll * b <= 1ll * (1 + d) * r) cout << "YES" << endl;
		else cout << "NO" << endl;
	}
	return 0;
}

B. The Cake Is a Lie

题目链接

题意

从网格的 $(1,1)$ 走到 $(n,m)$ ，只能向右或向下。向右一步花当前行号的钱，向下一步花当前列号的钱，问能不能恰好花 $k$ 。

思路

看一下当前位置的行列乘积 $xy$ ：向右一步增加 $x$ ，向下一步增加 $y$ ，刚好都是这一步的花费。

所以不管怎么走，总花费都是 $nm-1$ ，直接和 $k$ 比较就行。

代码

#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

int main() {
	int t;
	cin >> t;
	while(t--) {
		int n, m, k;
		cin >> n >> m >> k;
		if(k == n * m - 1) cout << "YES" << endl;
		else cout << "NO" << endl;
	}
	return 0;
}

C. Berland Regional

题目链接

题意

每个学生属于一所大学，有各自的能力值。队伍人数固定为 $k$ 时，每所大学从强到弱每 $k$ 人组一队，不够一队的留下。求 $k=1\ldots n$ 时，所有参赛学生能力值的总和。

思路

先按大学分组，每组能力值从大到小排，再做前缀和。一所大学有 $t$ 人，队伍人数是 $k$ 时，能用上的就是最强的 $\lfloor t/k\rfloor k$ 人，查一次前缀和加到答案里。

每组只枚举 $k=1\ldots t$ ，所有组的大小加起来就是 $n$ ，所以这部分一共只扫 $n$ 次。时间主要在排序，是 $O(n\log n)$ ，总和用 long long。

代码

#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;

typedef long long ll;
const int maxn = 2e5 + 17;
int n, u[maxn];
vector<ll> v[maxn];
ll s[maxn];
int sz[maxn];

bool cmp(ll a, ll b) {
	return a > b;
}

int main() {
	int T;
	scanf("%d", &T);
	while(T--) {
		scanf("%d", &n);
		for(int i = 1; i <= n; i++) {
			s[i] = 0;
			v[i].clear();
			sz[i] = 0;
		}
		for(int i = 1; i <= n; i++) scanf("%d", &u[i]);
		for(int i = 1; i <= n; i++) {
			int tmp; scanf("%d", &tmp);
			v[u[i]].push_back(1ll * tmp);
			sz[u[i]]++;
		}
		for(int i = 1; i <= n; i++) {
			int t = sz[i];
			sort(v[i].begin(), v[i].end(), cmp);
			// for(int j = 0; j < t; j++) printf("%d%c", v[i][j], " \n"[j == t - 1]);
			for(int j = 1; j < t; j++) v[i][j] = v[i][j] + v[i][j - 1];
			for(int j = 1; j <= t; j++) {
				s[j] += v[i][t / j * j - 1];
			}
		}
		for(int i = 1; i <= n; i++) printf("%lld%c", s[i], " \n"[i == n]);
	}
	return 0;
}

D. Maximum Sum of Products

题目链接

题意

给两个长度为 $n$ 的数组 $a,b$ ，最多翻转 $a$ 的一个连续区间。问 $\sum a_i b_i$ 最大能是多少。

思路

f[l][r] 记翻转 $[l,r]$ 以后的整个点积。已经知道翻转内层 $[l+1,r-1]$ 的结果，再减掉两端原来的贡献，换成交换后的贡献就行：

f[l][r]=f[l+1][r-1]-a_lb_l-a_rb_r+a_lb_r+a_rb_l.

长度 1 就是不变，长度 2 单独算，再按区间长度递推。答案先取原来的总和，这样也包含不翻转的情况。时间和空间都是 $O(n^2)$ 。

代码

#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;

typedef long long ll;
const int maxn = 5e3 + 17;
int n;
ll a[maxn], b[maxn], f[maxn][maxn], ans;

bool cmp(ll a, ll b) {
	return a > b;
}

int main() {
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];
	for(int i = 1; i <= n; i++) cin >> b[i];
	for(int i = 1; i <= n; i++) f[1][1] += a[i] * b[i];
	for(int i = 2; i <= n; i++) f[i][i] = f[1][1];
	ans = f[1][1];
	// cout << ans << endl;
	for(int l = 1; l < n; l++) {
		int r = l + 1;
		f[l][r] = f[1][1] - a[l] * b[l] - a[r] * b[r] + a[l] * b[r] + a[r] * b[l];
		ans = max(ans, f[l][r]);
	}
	for(int i = 3; i <= n; i++) {
		for(int l = 1; l + i - 1 <= n; l++) {
			int r = l + i - 1;
			f[l][r] = f[l + 1][r - 1] - a[l] * b[l] - a[r] * b[r] + a[l] * b[r] + a[r] * b[l];
			ans = max(ans, f[l][r]);
		}
	}
	// cout << f[3][5] << endl;
	cout << ans << endl;
	return 0;
}

A. Red and Blue Beans

题意

思路

代码

B. The Cake Is a Lie

题意

思路

代码

C. Berland Regional

题意

思路

代码

D. Maximum Sum of Products

题意

思路

代码

Random Posts