哭いた閃光が目に刺さる / お別かれの鐘が鳴る / 神が成した歴史の / 結ぶ答えは砂の味がする
A. 美味しい美味しいハンバーグ
https://vjudge.net/contest/669299#problem/A
有一个很神奇的随机化做法：我们从前往后串签子，最开始签子数为 \(0\)，如果当前任何一个签子都没办法再串这一个就新增签子。如果没有签子可以用了，就说明这块肉不合法，挪到前 \(k\) 块中的随机位置使其优先被选择。
你会发现这个做法跑得很快，spdarkle 说因为 \(K\) 很小还保证有解，所以期望次数是非常对的。我太菜了他也没细说所以开摆。
由于神秘原因，我的 std::mt19937::operator()
如果外边不套一层 abs 就会起飞 
#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;
struct _ { int l, r, u, d; };
std::vector<_> a(n + 1), b(k + 1);
std::mt19937 rand(time(nullptr));
auto random = [&](int l, int r) {
return l + std::abs((int)rand()) % (r - l + 1);
};
for (int i = 1; i <= n; ++i)
std::cin >> a[i].l >> a[i].u >> a[i].r >> a[i].d;
for (;;) {
std::copy(a.begin() + 1, a.begin() + k + 1, b.begin() + 1);
for (int i = k + 1; i <= n; ++i) {
for (int j = 1; j <= k; ++j) {
if (std::min(b[j].r, a[i].r) >= std::max(b[j].l, a[i].l) && std::min(b[j].d, a[i].d) >= std::max(b[j].u, a[i].u)) {
b[j].l = std::max(b[j].l, a[i].l);
b[j].r = std::min(b[j].r, a[i].r);
b[j].u = std::max(b[j].u, a[i].u);
b[j].d = std::min(b[j].d, a[i].d);
goto issol;
}
}
std::swap(a[i], a[random(1, i)]);
goto nosol;
issol: ;
}
for (int i = 1; i <= k; ++i)
std::cout << b[i].l << ' ' << b[i].u << '\n';
break;
nosol: ;
}
return 0;
}B. Shik and Travel
https://vjudge.net/contest/669299#problem/B
最小化最大，显然需要二分答案，check 打个 DP。具体怎么 DP 呢？首先考虑暴力，设 \(f_{u, a, b}\) 表示在当前 \(mid\) 的限制下，从 \(u\) 出发到第一个叶子距离为 \(a\)，最后一个距离为 \(b\) 的可行性。那么有 \(f_{u,a,b} = (f_{l,a,i}\land f_{r,j,b})\lor (f_{r,a,i}\land f_{l,j,b})\)。
先不说转移，状态数已经难以接受。所以我们从状态数入手，显然如果存在一个 \(a'\le a\) 和 \(b'\le b\)，那么 \((a',b')\) 就是无用状态。也就是说，我们把所有有用的 \((a, b)\) 按 \(a\) 从小到大排序，\(b\) 应该是单调递减的；考虑这个抽象的过程，相当于从头到尾遍历一串状态，在路上碰到的所有较大的 \(b\) 都会被当场丢弃。
感性思考可以发现当我们试图让 \(b\) 最小的时候，这个状态最有用（即最不可能被丢弃）。对于一个 \(f_{l,a,i}\)，我们找到能够转移的 \(f_{r,j,b_{\min}}\) 来转移。正确性很好证明，我们的 check 只要求在根节点上存在任意合法状态，那只需要让最不可能被丢弃的不被丢弃即可，更可能被丢弃的状态是否被丢弃就不会产生影响了。
优化后的状态数在 \(u\) 上只会增加 \(\min(|a_l|,|b_r|)+\min(|a_r|,|b_l|)\)，即两个儿子上的状态数较小者，参考 DSU on tree，是 \(O(n\log)\) 的。加上对状态排序的数据结构，复杂度 \(O(n\log^2 n\log V)\)。
#include <bits/stdc++.h>
const long long inf = 1e18;
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;
std::cin >> n;
std::vector<std::vector<std::pair<int, int> > > g(n + 1);
for (int i = 2, x, w; i <= n; ++i) {
std::cin >> x >> w;
g[x].emplace_back(i, w);
}
long long res = -1;
for (long long l = 0, r = inf, mid; l <= r; ) {
mid = (l + r) >> 1;
if ([&](void) -> bool {
std::vector<std::vector<std::pair<long long, long> > > f(n + 1);
std::function<void(int)> DFS = [&](int x) {
if (g[x].empty()) {
f[x].emplace_back(0, 0);
return;
}
long long lim = mid;
for (auto [i, w] : g[x])
DFS(i), lim -= w;
std::vector<std::pair<long long, long long> > t;
for (int i = 0; i < 2; ++i) {
int j = 0;
auto l = g[x][0], r = g[x][1];
for (auto [a, b] : f[l.first]) {
for (; j + 1 < (int)f[r.first].size() && f[r.first][j + 1].first + b <= lim; ++j);
if (j < (int)f[r.first].size() && f[r.first][j].first + b <= lim)
t.emplace_back(a + l.second, f[r.first][j].second + r.second);
}
std::swap(g[x][0], g[x][1]);
}
std::sort(t.begin(), t.end());
for (auto [a, b] : t)
if (f[x].empty() || f[x].back().second > b)
f[x].emplace_back(a, b);
return;
};
DFS(1);
return !f[1].empty();
} ())
res = mid, r = mid - 1;
else
l = mid + 1;
}
std::cout << res << '\n';
return 0;
}D. Candy Piles
https://vjudge.net/contest/669299#problem/D
不难发现我们可以把题意转化为，把所有列从大到小排列，每次可以选择删掉最左边一列或最下边一行，删空者胜。
把该柱状图转化为网格图，定义边界为胜利点，对于非边界上的点，其一定可以往右走、往上走。若一个点上方、右侧点均为胜利点，此点为失败点；否则，此点为胜利点。