ABC373 D-F 详解
D
思路
说是有向图，实际上可以看作是无向图。因为如果有 \(x_{v_j} - x_{u_j} = w_j\)，那么就一定有 \(x_{u_j} - x_{v_j} = -w_j\)。
因为题目保证给出的数量关系没有冲突，所以如果我们知道了一个结点 \(a\) 的值，那么所有与它有数量关系的结点 \(b\) 的值都能被推出。从而如果一个连通块内有一个结点已经有值，那么整个连通块内的所有结点的值都能被推出。
我们可以对每个连通块任取一个结点，将它的值设为 \(0\)，然后将它作为起点用任意方式遍历一遍这个连通块即可。
实现
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int N = 200000 + 1;
vector<pair<int, int>> graph[N];
bitset<N> vis;
int que[N];
ll x[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
int u, v, w;
cin >> u >> v >> w;
graph[u].emplace_back(v, w);
graph[v].emplace_back(u, -w);
}
for (int i = 1; i <= n; ++i) if (!vis[i]) {
int front = 1, rear = 0;
vis[que[++rear] = i] = true;
while (front <= rear) {
int u = que[front++];
for (auto [v, w] : graph[u]) if (!vis[v]) {
x[v] = x[u] + w;
vis[que[++rear] = v] = true;
}
}
}
for (int i = 1; i <= n; ++i) {
cout << x[i] << " \n"[i == n];
}
return 0;
}
E
思路
对每一位候选者 \(i\) 来说，给 \(i\) 的票数 \(X\) 越多自然越容易当选，所以我们自然考虑二分最小的 \(X\)。
考虑每个候选者 \(i\)，check 给 \(i\) \(mid\) 票时 \(i\) 是否可以当选的时候实际上就是在 check 除了正在考虑的候选者 \(i\)，票数最多的 \(M\) 位候选者的票数是否都可以利用剩余的票数（\(K - \sum_{i=1}^{N} A_i - mid\)）达到 \(A_i + mid + 1\) 票，如果可以那么说明 \(i\) 不能当选，否则 \(i\) 可以当选。
先将 \(A\) 升序排序后，朴素的 check 实现每次都需要扫 \(M\) 位候选者计算，考虑全部 \(n\) 位候选者时总复杂度是 \(O(N \times (\log K) \times M)\)，无法接受。
考虑优化 check，注意到 check 等价于在算这样一个式子：
\((\sum_{j=N-M}^{N} \max((A_i + mid + 1) - A_j, 0)) - [i>n-m] \times max(A_i + mid + 1 - A_i, 0) - [i \leq n - m] \times max(A_i + mid + 1 - A_{n-m}, 0)\)
因为 \(A\) 被升序排序过了，所以注意到这个 \(\sum_{j=N-M}^{N} \max((A_i + mid + 1) - A_j, 0)\) 存在有一条分界线使得分界线以前对 \(\max((A_i + mid + 1) - A_j, 0)\) 的贡献都是 \(A_i + mid + 1\)，以后都是 \(0\)。这条分界线显然是可以在 \(A\) 上二分找到的，设这条分界线前的下标在 \(P\) 处，那么目标就变成了加速计算 \(\sum_{j=N-M}^{P} A_i + mid + 1 - A_j\)，这个是经典的，可以转换成 \((P - N - M + 1) \times (A_i + mid + 1) - \sum_{j=N-M}^{P} A_j\)，那么这个 \(\sum_{j=N-M}^{P} A_j\) 就能通过预处理前缀和求出了。
最终复杂度为 \(O(N \times (\log K) \times (\log N))\)，可以接受。
实现
有一些实现需要特判 \(N=M\) 的情况，否则 check 会因为数组访问越界产生 UB。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int N = 200000 + 1;
ll a[N], b[N], pre[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;;
cin >> n >> m;
if (n == m) {
for (int i = 1; i <= n; ++i) {
cout << "0" << " \n"[i == n];
}
return 0;
}
ll k;
cin >> k;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
memcpy(b + 1, a + 1, sizeof(ll) * n);
sort(b + 1, b + n + 1);
for (int i = 1; i <= n; ++i) {
pre[i] = pre[i - 1] + b[i];
}
ll rem = k - pre[n];
auto check = [=](int x, ll mid) {
ll tar = a[x] + mid + 1;
if (lower_bound(b + 1, b + n + 1, a[x]) - b <= n - m) {
int idx = (int)(lower_bound(b + n - m + 1, b + n + 1, tar) - b - 1);
return 1ll * (idx - (n - m)) * tar - (pre[idx] - pre[n - m]) > rem - mid;
}
int idx = (int)(lower_bound(b + n - m, b + n + 1, tar) - b - 1);
return 1ll * (idx - (n - m - 1)) * tar - (pre[idx] - pre[n - m - 1]) - max(tar - a[x], 0ll) > rem - mid;
};
for (int i = 1; i <= n; ++i) {
ll l = 0, r = rem;
while (l <= r) {
ll mid = (l + r) >> 1;
if (check(i, mid)) {
r = mid - 1;
} else {
l = mid + 1;
}
}
cout << (l > rem ? -1ll : l) << " \n"[i == n];
}
return 0;
}
F
思路
相信普及组毕业的同学都有能力随手列出这样一个 dp 式子：
设 $f[i][j] $ 为考虑完了前 \(i\) 类物品，选取的物品的重量之和不超过 \(j\) 时能贡献给高桥的快乐值之和最大是多少：
static long long f[MAXN][MAXW];
for (int i = 1; i <= n; ++i) {
for (int j = 0; w[i] * j <= W; ++j) {
for (int k = W; k >= w[i] * j; --k) {
f[i][k] = max(f[i][k], f[i - 1][k - w[i] * j] + 1ll * j * v[i] - 1ll * j * j));
}
}
}
容易得知计算量为 \(O(\sum_{i=1}^{N} \frac{W}{w_i} \times W)\)，\(w_i = 1\) 时计算量最大，故时间复杂度为 \(O(NW^2)\)。
那如果 \(w_i\) 互不相等呢？也就是 \(w_i = i\)， 此时时间复杂度为 \(\sum_{i=1}^{N} \frac{W}{i} \times W\)，普及组毕业的选手容易注意到这是一个调和级数，时间复杂度为 \(O(NW \log W)\)，对于本题的数据范围来说可以接受。
现实总是残酷的，但想象力丰富的人或许可以有时活在童话里。
我们应该还是小孩，天真和童趣暂未离我们而去，如果又是 OIer 那么可能还会带着一点青涩的哲思：如果可以把所有重量相同的物品取 \(j\) 个时贡献的快乐值通过某种方式取其精华并去其糟粕式地合并，那我们便可以实现每个出现过的重量 \(i\) 都只对时间复杂度贡献了一次 \(\frac{W}{i} \times W\)。
按照这个目标我们奋进。我们自然地设出 $f[i][j] $ 为考虑完了所有重量 \(\leq i\) 的物品，选取的物品重量之和不超过 \(j\) 时这些物品贡献的快乐值之和最大是多少，那么转移也是自然的：
static long long f[MAXN][MAXW];
for (int i = 1; i <= n; ++i) {
for (int j = 0; i * j <= W; ++j) {
for (int k = W; k >= i * j; --k) {
f[i][k] = max(f[i][k], f[i - 1][k - i * j] + val(i, j)));
}
}
}
其中 \(\text{val}[i][j]\) 表示所有重量为 \(i\) 的物品中选 \(j\) 个物品能贡献的最大快乐值。
那么我们现在的问题就转换为了求出每个 \(\text{val}(i, j)\)。
\(\text{val}[i][0]\) 为 \(0\) 毫无疑问，\(\text{val}[i][1]\) 肯定是所有重量为 \(i\) 的物品中价值的最大值减去 \(1\)。注意到假设这类物品的价值为 \(e\)，我们包括这一次在这类物品中已经取了 \(p\) 个物品，那么会贡献 \(ep - p^2\) 快乐值。我们将目前价值最大的物品计入贡献后，贡献会从 \(ep - p^2\) 变为 \(e(p+1) - (p+1)^2\)，也就是如果我们下一次还选择这一类物品，就会贡献 \(e(p+1) - (p+1)^2 - (ep - p^2) = e - 2p - 1\) 快乐值。
之后我们可以实时维护一个所有重量为 \(i\) 的物品当前能贡献的快乐值的序列。初始每类物品能贡献的快乐值就为这类物品的价值减 \(1\)。之后我们按 \(j\) 从 \(1\) 到 \(\lfloor W/i \rfloor\)，顺序依次求出 \(\text{val}[i][j]\)，每一轮我们贪心地选择能贡献最多快乐值的一类物品，贡献到 \(\text{val}[i][j]\)，并将这类物品当前能贡献的快乐值减去 \(2\)，进入下一轮。别忘了最后做一遍 \(val[i]\) 的前缀和。
形式化一点，我们设所有重量为 \(i\) 的物品的总数为 \(m\)，定义一个长度为 \(m\) 的序列 \(v\)，第 \(j\) 个物品的体积为 \(v_j\)，长度同样为 \(m\) 的序列 \(d\)。
- \(j=1,2,\dots,m\) :
- \(d_j \gets v_j - 1\).
- \(j=1,2,\dots,\lfloor W/i \rfloor\) :
- 求出一个下标 \(k\) 使得 \(d_i\) 的值在序列 \(d\) 中最大.
- \(\text{val}[i][j] \gets \text{val}[i][j - 1] + d_k\).
- \(d_k \gets d_k - 2\).
要动态支持获取最大值，删去最大值，插入一个值……我们容易想到用堆来维护 \(d\) 序列。至此，我们在 \(O(N + \sum_{i=1}^{W} \frac{W}{i} \log N) = O(N + W \log W \log N)\) 时间复杂度内求出了所有 \(\text{val}[i][j]\) 的值（至于为什么 \(N\) 没有乘 \(\log N\) 是因为堆是可以线性建的）。
于是我们就在总复杂度为 \(O(N + W \log W \log N + W^2 \log W)\) 内解决了此题。看似有点紧？实际很多地方跑得都不满。我的实现在本题数据下最慢的点只跑了 \(5\) ms，目前本题全站最优解。
实现
建议写 dp 时能滚动数组就滚动数组实现，缓存和空间都会友好许多。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int N = 3000 + 1;
vector<ll> vs[N];
ll heap[N], f[2][N];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, w;
cin >> n >> w;
for (int i = 1; i <= n; ++i) {
int w, v;
cin >> w >> v;
vs[w].emplace_back(v);
}
int cur = 0;
for (int i = 1; i <= w; ++i) {
int sz = (int)vs[i].size();
if (!sz) {
continue;
}
for (int j = 0; j < sz; ++j) {
heap[j + 1] = vs[i][j] - 1;
}
make_heap(heap + 1, heap + sz + 1);//线性建堆
cur ^= 1;
memcpy(f[cur], f[!cur], sizeof(ll) * (w + 1));
ll val = 0;
for (int j = 1; j <= w / i; ++j) {
if ((val += heap[1]) <= 0ll) {
break;
}//可能没什么用的剪枝
for (int k = w; k >= i * j; --k) {
f[cur][k] = max(f[cur][k], f[!cur][k - i * j] + val);
}
pop_heap(heap + 1, heap + sz + 1);
heap[sz] -= 2;
push_heap(heap + 1, heap + sz + 1);
}
}
cout << f[cur][w] << '\n';
return 0;
}