Stewart’s theorem：在线段 \(AB\) 上取一点 \(M\)，使得 \(\vec{AB}=\lambda \vec{AM}\)。在 \(AB\) 上方任取一点 \(P\)，则有 \(PM^2=(1-\lambda) PA^2+\lambda PB^2-\lambda(1-\lambda) AB^2\)。
D. Akvizna
http://222.180.160.110:61235/contest/6393/problem/4
其实到这里应该发现了，WQS 的奖励都以一次项系数出现，原因也很显然，奖励的对象是一次项系数嘛。此外，WQS 内层 DP 数组的维度都应和操作次数无关，而 DP 值应为最大收益。这个也很显然。
令一轮比赛的惩罚是 \(mid\) 然后二分。令 \(f_{j}\) 表示剩余人数为 \(j\) 时的最大收益，那么有 \(f_{j}=\max\limits_{k\ge j}\left\{f_k+\frac {k-j}k\right\}-mid\)。最后在 \(f_0\) 处找答案即可。
然后就发现一个很可怕的问题，内层 DP 咋写。发现把 \(\frac {k-j}k\) 改写成 \(1-\frac jk\) 后出现交叉项，考虑斜优。令 \(a<b\)，那么 \(a\) 优于 \(b\) 当且仅当 \(\dfrac {f_a-f_b}{\frac 1a - \frac 1b} > j\)。维护单减的斜率即可。
笑话：二分 50 次不够，需要 60 次。
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n, k;
std::cin >> n >> k;
double l = 0., r = 1e5, mid;
auto calc = [&](double mid) {
std::vector<double> f(n + 1, -1e18);
f[n] = 0.;
int h = 1, t = 0;
std::vector<int> q(n + 1), p(n + 1);
q[++t] = n;
// printf("mid = %.3lf: \n", mid);
for (int i = n - 1; ~i; --i) {
for (; h < t && (f[q[h + 1]] - f[q[h]]) / (1. / q[h + 1] - 1. / q[h]) >= i; ++h);
f[i] = f[q[h]] + 1. - i * 1.0 / q[h] - mid, p[i] = p[q[h]] + 1;
// printf(" %d: f = %.3lf, p = %d, q[h] = %d(%.3lf / %d)\n", i, f[i], p[i], q[h], f[q[h]], p[q[h]]);
if (i) {
for (; h < t && (f[i] - f[q[t]]) / (1. / i - 1. / q[t]) >= (f[q[t]] - f[q[t - 1]]) / (1. / q[t] - 1. / q[t - 1]); --t);
q[++t] = i;
}
}
// printf("res = %.3lf\n", f[0] + p[0] * mid);
return std::make_pair(f[0], p[0]);
};
// calc(0.);
// return 0;
double res(0.);
for (int i = 1; i <= 60; ++i) {
mid = (l + r) / 2.;
auto t(calc(mid));
if (t.second >= k)
l = mid, res = t.first + k * mid;
else
r = mid;
}
std::cout << std::fixed << std::setprecision(8) << res << '\n';
return 0;
}E. Poborcy podatkowi
http://222.180.160.110:61235/contest/6393/problem/5
首先令 \(f_{u,l}(i),l=0,1,2,3\) 表示在 \(u\) 上挂了长度为 \(l\) 的半条链，共有 \(i\) 条整链的最大收益。
可以观察到是凸的。那么不难发现需要闽可夫斯基和，考虑 \(u\) 位置上的合并。首先需要注意到儿子上长度为 \(l\) 的链到父亲上会变成 \(l+1\)。显然每条可以不选；如果选了 \(cnt_a\) 条长度为 \(a\) 的半链，那么合并出来的结果是 \(cnt_1-cnt_3\) 条长度为 \(1\) 或 \(3\) 的链、\(cnt_2\bmod 2\) 条长度为 \(2\) 的链，并且要求两者不同时出现。发现这个东西基本上处理不了。
接着注意到这个形式有点像背包。但怎么处理 \(cnt_1\) 和 \(cnt_3\) 配对的这个要求呢？有个非常精妙的在物品体积上做文章的方法：
首先注意到我们最后的查询的答案肯定要求把所有儿子用完。那么不妨设体积之和为儿子总数 \(tot\)。接着，对 \(cnt_0\)（同时也是 \(cnt_4\)）没有限制，直接令其体积为 \(1\)。\(cnt_2\) 单独处理（等会儿会说），为了不对现在的问题产生影响也令其体积为 \(1\)。对于 \(cnt_1\) 和 \(cnt_3\)，显然两者平均体积需要为 \(1\)；你可以令 \(cnt_3\) 体积为 \(2\)，令 \(cnt_1\) 体积为 \(0\)。
接下来就有个很好的性质：\(cnt_1\) 必须和 \(cnt_3\) 配对才能让平均体积为 \(1\)。在 \(tot\) 处查找的答案，由 \(x\) 个体积不为 \(0\) 的物品和 \(tot-x\) 个体积为 \(0\) 的物品（\(cnt_1\)）组成，原因是背包会贪心地在所有『剩余』的分组中选择体积为 \(0\) 的一项。再计算一下 \(cnt_3\)，发现显然为 \(tot-x\)。符合目的。
在 \(dp_{tot}\) 处查找可以找到 \(cnt_1=cnt_3\) 时的答案；同理，在 \(dp_{tot-1},dp_{tot1+1}\) 处可以查找到 \(cnt_1=cnt_3\pm 1\) 的答案。
接下来再考虑 \(cnt_2\)，解决『\(cnt\bmod2=1\) 和 \(cnt_1\ne cnt_3\) 不能同时成立』的限制。那太好了，直接多开一维记录 \(cnt_2\bmod 2\) 即可。
啊啊太妙了。像利用体积为 \(-1,1\) 的随机数据背包期望最大体积不超过 \(\sqrt V\) 的那个方法，显然就没有办法利用凸性了。所以这或许是闽可夫斯基和做法的唯一解？
需要知道，如果设 \(cnt_1\) 为 \(2\) 而 \(cnt_3\) 为 \(0\)，始终会出一些问题。这个我和 yly 讨论了一下没啥结果。
#include <bits/stdc++.h>
const long long inf = 1e12;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen("1.in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n;
std::cin >> n;
std::vector<std::vector<std::pair<int, int> > > g(n + 1);
for (int i = 1, x, y, w; i < n; ++i) {
std::cin >> x >> y >> w;
g[x].emplace_back(y, w), g[y].emplace_back(x, w);
}
using arr = std::vector<long long>;
std::vector<arr> f(n + 1, arr(4));
struct node {
std::vector<arr> f;
node(): f(2) {}
node(std::vector<arr> f1): f(f1) {}
arr& operator[](int q) {
return f[q];
}
};
auto getmax = [&](arr p, arr q) {
arr res(p);
if (q.size() > p.size())
res.resize(q.size());
for (int i = 0; i < (int)q.size(); ++i)
res[i] = std::max(res[i], q[i]);
return res;
};
auto merge = [&](arr &p, arr &q) {
arr res(p.size() + q.size() - 1), dp(p.size()), dq(q.size());
std::adjacent_difference(p.begin(), p.end(), dp.begin());
std::adjacent_difference(q.begin(), q.end(), dq.begin());
std::merge(dp.begin() + 1, dp.end(), dq.begin() + 1, dq.end(), res.begin() + 1, std::greater<long long> ());
res[0] = p[0] + q[0];
std::partial_sum(res.begin(), res.end(), res.begin());
return res;
};
std::function<void(int, int)> DFS = [&](int x, int fa) {
if ((int)g[x].size() == 1 && x != 1) {
f[x][1] = f[x][2] = f[x][3] = -inf;
return;
}
int tot = (int)g[x].size() - (x != 1);
std::vector<arr> w1(1), w2(1);
for (auto [i, w] : g[x])
if (i != fa) {
DFS(i, x);
w1.push_back({ f[i][0] + w, std::max(f[i][0], f[i][3] + w), f[i][2] + w });
w2.push_back({ -inf, f[i][1] + w });
}
auto fun = [&](arr &p, arr &q) {
arr res(p.size() + q.size() - 1, -inf);
for (int ip = 0; ip < 2; ++ip)
for (int iq = 0; iq < 2; ++iq) {
arr tp, tq;
for (int i = ip; i < (int)p.size(); i += 2)
tp.push_back(p[i]);
for (int i = iq; i < (int)q.size(); i += 2)
tq.push_back(q[i]);
auto t = merge(tp, tq);
for (int i = 0; i < (int)t.size(); ++i)
if (i * 2 + ip + iq < (int)res.size())
res[i * 2 + ip + iq] = std::max(res[i * 2 + ip + iq], t[i]);
}
return res;
};
std::function<node(int, int)> calc = [&](int l, int r) {
if (l == r)
return node({ w1[l], w2[l] });
int mid = (l + r) >> 1;
node t1(calc(l, mid)), t2(calc(mid + 1, r));
return node({ getmax(fun(t1[0], t2[0]), fun(t1[1], t2[1])),
getmax(fun(t1[0], t2[1]), fun(t1[1], t2[0])) });
};
auto t(calc(1, tot));
f[x][0] = t[0][tot], f[x][1] = t[0][tot - 1], f[x][2] = t[1][tot], f[x][3] = t[0][tot + 1];
return;
};
DFS(1, -1);
std::cout << f[1][0] << '\n';
return 0;
}