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;
}