首页 > 代码库 > Codeforces Round #273 (Div. 2)

Codeforces Round #273 (Div. 2)

Codeforces Round #273 (Div. 2)

题目链接

A:签到,只要判断总和是不是5的倍数即可,注意判断0的情况

B:最大值的情况是每个集合先放1个,剩下都丢到一个集合去,最小值是尽量平均去分

C:假如3种球从小到大是a, b, c,那么如果(a + b) 2 <= c这个比较明显答案就是a + b了,因为c肯定要剩余了,如果(a + b)2 > c的话,就肯定能构造出最优的(a + b + c) / 3,因为肯定可以先拿a和b去消除c,并且控制a和b成2倍关系或者消除一堆,让剩下两堆尽量一样。

D:dp,先计算出最大高度h,然后1到h每一列看成一个物品,就是要选出其中几个组成r,求情况数,这个用01背包就可以求解了

代码:

A:

#include <cstdio>
#include <cstring>

int c, sum = 0;
int main() {
	for (int i = 0; i < 5; i++) {
		scanf("%d", &c);
		sum += c;
	}
	if (sum == 0 || sum % 5) printf("-1\n");
	else printf("%d\n", sum / 5);
	return 0;
}

B:

#include <cstdio>
#include <cstring>

typedef long long ll;

ll n, m;

int main() {
	scanf("%lld%lld", &n, &m);
	ll yu = n - m + 1;
	ll Max = yu * (yu - 1) / 2;
	yu = n % m;
	ll sb = n / m;
	ll sbb = sb + 1;
	ll Min = 0;
	if (sbb % 2) {
		Min += yu * (sbb - 1) / 2 * sbb;
	} else Min += yu * sbb / 2 * (sbb - 1);
	if (sb % 2) {
		Min += (m - yu) * (sb - 1) / 2 * sb;
	} else Min += (m - yu) * sb / 2 * (sb - 1);
	printf("%lld %lld\n", Min, Max);
	return 0;
}

C:

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

typedef long long ll;
ll a[3], ans = 0;

int main() {
	for (ll i = 0; i < 3; i++)
		scanf("%lld", &a[i]);
	sort(a, a + 3);
	if ((a[0] + a[1]) * 2 >= a[2]) printf("%lld\n", (a[0] + a[1] + a[2]) / 3);
	else printf("%lld\n", a[0] + a[1]);
	return 0;
}

D:

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

typedef long long ll;
const int N = 200005;
const ll MOD = 1000000007;

ll r, g;
int n;
ll dp[N];

int main() {
	scanf("%lld%lld", &r, &g);
	if (r > g) swap(r, g);
	ll sum = 0;
	for (int i = 1; ;i++) {
		sum += i;
		if (sum >= r + g) {
			if (sum > r + g) {
				sum -= i;
				i--;
			}
			n = i;
			break;
		}
	}
	dp[0] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = r; j >= i; j--) {
			dp[j] = dp[j] + dp[j - i];
			if (dp[j] > MOD) dp[j] -= MOD;
		}
	}
	ll sb = 0;
	for (int i = 0; i <= r + g - sum; i++) {
		if (r < i) break;
		sb = (dp[r - i] + sb) % MOD;
	}
	printf("%lld\n", sb);
	return 0;
}


Codeforces Round #273 (Div. 2)