A - Minimum Path
https://www.luogu.com.cn/problem/CF1473E
- 经典套路,发现可以把 max 和 min 换成任意路径中的边,然后 max 和 min 就会最小化这个式子
- 故写一个 Dijkstra + DP,求这个式子的最小值即可
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGEstd::ios::sync_with_stdio(false);std::cin.tie(nullptr), std::cout.tie(nullptr);
#elsestd::freopen(".in", "r", stdin);std::freopen(".out", "w", stdout);const auto stime = std::chrono::steady_clock::now();
#endifint n, m;std::cin >> n >> m;using arr = std::vector<long long>;using brr = std::vector<arr>;std::vector<std::vector<std::pair<int, int> > > g(n + 1);std::vector<brr> dis(2, brr(2, arr(n + 1, 1e18))), vis(2, brr(2, arr(n + 1)));for (int x, y, w; m--; ) {std::cin >> x >> y >> w;g[x].emplace_back(y, w);g[y].emplace_back(x, w);}dis[0][0][1] = 0;std::array<std::array<std::priority_queue<std::pair<long long, int> >, 2>, 2> q;q[0][0].emplace(0, 1);for (int i = 0; i < 2; ++i) {for (int j = 0; j < 2; ++j) {for (; !q[i][j].empty(); ) {int f = q[i][j].top().second;q[i][j].pop();if (vis[i][j][f])continue;vis[i][j][f] = 1;for (auto k : g[f]) {if (dis[i][j][k.first] > dis[i][j][f] + k.second) {dis[i][j][k.first] = dis[i][j][f] + k.second;q[i][j].emplace(-dis[i][j][k.first], k.first);}if (!i && dis[1][j][k.first] > dis[i][j][f]) {dis[1][j][k.first] = dis[i][j][f];q[1][j].emplace(-dis[1][j][k.first], k.first);}if (!j && dis[i][1][k.first] > dis[i][j][f] + 2 * k.second) {dis[i][1][k.first] = dis[i][j][f] + 2 * k.second;q[i][1].emplace(-dis[i][1][k.first], k.first);}}}}}for (int i = 2; i <= n; ++i)std::cout << std::min({ dis[0][0][i], dis[1][1][i] }) << ' ';std::cout << '\n';
#ifndef ONLINE_JUDGEstd::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endifreturn 0;
}
B - Train Delay
https://vjudge.net/contest/750645#problem/B
-
简化题目很重要的一个转化是由于 \(S\le T\) 带来的 \(S\) 和 \(T\) 地位平等,考虑把出发和到达分别看作一次事件处理。
-
按照所有事件的发生时刻排序,有:
- 对于一次出发事件,可以得到在其之前该站点所有到达事件的 \(\max\{T'\}\),用之更新 \(X\) 即可。
- 对于一次到达事件,由于对应的 \(X\) 已经确定,更新该站点当前最大值即可。
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGEstd::ios::sync_with_stdio(false);std::cin.tie(nullptr), std::cout.tie(nullptr);
#elsestd::freopen(".in", "r", stdin);std::freopen(".out", "w", stdout);const auto stime = std::chrono::steady_clock::now();
#endifint n, m;std::cin >> n >> m;std::vector<int> d(m + 1);std::cin >> d[1];struct event {int t, op, id, x;};std::vector<event> a;std::vector<int> mx(n + 1);for (int i = 1, x, y, s, t; i <= m; ++i) {std::cin >> x >> y >> s >> t;a.push_back({ s, 0, i, x });a.push_back({ t, 1, i, y });}std::sort(a.begin(), a.end(), [&](event &x, event &y) { return x.t == y.t ? x.op > y.op : x.t < y.t; });for (auto [t, op, id, x] : a)if (op == 1)mx[x] = std::max(mx[x], t + d[id]);else if (id != 1)d[id] = std::max(mx[x] - t, 0);for (int i = 2; i <= m; ++i)std::cout << d[i] << ' ';std::cout << '\n';
#ifndef ONLINE_JUDGEstd::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endifreturn 0;
}
C - Complete The Graph
https://www.luogu.com.cn/problem/CF715B
神仙二分
-
如果初始把所有白边置为 \(1\),那么会想到调整法构造
-
但是不知道应该在哪些边上调整,确定调整多少似乎也没有什么简单的做法
-
故平均用力,构造一个 边1 += 1,边2 += 1,边3 += 1, ..., 边cnt0 += 1, 边1 += 1, 边2 += 1, ... 的操作序列
容易发现每次操作最多让当前最短路长度增加 1,而且有单调性
-
故二分答案即可
#include <bits/stdc++.h>
const __int128 inf = 1e18;
const __int128 inff = 1e23;
int main() {
#ifdef ONLINE_JUDGEstd::ios::sync_with_stdio(false);std::cin.tie(nullptr), std::cout.tie(nullptr);
#elsestd::freopen(".in", "r", stdin);std::freopen(".out", "w", stdout);const auto stime = std::chrono::steady_clock::now();
#endifint n, m, s, t, l, cnt = 0;std::cin >> n >> m >> l >> s >> t, ++s, ++t;std::vector<std::tuple<int, int, long long> > u(m + 1);std::vector<std::vector<std::pair<int, long long> > > g(n + 1);for (int i = 1, x, y; i <= m; ++i) {long long w;std::cin >> x >> y >> w, ++x, ++y;if (w == 0)w = -(++cnt);g[x].emplace_back(y, w), g[y].emplace_back(x, w);u[i] = { x, y, w };}std::vector<int> vis(n + 1);std::vector<__int128> dis(n + 1);std::vector<long long> k(cnt + 1);__int128 res = -1;auto check = [&](__int128 x) {for (int i = 1; i <= cnt; ++i)k[i] = x / cnt + (i <= x % cnt);std::fill(vis.begin() + 1, vis.end(), 0);std::fill(dis.begin() + 1, dis.end(), inf);std::priority_queue<std::pair<__int128, int> > q;dis[s] = 0, q.emplace(0, s);for (; !q.empty(); ) {int f = q.top().second;q.pop();if (vis[f])continue;vis[f] = 1;for (auto [v, w] : g[f]) {if (w < 0)w = k[-w];if (dis[v] > dis[f] + w) {dis[v] = dis[f] + w;q.emplace(-dis[v], v);}}}return dis[t] <= l;};for (__int128 l = cnt, r = cnt * inf, mid; l <= r; ) {mid = (l + r) >> 1;if (check(mid))res = mid, l = mid + 1;elser = mid - 1;}if (res == -1)std::cout << "NO\n";else {check(res);if (dis[t] != l)std::cout << "NO\n";else {std::cout << "YES\n";for (int i = 1; i <= m; ++i) {auto [x, y, w] = u[i];if (w < 0)w = k[-w];std::cout << x - 1 << ' ' << y - 1 << ' ' << w << '\n';}}}
#ifndef ONLINE_JUDGEstd::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endifreturn 0;
}
A - 重力球
https://www.luogu.com.cn/problem/P7473
-
\(m\) 相对很小,看看有没有什么基于 \(m\) 的做法
-
每次球停下的位置一定是某个障碍物(或边界)上 / 下 / 左 / 右的格子,故可以在这 \(O(n + m)\) 个点上建图
-
怎么同时维护两个球的信息呢,发现 \(m\) 还是很小,所以可以把两个球塞一起作为一个状态
-
\(m^2\) 次 Dij 还是太激进了 进一步思考发现可能的终点共 \(m\) 个 并且彼此不区分
故以这 \(m\) 个终点跑多源最短路即可
但 5e6 跑 Dij 还是太勉强了。发现边权为 1,为什么不 BFS 呢 😅
-
发现起点可能不在我们限定的点上,但可以人为选择一次重力方向,然后就回到刚刚的问题了
或者离线也是一种方法
疑似常数太大,拼尽全力勉强卡过
#include <bits/stdc++.h>
const int LEN = (1 << 20);
#ifdef ONLINE_JUDGE
inline int nec(void) {static char buf[LEN], *p = buf, *e = buf;if (p == e) {e = buf + fread(buf, 1, LEN, stdin);if (e == buf)return EOF;p = buf;}return *p++;
}
#else
#define nec getchar
#endif
inline bool read(int &x) {x = 0;bool f = 0;char ch = nec();while (ch < '0' || ch > '9') {if (ch == EOF)return 0;if (ch == '-')f = 1;ch = nec();}while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = nec();}if (f)x = -x;return 1;
}
void print(int x) {if (x < 0) {putchar('-');x = -x;}if (x >= 10)print(x / 10);putchar(x % 10 + '0');return;
}
void print(int x, char ch) {print(x);putchar(ch);return;
}
const int inf = 0x3f3f3f3f;
const int dir[][2] = {{ -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 }};
int main() {
#ifdef ONLINE_JUDGEstd::ios::sync_with_stdio(false);std::cin.tie(nullptr), std::cout.tie(nullptr);
#elsestd::freopen(".in", "r", stdin);std::freopen(".out", "w", stdout);const auto stime = std::chrono::steady_clock::now();
#endifint n, m, q;read(n), read(m), read(q);std::vector<std::pair<int, int> > pos(m + 1);std::vector<std::vector<int> > a(n + 1, std::vector<int> (n + 1));for (int i = 1, x, y; i <= m; ++i) {read(x), read(y);pos[i] = { x, y }, a[x][y] = -1;}for (int i = 1; i <= n; ++i)pos.emplace_back(0, i), ++m;for (int i = 1; i <= n; ++i)pos.emplace_back(i, n + 1), ++m;for (int i = 1; i <= n; ++i)pos.emplace_back(n + 1, i), ++m;for (int i = 1; i <= n; ++i)pos.emplace_back(i, 0), ++m;int cnt = 0;std::vector<std::pair<int, int> > u(1);for (int i = 1; i <= m; ++i)for (auto [fx, fy] : dir) {int nx = pos[i].first + fx, ny = pos[i].second + fy;if (nx >= 1 && nx <= n && ny >= 1 && ny <= n && !a[nx][ny])a[nx][ny] = ++cnt, u.emplace_back(nx, ny);}std::vector<std::vector<std::array<int, 4> > > top(n + 1, std::vector<std::array<int, 4> > (n + 1));for (int j = 1; j <= n; ++j) {for (int i = 1; i <= n; ++i)if (a[i][j] != -1) {if (i == 1 || a[i - 1][j] == -1)top[i][j][0] = a[i][j];elsetop[i][j][0] = top[i - 1][j][0];}for (int i = n; i; --i)if (a[i][j] != -1) {if (i == n || a[i + 1][j] == -1)top[i][j][1] = a[i][j];elsetop[i][j][1] = top[i + 1][j][1];}}for (int i = 1; i <= n; ++i) {for (int j = 1; j <= n; ++j)if (a[i][j] != -1) {if (j == 1 || a[i][j - 1] == -1)top[i][j][2] = a[i][j];elsetop[i][j][2] = top[i][j - 1][2];}for (int j = n; j; --j)if (a[i][j] != -1) {if (j == n || a[i][j + 1] == -1)top[i][j][3] = a[i][j];elsetop[i][j][3] = top[i][j + 1][3];}}const int N = cnt * cnt;std::vector<std::vector<int> > g(N + 1);auto encode = [&](int x, int y) {return (x - 1) * cnt + y;};auto decode = [&](int id) {return std::make_pair((id - 1) / cnt + 1, (id - 1) % cnt + 1);};for (int i = 1; i <= N; ++i)for (int j = 0; j < 4; ++j) {auto [a, b] = decode(i);g[encode(top[u[a].first][u[a].second][j], top[u[b].first][u[b].second][j])].emplace_back(i);}std::vector<int> dis(N + 1, inf), vis(N + 1);{std::queue<int> q;for (int i = 1; i <= cnt; ++i)dis[encode(i, i)] = 0, q.push(encode(i, i)), vis[encode(i, i)] = 1;for (; !q.empty(); ) {int x = q.front();q.pop();for (auto i : g[x])if (!vis[i])dis[i] = dis[x] + 1, vis[i] = 1, q.push(i);}}for (int a, b, c, d; q--; ) {read(a), read(b), read(c), read(d);if (a == c && b == d)print(0, '\n');else {int res = inf;for (int j = 0; j < 4; ++j)res = std::min(res, dis[encode(top[a][b][j], top[c][d][j])] + 1);if (res == inf)print(-1, '\n');elseprint(res, '\n');}}
#ifndef ONLINE_JUDGEstd::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endifreturn 0;
}
B - 矩阵游戏
https://www.luogu.com.cn/problem/P7515
-
把问题形式化一下,现在有 \(n\times m\) 个未知数和 \((n-1)\times (m-1)\) 个方程
那么可以对边上一圈任意赋值,限制是左上角这 \((n-1)\times (m-1)\) 个未知数必须落在 \([0,10^6]\) 上
-
有一个很容易观察到的性质,对于一个 \(a\),选取一个 \(v\),并把棋盘黑白染色,那么把所有黑格 \(+=v\),白格 \(-=v\),对应的 \(b\) 是不会变的。
-
这个操作是涉及全局的,太苛刻了,有没有什么更 mild 的构造?
发现只对一行 / 列黑白染色并操作也可以得到相同的结果。能感受到操作无法再简化了。考虑用这个版本的操作调整。
-
故大力令周围一圈的临时解 \(a'\) 为 \(0\),令每行、列的调整 delta 为 \(r_i,c_i\),可以得到若干个关于 \(0\) 和 \(10^6\) 的约束。最后建出来一个完全二分图状物,跑差分约束即可,容易发现复杂度正确。
-
实现技巧:规划一下 \(r\) 和 \(c\) 的染色方式,使得它们错开,可以把所有位置都写作 \(a'_{i,j}+c-r\) 或 \(a'_{i,j}+r-c\) 的形式,便于差分约束
C - Tax
https://www.luogu.com.cn/problem/P6822
- 容易想到分类讨论,如果钦定是入边贡献边权,那么出边边权不能大于入边边权;否则,出边贡献边权。
- 考虑把每个点上的出边按边权从小到大排序,显然需要入边贡献的是一段前缀,需要出边贡献的是一段后缀,就可以做一个前后缀优化建图。
#include <bits/stdc++.h>
const long long inf = 1e18;
int main() {
#ifdef ONLINE_JUDGEstd::ios::sync_with_stdio(false);std::cin.tie(nullptr), std::cout.tie(nullptr);
#elsestd::freopen(".in", "r", stdin);std::freopen(".out", "w", stdout);const auto stime = std::chrono::steady_clock::now();
#endifint n, m;std::cin >> n >> m;struct edge { int v, w, id, pi, si; };std::vector<std::vector<edge> > g1(n + 2);std::vector<std::vector<std::pair<int, int> > > g(1);int cnt = 0;for (int x, y, w; m--; ) {std::cin >> x >> y >> w;g1[x].push_back({ y, w, ++cnt, 0, 0 });g1[y].push_back({ x, w, ++cnt, 0, 0 });g.emplace_back(), g.emplace_back();}int s = ++cnt, t = ++cnt;g1[0].push_back({ 1, 0, s, 0, 0 }), g1[n].push_back({ n + 1, 0, t, 0, 0 });g.emplace_back(), g.emplace_back();for (int i = 0; i <= n + 1; ++i)if (!g1[i].empty()) {std::sort(g1[i].begin(), g1[i].end(), [&](edge &x, edge &y) { return x.w < y.w; });for (int j = 0; j < (int)g1[i].size(); ++j) {g1[i][j].pi = ++cnt, g.emplace_back();if (j != 0)g[cnt].emplace_back(cnt - 1, 0);g[cnt].emplace_back(g1[i][j].id, 0);}for (int j = (int)g1[i].size() - 1; ~j; --j) {g1[i][j].si = ++cnt, g.emplace_back();if (j != (int)g1[i].size() - 1)g[cnt].emplace_back(cnt - 1, 0);g[cnt].emplace_back(g1[i][j].id, g1[i][j].w);}}for (int i = 0; i <= n + 1; ++i)for (auto &[v, w, id, pi, si] : g1[i]) {auto to = std::upper_bound(g1[v].begin(), g1[v].end(), w, [&](int x, edge &y) { return x < y.w; });if (to != g1[v].end())g[id].emplace_back(to->si, 0);if (to != g1[v].begin())g[id].emplace_back((--to)->pi, w);}std::vector<int> vis(cnt + 1, 0);std::vector<long long> dis(cnt + 1, inf);std::priority_queue<std::pair<long long, int> > q;dis[s] = 0, q.emplace(0, s);for (; !q.empty(); ) {int f = q.top().second;q.pop();if (vis[f])continue;vis[f] = 1;for (auto [v, w] : g[f])if (dis[v] > dis[f] + w) {dis[v] = dis[f] + w;q.emplace(-dis[v], v);}}std::cout << dis[t] << '\n';
#ifndef ONLINE_JUDGEstd::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endifreturn 0;
}
D - Travelling Through the Snow Queen's Kingdom
https://www.luogu.com.cn/problem/CF685E
目前见过的数据范围提示性极弱(误导性极强)的循环结构题:
- [BZOJ3620] 似乎在梦中见过的样子
- 字符合并
- [ARC205E] Subset Product Problem
正赛因为有部分分,应该不会出现不敢写的问题
-
考虑离线询问,逆序加边;原文无边权;边的通行时刻只决定到达点的时刻。
-
借鉴 merchant 中的思路,只需要更新当前边两侧点为起点的 DP 数组。
需要注意边从某种意义上说是『有向』的。
#include <bits/stdc++.h>
const int inf = 0x3f3f3f3f;
int main() {
#ifdef ONLINE_JUDGEstd::ios::sync_with_stdio(false);std::cin.tie(nullptr), std::cout.tie(nullptr);
#elsestd::freopen(".in", "r", stdin);std::freopen(".out", "w", stdout);const auto stime = std::chrono::steady_clock::now();
#endifint n, m, q;std::cin >> n >> m >> q;struct query { int r, s, t, id; };std::vector<int> res(q + 1);std::vector<std::vector<query> > u(m + 1);std::vector<std::pair<int, int> > e(m + 1);for (int i = 1; i <= m; ++i)std::cin >> e[i].first >> e[i].second;for (int i = 1, l, r, s, t; i <= q; ++i) {std::cin >> l >> r >> s >> t;u[l].push_back({ r, s, t, i });}std::vector<std::vector<int> > g(n + 1, std::vector<int> (n + 1, inf));for (int i = m; i; --i) {auto [x, y] = e[i];g[x][y] = g[y][x] = i;for (int j = 1; j <= n; ++j)g[x][j] = g[y][j] = std::min(g[x][j], g[y][j]);for (auto [r, s, t, id] : u[i])if (g[s][t] <= r)res[id] = 1;}for (int i = 1; i <= q; ++i)std::cout << (res[i] ? "Yes" : "No") << '\n';
#ifndef ONLINE_JUDGEstd::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endifreturn 0;
}
E - Culture Code
https://www.luogu.com.cn/problem/CF1197E
-
先按 \(out\) 排序,做一个前缀优化建图。
-
容易发现除了最外层,每一个套娃都会提供 \(in_i-out_i\) 的代价,而最外层会提供 \(in_x\) 的代价。
好在要求的是最长路,这样就可以 Dij 了,并不需要真正把图建出来,发现这个形式更序列,直接在序列上二分前缀 + DP 即可。 -
求方案是容易的。最后统计 DP 值最大,且不能被其他套娃包含的元素即可。
Tip:在求解过程中并不用考虑当前元素和前缀 min 元素间能否加入其他套娃,因为保证 \(out>in\),如果存在这样的套娃,其 DP 值会比前缀 min 更小,矛盾。
#include <bits/stdc++.h>
const int mod = 1e9 + 7;
int main() {
#ifdef ONLINE_JUDGEstd::ios::sync_with_stdio(false);std::cin.tie(nullptr), std::cout.tie(nullptr);
#elsestd::freopen(".in", "r", stdin);std::freopen(".out", "w", stdout);const auto stime = std::chrono::steady_clock::now();
#endifint n;std::cin >> n;std::vector<std::pair<int, int> > a(n + 1);int mxi = 0;for (int i = 1; i <= n; ++i) {std::cin >> a[i].first >> a[i].second;mxi = std::max(mxi, a[i].second);}std::sort(a.begin() + 1, a.end());std::vector<long long> g(n + 1), mxg(n + 1), f(n + 1), mx(n + 1);for (int i = 1; i <= n; ++i) {int j = std::upper_bound(a.begin() + 1, a.begin() + i, std::make_pair(a[i].second, 0x3f3f3f3f)) - a.begin() - 1;if (j == 0)f[i] = a[i].second, g[i] = 1ll;elsef[i] = mx[j] + a[i].second, g[i] = mxg[j];long long now = f[i] - a[i].first;if (now < mx[i - 1])mx[i] = now, mxg[i] = g[i];else if (now == mx[i - 1])mx[i] = now, mxg[i] = (mxg[i - 1] + g[i]) % mod;elsemx[i] = mx[i - 1], mxg[i] = mxg[i - 1];}auto now = 0x3f3f3f3fll, res = 0ll;for (int i = 1; i <= n; ++i) {if (a[i].first <= mxi)continue;if (f[i] < now)now = f[i], res = g[i];else if (f[i] == now)(res += g[i]) %= mod;}std::cout << res << '\n';
#ifndef ONLINE_JUDGEstd::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endifreturn 0;
}
A - Awesome Arrowland Adventure
https://www.luogu.com.cn/problem/P6233
- 没什么好说的建图,注意只能顺时针转
- 代码略
B - 地铁线路
https://www.luogu.com.cn/problem/P6096
-
考虑做一个神秘拆点,把每个点附上线路和运行方向的信息(所以是单向的)
-
认为路径代价是二元组,那么同条线路中的点通行代价为 \((0,-1)\)
-
换乘需要优化建图,每个点可以花 \((0,0)\) 的代价走到这个点的『换乘点』,再花 \((1,0)\) 的代价走到另一个分点
-
但 15 年的时候 SPFA 已经死了,所以需要好好考虑怎么实现最短路。
分两问是有提示性在的,可以想到 01 BFS 解决第一个关键字,比较对的想法是把所有最短路拿出来形成 DAG,在 DAG 上对第二关键字 DP。
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGEstd::ios::sync_with_stdio(false);std::cin.tie(nullptr), std::cout.tie(nullptr);
#elsestd::freopen(".in", "r", stdin);std::freopen(".out", "w", stdout);const auto stime = std::chrono::steady_clock::now();
#endifint n, m;std::cin >> m >> n;std::unordered_map<std::string, int> tab;std::vector<std::vector<int> > l(n + 1);std::vector<std::vector<std::tuple<int, int, int> > > g0(n + 1), g1(n + 1);for (int i = 1; i <= n; ++i) {std::string s;std::cin >> s, tab[s] = i;}int tot = n;for (int i = 1, k; i <= m; ++i) {std::cin >> k;int lp = 0, lq = 0;for (std::string s; k--; ) {std::cin >> s;int p = ++tot, q = ++tot, id = tab[s];g0.emplace_back(), g0.emplace_back();g1.emplace_back(), g1.emplace_back();if (lp) {g0[p].emplace_back(lp, 0, 1), g0[lq].emplace_back(q, 0, 1);g1[lp].emplace_back(p, 0, 1), g1[q].emplace_back(lq, 0, 1);}g0[p].emplace_back(id, 0, 0), g0[id].emplace_back(p, 1, 0);g1[id].emplace_back(p, 0, 0), g1[p].emplace_back(id, 1, 0);g0[q].emplace_back(id, 0, 0), g0[id].emplace_back(q, 1, 0);g1[id].emplace_back(q, 0, 0), g1[q].emplace_back(id, 1, 0);l[id].push_back(p), l[id].push_back(q);lp = p, lq = q;}}int s, t;{std::string s1, s2;std::cin >> s1 >> s2;s = ++tot, t = tab[s2];g0.emplace_back(), g1.emplace_back();int p = tab[s1];for (auto i : l[p])g0[s].emplace_back(i, 1, 0), g1[i].emplace_back(s, 1, 0);}std::vector<int> dis0(tot + 1, 0x3f3f3f3f), dis1(tot + 1, 0x3f3f3f3f);auto BFS = [&](decltype(g0) &g, decltype(dis0) &dis, int s) {std::deque<int> q;std::vector<int> vis(tot + 1);q.push_back(s), dis[s] = 0;for (; !q.empty(); ) {int x = q.front();q.pop_front();if (vis[x])continue;vis[x] = 1;for (auto [v, w1, w2] : g[x])if (dis[x] + w1 < dis[v]) {dis[v] = dis[x] + w1;if (w1 == 0)q.push_front(v);elseq.push_back(v);}}return;};BFS(g0, dis0, s), BFS(g1, dis1, t);std::cout << dis0[t] << '\n';std::vector<int> deg(tot + 1);std::vector<std::vector<std::pair<int, int> > > g(tot + 1);for (int i = 1; i <= tot; ++i)for (auto [j, w1, w2] : g0[i])if (dis0[i] + dis1[j] + w1 == dis0[t])g[i].emplace_back(j, w2), ++deg[j];std::queue<int> q;for (int i = 1; i <= tot; ++i)if (!deg[i])q.push(i);std::vector<int> f(tot + 1);for (; !q.empty(); ) {int x = q.front();q.pop();for (auto [v, w] : g[x]) {f[v] = std::max(f[v], f[x] + w);if (!--deg[v])q.push(v);}}std::cout << f[t] << '\n';
#ifndef ONLINE_JUDGEstd::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endifreturn 0;
}
C - Droga do domu
https://www.luogu.com.cn/problem/P9402
- 还是做一个和上一题类似的优化建图
- 此外就是一个普通的 Dij 上 DP 了。图没有环,直接拓扑即可。
- 可以滚动优化空间,但似乎并无必要。代码略。
D - Tickets P
https://www.luogu.com.cn/problem/P7984
-
没什么好说的线段树优化建图,难点在于如何同时获取 \(1\) 和 \(N\) 的信息
-
发现从某个点走到 \(1\) 和 \(N\),有一种不劣的走法:
-
维护一下每个点单独走到 \(1\),\(N\) 的最小代价和同时走到 \(1,N\) 的最小代价
看到一种更加对的写法是令 \(f_u\) 表示 \(v\) 的答案,那么可以用 \(f_v+w(u,v)\) 更新 \(f_u\)。
-
那么可以从 \(1,N\) 出发做一个 Dij。代码略。
E - 监狱
https://www.luogu.com.cn/problem/P9520
-
注意要走简单路径,也就是说不存在绕路让道的可能性。容易推出:若输入合法,总能找到一种方式使得每个人受到的指令是连续给出的。
P.S. 这个结论挪到图上就不成立了,很容易举出反例。
-
若一个人的起点 / 终点在另一个人的路径上,那么这两个人之间存在先后关系。建图后检查是否为 DAG 即可。
-
但建图显然是比较困难的,容易构造出数据使得边数来到 \(n^2\) 级别。考虑优化建图。
发现可以用一个树剖 / 倍增的结构来建图。
Tips:这一点同样是一个树上路径问题。参见 树上问题,倍增和树剖的选择?
-
这里的路径要求两端都是开的,这就导致倍增写着很困难(虽然树剖可能也是),不排除我写丑了
#include <bits/stdc++.h>
const int K = 19;
int main() {
#ifdef ONLINE_JUDGEstd::ios::sync_with_stdio(false);std::cin.tie(nullptr), std::cout.tie(nullptr);
#elsestd::freopen("01-02.in", "r", stdin);std::freopen(".out", "w", stdout);const auto stime = std::chrono::steady_clock::now();
#endifint T;for (std::cin >> T; T--; ) {int n, m;std::cin >> n;std::vector<std::vector<int> > g1(n + 1);std::vector<int> s(n + 1), t(n + 1);for (int i = 1, x, y; i < n; ++i) {std::cin >> x >> y;g1[x].push_back(y), g1[y].push_back(x);}std::cin >> m;std::vector<std::vector<int> > g(m + 1);std::vector<std::pair<int, int> > a(m + 1);for (int i = 1; i <= m; ++i) {std::cin >> a[i].first >> a[i].second;s[a[i].first] = i;t[a[i].second] = i;}int cnt = m;struct node { int fa, i0, i1; };std::vector<std::array<node, K + 1> > p(n + 1);std::vector<int> i0(n + 1), i1(n + 1), dep(n + 1), deg(m + 1);auto init = [&](void) {g.emplace_back(), deg.emplace_back();return ++cnt;};auto add = [&](int x, int y) {g[x].push_back(y), ++deg[y];return;};for (int i = 1; i <= n; ++i)i0[i] = init(), i1[i] = init();std::function<void(int, int)> DFS = [&](int x, int fa) {if (s[x])add(s[x], i1[x]);if (t[x])add(i0[x], t[x]);for (auto i : g1[x])if (i != fa) {dep[i] = dep[x] + 1;p[i][0].fa = x;p[i][0].i0 = init(), p[i][0].i1 = init();add(p[i][0].i0, i0[i]), add(i1[i], p[i][0].i1);for (int j = 1; j <= K; ++j) {p[i][j].fa = p[p[i][j - 1].fa][j - 1].fa;if (!p[i][j].fa)break;p[i][j].i0 = init(), p[i][j].i1 = init();add(p[i][j].i0, p[i][j - 1].i0);add(p[i][j].i0, p[p[i][j - 1].fa][j - 1].i0);add(p[i][j - 1].i1, p[i][j].i1);add(p[p[i][j - 1].fa][j - 1].i1, p[i][j].i1);}DFS(i, x);}return;};dep[1] = 1, DFS(1, -1);for (int i = 1; i <= m; ++i) {auto [x, y] = a[i];if (x == y)continue;if (t[x])add(i, t[x]);if (s[y])add(s[y], i);if (dep[x] < dep[y])std::swap(x, y);x = p[x][0].fa;if (dep[x] >= dep[y]) {for (int j = K; ~j; --j)if (dep[p[x][j].fa] >= dep[y]) {add(i, p[x][j].i0), add(p[x][j].i1, i);x = p[x][j].fa;}if (x == y)continue;add(i, p[x][0].i0), add(p[x][0].i1, i);x = p[x][0].fa;}y = p[y][0].fa;if (x != y) {for (int j = K; ~j; --j)if (p[x][j].fa != p[y][j].fa) {add(i, p[x][j].i0), add(i, p[y][j].i0);add(p[x][j].i1, i), add(p[y][j].i1, i);x = p[x][j].fa, y = p[y][j].fa;}add(i, p[x][0].i0), add(i, p[y][0].i0);add(p[x][0].i1, i), add(p[y][0].i1, i);x = p[x][0].fa;}add(i, i0[x]), add(i1[x], i);}std::queue<int> q;for (int i = 1; i <= cnt; ++i)if (!deg[i])q.push(i);int tot = 0;for (; !q.empty(); ) {int x = q.front();q.pop(), ++tot;for (auto i : g[x])if (!--deg[i])q.push(i);}std::cout << (tot == cnt ? "Yes" : "No") << '\n';}
#ifndef ONLINE_JUDGEstd::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endifreturn 0;
}