A-Task Computing
从 $n$ 个任务中选 $m$ 个 $(a_1, a_2, …, a_m)$ 出来并任意排序,收益是 $\sum\limits_{i=1}^mw_{a_i}\prod\limits_{j=1}^{i-1}p_{a_j}$,最大化收益。
先猜一个按某种方式排序,然后通过交换某两个元素来证明那种方案更优。
假设我们选出了 $a_1, a_2, …, a_m$,考虑某两个相邻元素 $a_x, a_y$。
$$
R_x=\sum\limits_{i=1}^{x-1}w_{a_i}\prod\limits_j^{i-1}p_{a_j} + w_{a_x}\prod\limits_j^{x-1}p_{a_j}+w_{a_y}p_{a_x}\prod\limits_j^{x-1}p_{a_j}+\sum\limits_{i=y+1}^{m}w_{a_i}\prod\limits_j^{i-1}p_{a_j}
$$
$$
交换 x,y
$$
$$
R_y=\sum\limits_{i=1}^{x-1}w_{a_i}\prod\limits_j^{i-1}p_{a_j} + w_{a_y}\prod\limits_j^{x-1}p_{a_j}+w_{a_x}p_{a_y}\prod\limits_j^{x-1}p_{a_j}+\sum\limits_{i=y+1}^{m}w_{a_i}\prod\limits_j^{i-1}p_{a_j}
$$
$$
可以发现 \prod\limits_j^{x-1}p_{a_j} 是不变的。最优解里相邻的 x, y 一定满足
$$
$$
R_x - R_y = (w_{a_x} + w_{a_y}p_{a_x} - w_{a_y} - w_{a_x}p_{a_y})\prod\limits_j^{x-1}p_{a_j} >= 0
$$
,那么最优解有多优只跟 $a_x$ 和 $a_y$ 有关。按照此不等式排序后用类似背包的 dp 求出答案。
$$
dp(i, j):=从后往前考虑i个任务,选择j个任务的最优收益
$$
转移时考虑选不选这个任务即可
$$
dp(i, j) = max(dp(i + 1,j), dp(i+1, j-1) \times p_i + w_i)
$$
注意精度。
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<array<int, 2>> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i][0];
}
for (int i = 0; i < n; i++) {
cin >> a[i][1];
}
sort(a.begin(), a.end(), [&](auto x, auto y) {
return x[0] * (10000ll - y[1]) > y[0] * (10000ll - x[1]);
});
vector<double> dp(m + 1);
for (int i = n - 1; i >= 0; i--) {
for (int j = m - 1; j >= 0; j--) {
dp[j + 1] = max(dp[j + 1], dp[j] * a[i][1] * 0.0001 + a[i][0]);
}
}
cout << fixed << setprecision(12) << dp[m] << '\n';
return 0;
}
K-NIO’s Sword
玩家初始有一把攻击力为 $0$ 的剑,需要依次击杀 $n$ 个敌人,仅当攻击力模 $n$ 与 $i$ 同余才能击杀第 $i$ 个敌人。玩家可以升级剑,每次升级相当于在当前攻击力后面添加一个 $0-9$ 之间的数字,问最少需要几次升级。
记 $A_i$ 为击杀第 $i$ 个怪物的攻击力。$A_0 = 0$。设为了击杀第 $i$ 只怪物进行了 $k_i$ 次升级,有
$$
A_{i - 1} + 10^{k_i}+x_i=A_i, (0\le x_i\lt 10^{k_i})
$$
由于 $A_i \equiv i \pmod n$,有 $(i - 1)\times 10^{k_i} + x_i\equiv i\pmod n(0\le x_i\lt 10^{k_i})$
对于每个 $i$,枚举 $k_i$,计算可行的 $x_i$ 的最小非负值。
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
if (n == 1) {
cout << "0\n";
return 0;
}
int ans = 0;
auto Get = [&](int x, int y) {
x = x * 10 % n;
int iter = 1, pow = 10;
while (true) {
int l = x, r = x + pow;
if (l <= y && y < r || (l <= y + n && y + n < r)) {
return iter;
}
iter++;
pow *= 10;
x *= 10;
x %= n;
}
};
for (int i = 1; i <= n; i++) {
ans += Get(i - 1, i % n);
}
cout << ans << '\n';
return 0;
}
H-Wall Builder II
给 $n$ 个$1\times 1$的矩形,$n-1$ 个 $1\times 2$ 的矩形,$n-2$ 个 $1\times 3$ 的矩形…,$1$ 个 $1\times n$ 的矩形,把这些矩形拼成一个大矩形,求大矩形的最小周长。
首先可以求出总共的面积大小 $S$,然后枚举所有可能的 $w\times h=S$,验证能不能拼出 $w\times h$ 的矩形。
验证的时候可以贪心,把所有小矩形从长到短放入 $w\times h$ 的大矩形,从上到下一行一行试着放,遇到某一行能放就放。对于$1$ 到 $100$ 中的所有 $n$,这个贪心都可以构造出理论上的最优解,即最接近的一组 $w\times h$。
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int tt;
cin >> tt;
while (tt--) {
int n;
cin >> n;
vector<int> cnt(n + 1);
for (int i = 1; i <= n; i++) {
cnt[i] = n - i + 1;
}
int area = 0;
for (int i = 1; i <= n; i++) {
area += i * cnt[i];
}
int a = area, b = 1;
for (int i = 1; i <= area / i; i++) {
if (area % i == 0) {
a = area / i;
b = i;
}
}
cout << (a + b) * 2 << '\n';
for (int i = 0; i < b; i++) {
int cur = 0;
while (cur < a) {
int j = min(a - cur, n);
while (cnt[j] == 0) {
j--;
}
cout << cur << " " << i << " " << cur + j << " " << i + 1 << '\n';
cur += j;
cnt[j]--;
}
}
}
return 0;
}