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\)

  1. \(j=1,2,\dots,m\) :
    • \(d_j \gets v_j – 1\).
  2. \(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;
}
请登录后发表评论

    没有回复内容