Educational Codeforces Round 108 (Rated for Div. 2)
A. Red and Blue Beans
题意
有 个红豆和 个蓝豆，要全部分进若干袋。每袋至少各有一个，两种豆子的数量差不能超过 ，问能不能分。
思路
先让 。红豆每袋至少放一个，所以最多分 袋；每袋最多多放 个蓝豆，总共就要求 ，也就是 。
满足时把红豆一个一袋，再把蓝豆分进去就够了。乘法用 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
题意
从网格的 走到 ，只能向右或向下。向右一步花当前行号的钱，向下一步花当前列号的钱，问能不能恰好花 。
思路
看一下当前位置的行列乘积 ：向右一步增加 ，向下一步增加 ，刚好都是这一步的花费。
所以不管怎么走，总花费都是 ，直接和 比较就行。
代码
#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
题意
每个学生属于一所大学，有各自的能力值。队伍人数固定为 时，每所大学从强到弱每 人组一队，不够一队的留下。求 时，所有参赛学生能力值的总和。
思路
先按大学分组，每组能力值从大到小排，再做前缀和。一所大学有 人，队伍人数是 时，能用上的就是最强的 人，查一次前缀和加到答案里。
每组只枚举 ，所有组的大小加起来就是 ，所以这部分一共只扫 次。时间主要在排序，是 ，总和用 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
题意
给两个长度为 的数组 ，最多翻转 的一个连续区间。问 最大能是多少。
思路
f[l][r] 记翻转 以后的整个点积。已经知道翻转内层 的结果，再减掉两端原来的贡献，换成交换后的贡献就行：
长度 1 就是不变，长度 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;
}