3 月 8 日测试题解
T1
题意
给你一张图 \(G = (V, E)\)，\(|V| = n\)，\(|E| = m\)，带边权、点权。你可以执行以下操作任意多次：
- 选取一个顶点，将其自身与与其相连的边删去
当你结束操作时，得到一张新图 \(G' = (V', E')\)，你需要保证 \(n' \ge 2\)，并且图联通。
现在求下面这个式子的值：
\[\max{(\frac{\sum_{v \in V'} w(v)}{\sum_{e \in E'} w(e)})} \]对于 \(20\%\) 的数据，\(n = 2\)；
对于 \(50\%\) 的数据，\(n \le 5\)；
对于 \(100\%\) 的数据，\(n \le 10^5\)。
思路
\(\text{20pts}\)
只有一条边，用脚趾头都写的出来。
\(\text{50pts}\)
考虑 DSU + 二进制枚举，倒着做，每次枚举一条边的两个顶点是否加入图中，这样可以保证图联通。
\(\text{100pts}\)
本题为结论题，结论就是最优的解一定只包含两个顶点。
为了证明这个结论，我们令 \(S_v\) 为当前选出的最优点权和，\(S_e\) 为当前选出的最优边权和，\(\Delta v\) 为将要加入的点权和，\(\Delta e\) 为将要加入的边权和。
如果更优的话，那么我们有：
\[\frac{S_v}{S_e} \le \frac{S_v + \Delta v}{S_e + \Delta e} \]\[S_v(S_e + \Delta e) \le S_e(S_v + \Delta v) \]\[S_v \Delta e \le S_e \Delta v \]也就是：
\[\frac{S_v}{S_e} \le \frac{\Delta v}{\Delta e} \]又：
\[\frac{S_v}{S_e} \le \frac{S_v + \Delta v}{S_e + \Delta e} \le \frac{\Delta v}{\Delta e} \]也就意味着你不如舍弃之前的，直接选 \(\Delta v\) 所对应的那个点。这样一番操作下来，你最终只能选两个点。
感觉证明有点假？凑合着看吧。
代码
\(\text{100pts}\)
#include <bits/stdc++.h>
using i64 = long long;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int n, m;
std::cin >> n >> m;
std::vector<int> a(n);
for (auto &i : a) {
std::cin >> i;
}
double ans = 0;
for (int i = 1; i <= m; i++) {
int u, v, w;
std::cin >> u >> v >> w;
ans = std::max(ans, double(a[u - 1] + a[v - 1]) / w);
}
std::cout << std::fixed << std::setprecision(2) << ans << "\n";
return 0;
}
T2
题意
四个数组 \(A\)，\(B\)，\(C\)，\(D\) 和一个整数 \(n\)。现从四个数组中各取一个数字，询问有多少种方案使得这四个数的和不超过 \(n\)。
对于 \(30\%\) 的数据，\(|A|,|B|,|C|,|D| \le 50\)；
对于另 \(30\%\) 的数据，\(n \le 1000\)；
对于 \(100\%\) 的数据，\(n \le 10^8\)，\(|A|,|B|,|C|,|D| \in [1, 5000]\)，\(A_i, B_i, C_i, D_i \in [0, 10^8]\)。
思路
\(\text{30pts}\)
此时数组的范围都比较小，考虑直接枚举，四重循环，时间复杂度为 \(O(|A| |B||C||D|)\)。
\(\text{60pts \& 100pts}\)
这道题 \(\text{60pts}\) 与 \(\text{100pts}\) 的做法应该是一样的。
考虑常见优化：折半。开两个桶 \(b_1\) 与 \(b_2\)，\(b_1\) 存储 \(A\) 与 \(B\) 中的和，\(b_2\) 存储 \(C\) 与 \(D\) 中的和。也就是说：
\[b_{1,i} = \sum_{i \in A, j \in B} {[i +j \le n]} \]\[b_{2,i} = \sum_{i \in C, j \in D} {[i +j \le n]} \]然后考虑对其中一个做前缀和，这里我们假设是 \(b_1\)。那么最终的答案就是：
\[\sum_{i = 0}^{n} {b_{1, n - i}b_{2, i}} \]时间复杂度为 \(O(|A||B| + |C||D| + n)\)。评价是能过就行，而且这个题也没有更优的做法了。
代码
#include <bits/stdc++.h>
using i64 = long long;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int n;
std::vector<int> num(4);
std::cin >> n;
for (auto &i : num) {
std::cin >> i;
}
std::vector<int> l[4];
for (int i = 0; i < 4; i++) {
l[i].resize(num[i]);
for (auto &j : l[i]) {
std::cin >> j;
}
}
std::vector<i64> lo(n + 1, 0), hi(n + 1, 0);
for (auto &i : l[0]) {
for (auto &j : l[1]) {
if (i + j > n) {
continue;
}
lo[i + j]++;
}
}
for (auto &i : l[2]) {
for (auto &j : l[3]) {
if (i + j > n) {
continue;
}
hi[i + j]++;
}
}
i64 ans = 0;
for (int i = 1; i <= n; i++) {
lo[i] += lo[i - 1];
}
for (int i = 0; i <= n; i++) {
ans += hi[i] * lo[n - i];
}
std::cout << ans << "\n";
return 0;
}
T3
题意
数轴上有 \(n\) 个动点，其中每个动点 \(\widetilde{P}\) 有两个属性：开始移动的时间 \(t_P\) 与速度 \(v_P\)。现在问在所有的点都开始移动后，处于第一的点与最后的点的距离最小值是多少。
\(n \le 100000\)。
思路
\(\text{100pts}\)
我们知道这道题的正解是三分法，但是有没有想过这个函数为什么是单谷函数？
证 nm 我不证了，评价是我想过但是想不出来，自己都不知道为什么是对的还要强迫我写题解？
反正就是你猜它是一个单谷函数，然后代进去发现很正确，注意一下细节然后就做完了。
从这道题得到的唯一收获就是：看到这种求最值的问题，先猜结论。
代码
#include <bits/stdc++.h>
using i64 = long long;
struct Node {
int t, v;
Node() {
t = 0, v = 0;
return;
}
};
long double calc(long double mid, std::vector<Node> a) {
long double minn, maxx;
minn = (mid - a[0].t) * a[0].v;
maxx = minn;
for (int i = 1; i < a.size(); i++) {
long double tmp = (mid - a[i].t) * a[i].v;
minn = std::min(minn, tmp);
maxx = std::max(maxx, tmp);
}
return maxx - minn;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
static const long double EPS = 1e-12;
int n;
std::cin >> n;
long double l = 0, r = 1e15;
std::vector<Node> a(n);
for (int i = 0; i < n; i++) {
std::cin >> a[i].t >> a[i].v;
l = std::max(l, (long double) a[i].t);
}
while (r - l > EPS) {
long double lmid = l + (r - l) / 3, rmid = r - (r - l) / 3;
std::cerr << lmid << " " << rmid << "\n";
if (calc(lmid, a) < calc(rmid, a) + EPS) {
r = rmid;
} else {
l = lmid;
}
}
std::cout << std::fixed << std::setprecision(2) << calc(l, a) << "\n";
return 0;
}