1928(924div2)
A. Rectangle Cutting
给出
void solve() {
int a, b;cin >> a >> b;
int x = a, y = b;
if (a > b)swap(a, b);//不能去掉
if (a % 2 == 0) {
a /= 2;
b *= 2;
} else if (b % 2 == 0) {
b /= 2;
a *= 2;
}
if (x == a || x == b) {
cout << "no\n";
}else{
cout << "yes\n";
}
}
if (a > b)swap(a, b);
不能去掉,HACK:12 6
不去掉就会输出no
void solve() {
int a, b;cin >> a >> b;
if (a % 2 == 0 && b % 2 == 0) {
cout << "yes\n";
} else if (a == 2 * b || 2 * a == b) {
cout << "no\n";
} else if (a % 2 == 0 || b % 2 == 0) {
cout << "yes\n";
} else {
cout << "no\n";
}
}
B. Equalize
给出一个长度为
易得相同的元素加上排列之后必然不相同,所以可以去重。
void solve() {
int n;cin >> n;
vector<int> a;
set<int> s;
for (int i = 0;i < n;i++) {
int x;cin >> x;
s.insert(x);
}
for (auto x : s)
a.push_back(x);
int ans = 0, j = 0;
for (int i = 0;i < s.size();i++) {
while (j < s.size() && a[j] - a[i] < n)j++;//j>=i
ans = max(ans, j - i);
}
cout << ans << '\n';
}
C. Physical Education Lesson
每个人都排成一排,并被要求站在 "第
给出在队伍中的位置
eg
解决这些问题的例子是
Solution
- 当在左边部分的时候:只需要满足
即可(当为 0 时需要特判为 2) - 反之满足
即可
暴力做法:(TLE)由于是
void solve() {
int n, x;cin >> n >> x;
int ans = 0;
for (int k = 2;k <= n;k++) {
int m = n % (2 * k - 2);
if (!m) m = 2;
if (m <= k) {
if (m == x) ans++;
} else {
m = 2 * k - m;
if (m == x) ans++;
}
}
cout << ans << '\n';
}
由上文:
可以变形为:
所以只需要判断哪些数是 (由于(2k-2)一定是偶数)
因子,即代表
NOTE: 试除法:要找到某个数的所有因子只需要
(不过当 vector
换为 set
去重即可)
auto find = [&](int n) {
vector<int> ans;
for (int i = 1;i * i <= n;i++) {
if (n % i == 0) {
ans.push_back(i);
ans.push_back(n / i);
}
}
return ans;
};
unordered_set
可换为 set
。但是 unordered_set
的插入是
void solve() {
int n, x;cin >> n >> x;
unordered_set<int> can;
auto find = [&](int a) {
unordered_set<int> ans;
for (int i = 1;i * i <= a;i++) {
if (a % i == 0) {
if (i % 2 == 0)can.insert(1 + i / 2);
if ((a / i) % 2 == 0)can.insert(1 + (a / i) / 2);
}
}
return ans;
};
for (auto i : find(n - x))can.insert(i);
for (auto i : find(n + x - 2))can.insert(i);
int ans = 0;
for (auto i : can) {
if (i >= x)ans++;
}
cout << ans << '\n';
}
D. Lonely Mountain Dungeons
中土世界居民的军队将由几个小队组成。众所周知,每一对同种族的生物分属不同的小队,军队的总兵力就会增加
有
Solution
三分(先单增,再单减)组合数
注意:long long
的计算稍不注意就会wa
三分法 (待更
codeforces round 924 (Div2) A-E 思路分享_哔哩哔哩_bilibili
对于计算分成
先算出
当每个队伍都是
对于一个人来说,其他队伍的人都有助于贡献:
对于和他同一个队伍的人来说:
其他队伍的也是一样,所以这时的贡献:
余数部分,只有部分队伍仅有 1 人,贡献:
余数和整数部分的接壤:则贡献:
对于后加入的余数部分,之前整数部分和他不在同一个队伍的
个人需要算上贡献
则该种族的战斗力
:
void solve() {
int n, b, x;cin >> n >> b >> x;
vector<int> c(n);for (int i = 0;i < n;i++)cin >> c[i];
auto check = [&](ll k) {//计算分成k个队伍时的战斗力
ll ans = 0;
for (auto i : c) {
ll t = i / k, tt = i % k, res = 0;
res += t * t * k * (k - 1) / 2;
if (tt > 0) {//可忽略这个条件
res += tt * (tt - 1) / 2;
res += tt * t * (k - 1);
}
ans += res * b;
}
ans -= (k - 1) * x;
return ans;
};
ll l = 1, r = *(max_element(c.begin(), c.end()));
while (r - l + 1 > 3) {//这段代码的主要目的是将l,r区间缩小到足够小了方便之后枚举
ll lmid = l + (r - l + 1) / 3;
ll rmid = r - (r - l + 1) / 3;
if (check(lmid) > check(rmid))r = rmid;//目的为了缩减区间长度
else l = lmid;
}
ll ans = 0;
for (ll i = l;i <= r;i++)ans = max(ans, check(i));
cout << ans << '\n';
}
D_哔哩哔哩_bilibili
(我认为最简单的思路):在
复杂度:最坏情况 (有
注:
num
数组只能开在外面,开在里面会 T ,要将num
数组放里面,需要将num
的大小改为
vector<int> num(2e5 + 1);
void solve() {
int n, b, x;cin >> n >> b >> x;
unordered_set<int> c;
for (int i = 0;i < n;i++) {
int x;cin >> x;
c.insert(x);
num[x]++;
}
auto check = [&](ll k) {
ll ans = 0;
for (auto i : c) {
ll t = i / k, tt = i % k, res = 0;
res += t * t * k * (k - 1) / 2;
res += tt * (tt - 1) / 2;
res += tt * t * (k - 1);
ans += res * b * num[i];
}
ans -= (k - 1) * x;
return ans;
};
ll l = 1, r = *(max_element(c.begin(), c.end())), ans = 0;
for (ll i = l;i <= r;i++)
ans = max(ans, check(i));
cout << ans << '\n';
for (auto p : c)num[p] = 0;
}
Codeforces Round 924 (Div. 2) A - E - 知乎
可以看出,最佳方案肯定是将每个种族均匀分配到每个队伍中。
假设某个种族有
由于
void solve() {
int n, b, x, m = 0;cin >> n >> b >> x;
vector<int>c(n);for (int i = 0;i < n;i++)cin >> c[i], m += c[i];
vector<ll>d(m + 1);
auto add = [&](int l, int r, ll x) {
d[l] += x;
if (r + 1 <= m)d[r + 1] -= x;
};
for (auto x : c) {
for (int i = 1;i < x;i++) {
ll sum = 1ll * x * (x - 1);
int t = x / i, r = x % i;
sum -= (i - r) * 1ll * t * (t - 1);
sum -= r * 1ll * (t + 1) * t;
add(i, i, sum / 2);
}
add(x, m, 1ll * x * (x - 1) / 2);
}
ll ans = 0;
for (int i = 1;i <= m;i++) {
d[i] += d[i - 1];
ans = max(ans, d[i] * b - 1ll * (i - 1) * x);
}
cout << ans << '\n';
}
D_哔哩哔哩_bilibili
平均分配最优,先排序,枚举队伍数量,种族数量小的下次不算了,数量大的在算一遍,直到不会被更新
#define int long long
void solve() {
int n, b, x;cin >> n >> b >> x;
vector<int> a(n);for (auto& i : a)cin >> i;sort(a.begin(), a.end());
int maxx = 1e9, divi = 0, hascal = 0;
int ans = 0;
for (int i = 2;divi <= n - 1 && i <= maxx;i++) {
int res = 0;
for (int j = divi;j <= n - 1;j++) {
if (a[j] <= i) {
hascal += b * (a[j] * (a[j] - 1)) / 2;
divi++;
} else {
int cnt = a[j] / i, mod = a[j] % i;
int a1 = i - mod, a2 = mod;
res += b * a[j] * (a[j] - 1) / 2;
res -= b * a1 * cnt * (cnt - 1) / 2;
res -= b * a2 * (cnt + 1) * cnt / 2;
}
}
res += hascal;
res -= (i - 1) * x;
ans = max(ans, res);
}
cout << ans << '\n';
}
E. Modular Sequence
给你两个整数
判断是否存在长度为
Solution
DP
暴力搜索
void solve() {
int n, x, y, s;cin >> n >> x >> y >> s;vector<int> a(n, 0);a[0] = x;
ll sum = x;
auto dfs = [&](auto self, int i, ll currSum) -> bool {
if (currSum > s) return false; // 前缀和剪枝
if (i == n) return currSum == s;
a[i] = (a[i - 1] + y) % y;
if (self(self, i + 1, currSum + a[i])) return true;
a[i] = a[i - 1] + y;
if (self(self, i + 1, currSum + a[i])) return true;
return false;
};
if (dfs(dfs, 1, sum)) {
cout << "yes\n";for (int i = 0;i < n;i++)cout << a[i] << " \n"[i == n - 1];
} else {
cout << "no\n";
}
}
官方题解:
我们先来看答案的形式:首先会有形如
的前缀,然后会有一些形如 的块。 我们可以从序列的所有元素中减去
,然后将所有元素除以 (所有元素最初的余数都为 ,因此它们都是可被 整除的)。设 。那么我们的序列将以 开头,然后会有形如 的块。 现在让我们计算这些值:
表示形如 且和为 的块序列的最小长度。我们可以利用动态规划计算从 到 的所有数的这个值。如果我们已经处理了从 到 的所有值,那么对于 ,我们已经计算出了最小长度,并且我们可以更新 的 值,总共不超过 的值有 个。在同一个 中,我们可以记录经过哪些值进行了重新计算,以便恢复答案。 现在,我们可以遍历形如
的第一个块的长度。然后我们就知道剩余块的和,并利用预先计算的 ,我们可以确定是否能够形成所需的序列。
codeforces round 924 (Div2) A-E 思路分享_哔哩哔哩_bilibili
序列形式如下图(当全部都减去
第一部分
其余部分
dp[x]={达到这个面积最少的长度,从哪里转移过来,最后高度}
要满足条件必须满足:dp[s][0]<=n
(待更

void solve() {
ll n, x, y, s;cin >> n >> x >> y >> s;
if (x + (n - 1) * (x % y) > s) {
cout << "NO\n";return;
}
s -= (x % y) * n;
vector<array<int, 3>>dp(s + 1, {INT_MAX,0,0});
for (int ns = x - x % y, h = x - x % y, i = 1;ns <= s;i++, h += y, ns += h) {
dp[ns] = {i,0,h};
}
for (int i = 0;i <= s;i++) {
if (dp[i][0] != INT_MAX) {
for (int j = 1, t = 0/*t代表一部分的柱子的长度*/;t + i <= s;t += j * y, j++) {
dp[t + i] = min(dp[t + i], {dp[i][0] + j, i, (j - 1)* y});
}
}
}
if (dp[s][0] > n) {
cout << "NO\n";return;
}
vector<int> ans(n);
int v = s;
while (v) {
auto [i, ns, h] = dp[v];
while (v != ns) {
i--;
ans[i] = h;
v -= h, h -= y;
}
}
cout << "YES\n";
for (auto i : ans)cout << i + (x % y) << " ";cout << "\n";
}