杂题1
更好的阅读体验
记录一些做到的自我感觉的好题。
P9350 [JOI 2023 Final] 宣传 2
左边有绝对值右边没有显然不是很好看，考虑拆绝对值。
那么相当于要同时满足 \(X_i - X_j \leq E_i - E_j\) 和 \(X_j - X_i <= E_i - E_j\)
移项就是 \(E_j - X_j <= E_i - X_i \ \wedge \ E_j + X_j \leq E_i + X_i\)
令 \(x_i = E_i - X_i\)，\(y_i = E_i + X_i\)，则可以再坐标轴上画出点，它能取到的就是它左下角的点。
问题转化成了选择最小的点覆盖所有的点，那么我们显然是选择随着 \(x\) 增加 \(y\) 下降的点，否则就可以将内层的点删掉。
直接按 \(y\) 从大到小排序后循环查找一遍即可。
const int N = 500010;
int n;
struct Node {
LL x, y;
} q[N];
int main() {
n = read();
for (int i = 1; i <= n; i ++) {
LL x = read(), e = read();
q[i].x = e - x, q[i].y = e + x;
}
sort(q + 1, q + 1 + n, [&](Node a, Node b) {
return a.y > b.y || a.y == b.y && a.x > b.x;
});
LL ans = 0, maxv = -2e9;
for (int i = 1; i <= n; i ++)
if (q[i].x > maxv) ans ++, maxv = q[i].x;
printf("%lld\n", ans);
return 0;
}
P9525 [JOISC 2022] 团队竞技
题目意思是要选择三个三元组 \((a, b, c)\) 使得每个三元组中都有一个元素严格大于其它两对的对应元素。
做法是将所有 \(a\), \(b\), \(c\)，分别加入三个大根堆中，并且记录下标。然后循环取出三个堆的堆顶，如果三个属于不同的三元组，那就是答案；否则如果有两个或三个数属于同一个三元组它就一定不可能是答案，直接将该三元组的所有元素从堆里踢出就可以了。
由于我们每次会删掉一个三元组，所以总的复杂度是 \(O(nlogn)\)。
如果最后都删完了也没有答案就说明无解。
const int N = 150010;
int n, x[N], y[N], z[N];
priority_queue<PII> A, B, C;
bool vis[N];
int main() {
n = read();
for (int i = 1; i <= n; i ++) {
x[i] = read(), y[i] = read(), z[i] = read();
A.push({x[i], i}); B.push({y[i], i}); C.push({z[i], i});
}
for (int i = 1; i <= n; i ++) {
auto a = A.top().second, b = B.top().second, c = C.top().second;
if (y[a] == y[b] || z[a] == z[c]) vis[a] = true;
if (x[b] == x[a] || z[b] == z[c]) vis[b] = true;
if (x[c] == x[a] || y[c] == y[b]) vis[c] = true;
if (!vis[a] && !vis[b] && !vis[c]) {
printf("%lld\n", (LL)x[a] + y[b] + z[c]);
return 0;
}
while (A.size() && vis[A.top().second]) A.pop();
while (B.size() && vis[B.top().second]) B.pop();
while (C.size() && vis[C.top().second]) C.pop();
}
puts("-1");
return 0;
}
P8162 [JOI 2022 Final] 让我们赢得选举
考虑很明显的贪心。
首先所有的人不可能分散，同一时刻必定在同一个州演讲拿下更多的人和票。其次在一个州的演讲时间只可能是 \(a_i, b_i, 0\)，否则都是浪费时间。
所以一个州就有三种情况，一种是不支持，一种是得票，一种是得票加得人。
由于每个州的人质量都一样的好，所以我们找人肯定先找 \(b_i\) 小的，所以我们按照 \(b\) 进行排序。
接着考虑 \(DP\)，令 \(F_{i, j, k}\) 表示在前 \(i\) 个州中有 \(j\) 个州得票，\(k\) 个州得票加得人，这样做是 \(O(n ^ 4)\) 的，可以得到 \(66\) 分。
如何优化呢？我们考虑继续贪心，可以发现一定存在一个分界点使得前半部分都是得票或者得票加得人，后半部分都是不支持的。
简单证明一下。假设最后一个票+人后倒数第二个票+人之间存在不支持，那么把最后一个票+人的州往前移一定更优。以此类推两个票+人之间一定全是票。
所以我们可以简化 \(DP\) 状态为 \(F_{i, j}\) 表示前 \(i\) 个州有 \(j\) 个州是票+人，然后总复杂度就变成 \(O(n^3)\) 的就可以卡过了。
具体实现我们可以枚举票+人州的上界，然后直接 \(DP\) 即可。
注意由于所有拿人的州一定比只拿票的州先演讲，所以在算一个州只拿票的时候人数为上界加一。
const int N = 510;
int n, k, a[N];
PII q[N];
double f[N][N];
double work(int B) {
for (int i = 1; i <= n; i ++) a[i] = q[i].first;
for (int i = 0; i <= n; i ++)
for (int j = 0; j <= n; j ++)
f[i][j] = 1e18;
f[0][0] = 0;
for (int i = 1; i <= n; i ++) {
for (int j = 0; j <= min(B, i); j ++) {
f[i][j] = f[i - 1][j] + q[i].first * 1.0 / (B + 1);
if (j && q[i].second != INF) f[i][j] = min(f[i][j], f[i - 1][j - 1] + q[i].second * 1.0 / j);
}
}
double res = 1e18;
for (int i = k; i <= n; i ++) res = min(res, f[i][B]);
for (int i = k; i >= B; i--) {
sort(a + 1 + i, a + 1 + n);
double sum = 0;
for (int j = i + 1; j <= k; j ++) sum += a[j];
res = min(res, f[i][B] + sum / (B + 1));
}
return res;
}
int main() {
n = read(), k = read();
for (int i = 1; i <= n; i ++) {
q[i] = {read(), read()};
if (q[i].second == -1) q[i].second = INF;
}
sort(q + 1, q + 1 + n, [&](PII a, PII b) {
return a.second < b.second;
});
double ans = 1e18;
for (int i = 0; i <= k; i ++) ans = min(ans, work(i));
printf("%.10lf\n", ans);
return 0;
}
P9352 [JOI 2023 Final] 训猫
首先我们发现如果按照题目中所给方式建一棵树，则如果猫在 \(u\)，那么当它跳向某一个子树中的结点时（即猫 \(u\) 被砸跑了），\(u\) 的其它子树的结点就不能跳了。
所以我们考虑树形 \(DP\)，令 \(F_u\) 表示猫在以 \(u\) 为根的子树中最多跳多少下。令 \(v\) 为 \(u\) 子树中满足 \(P_u > P_v\) 的 \(P\) 最大的结点。
则 \(F_u = \max(F_u, F_v + dist(u, v))\)，其中 \(dist(u, v)\) 为 \(u, v\) 在树上的距离，可以通过 \(lca\) 解决。
写出 \(DP\) 后稍加思索会发现，这个 \(DP\) 顺序是乱套的，可能从 \(i \to j \to k\)，但是 \(k\) 在 \(i, j\) 之间，如果按照原方式建图就炸了。
但我们其实只要在建图的时候不要 \((u, v)\) 而是 \((P_u, P_v)\) 即可，然后按照 \(u\) 从 \(1 \to n\) 的顺序 \(DP\)，并用并查集维护一下 \(v\) 即可。
代码太长就不放了，可以去云剪贴板查看。
P11674 [USACO25JAN] Reachable Pairs G
考虑正着做比较困难，所以正难则反。我们考虑按照 \(t\) 从大到小执行 \(S\) 中的操作。
对于操作 \(0\)，相当于删掉所有与 \(u\) 相连的边，反着来就是用 \(u\) 连接当前所有的边；对于操作 \(1\)，我们发现它并不会改变图上的连通性，相当于让点 \(u\) 变为了一个虚点，反着做相当于给联通块加一个点。
具体来说我们用并查集维护，最开始现将所有虚点之间的连边添加进并查集中。
const int N = 200010, M = 400010;
int n, m;
int fa[N];
LL res, ans[N], sz[N];
char s[N];
vector<int> g[N];
int find(int x) {
if (fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
void merge(int a, int b) {
a = find(a), b = find(b);
if (a == b) return;
fa[b] = a;
res -= sz[a] * (sz[a] - 1) / 2, res -= sz[b] * (sz[b] - 1) / 2;
sz[a] += sz[b], res += sz[a] * (sz[a] - 1) / 2;
}
int main() {
n = read(), m = read();
rep(i, 1, n) fa[i] = i;
scanf("%s", s + 1);
while (m --) {
int a = read(), b = read();
g[a].push_back(b); g[b].push_back(a);
if (s[a] == '1' && s[b] == '1') merge(a, b);
}
for (int u = n; u; u --) {
if (s[u] == '0') {
for (auto v : g[u])
if (v > u || s[v] == '1') merge(v, u);
}
int v = find(u); res += sz[v] ++;
ans[u] = res;
}
for (int i = 1; i <= n; i ++) printf("%lld\n", ans[i]);
return 0;
}
P11676 [USACO25JAN] DFS Order P
考虑 DFS 序的性质，一棵子树的 DFS 序一定是连续的一段，并且可以发现 \(N \leq 750\)，所以考虑区间 DP。
先考虑初始没有边怎么做，显然我们应该搞一棵树。
令 \(f_{i, j}\) 表示以 \(i\) 为根的子树在 DFS 序中结尾为 \(j\) 的最小代价。转移就是 \(f_{i, j} = f_{i, k} + f_{k + 1, j} + a_{i, k + 1}\)。
对于初始有边的情况，我们可以考虑直接把原来的边全部删除。由于最后的图里一定不包含横叉边，但是会有返祖边。而如果原图中有返祖边那我们就不应该删去增大代价，所以我们只要在 DP 的时候把原先删除过的返祖边加回来即可。
具体来说考虑子树 \([i, k]\) 和 \([k + 1, j]\)，如果要把 \([k + 1, j]\) 塞进 \([i, k]\) 那么增加的返祖边一定是 \((l, k + 1), (l, k + 2), ..., (l, j)\)。而我们只需要其中代价为负数的边，所以前缀和处理一下即可。
const int N = 810;
int n, a[N][N], s[N][N];
int f[N][N], cost;
int main() {
n = read();
rep(j, 2, n) rep(i, 1, j - 1) a[i][j] = read(), cost += (a[i][j] < 0 ? -a[i][j] : 0);
rep(i, 1, n) rep(j, 1, n) s[i][j] = s[i][j - 1] + (a[i][j] < 0 ? a[i][j] : 0);
rep(i, 1, n) f[i][i] = 0;
rep(len, 2, n) {
for (int i = 1; i + len - 1 <= n; i ++) {
int j = i + len - 1; f[i][j] = INF;
rep(k, i, j - 1) f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + s[i][j] - s[i][k + 1] + a[i][k + 1]);
}
}
printf("%d\n", f[1][n] + cost);
return 0;
}
AGC018F Two Trees
一个显然的性质是树上的点一定存在构造方式使得点权只取到 \([-1, 1]\)，这是显然的，因为最后每个子树的权值和只能为 \(-1\) 和 \(1\)。
然后我们先考虑无解的情况，因为对于一个结点它在两棵树上的子树和都要是 \(-1\) 或 \(1\)，而 \(-1 \equiv 1 \pmod 2\)，所以对于一个结点它的子树大小在两棵树上儿子数量奇偶性一定要相同，否则无解。
既然已经出现了奇偶性，所以我们考虑用一种方式将它们的奇偶性转化一下。对于本题，我们可以考虑构造一个图然后跑欧拉回路。
具体的构造方式是，对于度数为偶数的点，我们令它的权值为 \(0\)，度数为奇数的点，我们把它两棵树上的对应结点连一条横叉边。对于一条横叉边，如果它在欧拉回路上的方向是从第一棵树到第二棵树，则连接它的两个点的权值为 \(1\)，否则为 \(-1\)。
证明我们可以考虑对于欧拉回路拆成若干个环，对于每个环的贡献分类讨论：
- 从结点 \(u\) 向它的儿子走最后通过其它儿子或是横叉边回到 \(u\)。
- 从结点 \(u\) 向它的儿子走最后通过 \(u\) 的父亲回到 \(u\)。
- 从结点 \(u\) 向它的父亲走最后通过横叉边回到 \(u\)，或是从横叉边走从父亲回到 \(u\)。
对于第一类，我们画图可以发现，由于该环一定经历了相反方向的横叉边（因为要从树一到树二再回到树一）和偶数点，所以它的贡献会全部抵消。对于第二类和第三类，继续画图会发现它们的贡献一定是 \(-1\) 或是 \(1\)。因为从 \(u\) 的父亲走到 \(u\) 的这条边只会经过一次，所以第二类和第三类的环总共只会出现一次，这样就可以保证贡献和为 \(1\) 或 \(-1\)。
最后再考虑对于两棵树的根节点，我们要创建一个超级根连接两个根，可以直接再开辟一个节点，你也可以直接把两棵树的根节点连边，这是等价的。
const int N = 800010;
int n;
vector<int> g[N];
int rt1, rt2, cnt;
int ans[N], degs1[N], degs2[N], nx[N], ny[N], types[N];
bool st[N];
void add(int a, int b, int type) {
g[a].push_back(++ cnt); g[b].push_back(cnt);
nx[cnt] = a, ny[cnt] = b;
types[cnt] = type;
}
void dfs(int u) {
while (g[u].size()) {
int i = g[u].back(); g[u].pop_back();
if (st[i]) continue;
st[i] = true;
int v = nx[i] ^ ny[i] ^ u;
if (types[i] == 1) ans[min(u, v)] = u < v ? 1 : -1;
dfs(v);
}
}
int main() {
n = read();
for (int i = 1; i <= n; i ++) {
int x = read();
if (x == -1) rt1 = i;
else {
add(x, i, 0);
degs1[i] ++, degs1[x] ++;
}
}
for (int i = 1; i <= n; i ++) {
int x = read();
if (x == -1) rt2 = i;
else {
add(x + n, i + n, 0);
degs2[i] ++, degs2[x] ++;
}
}
degs1[rt1] ++, degs2[rt2] ++; add(rt1, rt2 + n, 0);
for (int i = 1; i <= n; i ++)
if (degs1[i] % 2 != degs2[i] % 2) {
puts("IMPOSSIBLE");
return 0;
}
for (int i = 1; i <= n; i ++)
if (degs1[i] & 1)
add(i, i + n, 1);
dfs(1);
puts("POSSIBLE");
printf("%d", ans[1]);
for (int i = 2; i <= n; i ++) printf(" %d", ans[i]);
puts("");
return 0;
}
P11727 [JOIG 2025] 神経衰弱 2 / Pair Matching 2
根据题目的左右手机制，可以发现只有两种策略可以拿到 \(x\) 的贡献，即 \(xx\) 和 \(xyxy\)，并且一张牌如果拿到了手上就一定要的到贡献，不然你拿这张牌肯定不优。
考虑线性 DP，令 \(pre_i\) 表示 \(i\) 第一次出现是在什么位置，\(f_{i, 0}\) 表示前 \(i\) 张牌中两张 \(A_i\) 连续取的最大得分，\(f_{i, 1}\) 则是不连续取。
那么显然有 \(f_{i, 0} = \underset{j \in [1, pre_i)}{\max} \{f_{j, 0/1} \} + V_{a_i}\)，即枚举 \(xx\) 前的部分的最大值加上 \(xx\) 的贡献。
对于 \(xyxy\) 的情况我们也可以同样地得出方程 \(f_{i, 1} = \underset{pre_j < pre_i}{\max} \{f_{j, 0} \} + V_{a_i}\)。注意这里由于 DP 的定义我们只考虑了 \(xyx\) 的情况，所以我们不能转移 \(f_{j, 1}\)，否则就会出现 \(xyxaba\) 之类的情况。
对于第一个式子因为 \(pre_i < i\)，所以我们维护一下前缀最大值，对于第二个式子我们直接用树状数组维护一下即可。
const int N = 800010;
int n, a[N], pre[N], p[N];
LL v[N], f[N][2], pm[N], tr[N];
void add(int x, LL k) {
for (; x <= n * 2; x += lowbit(x)) tr[x] = max(tr[x], k);
}
LL query(int x) {
LL res = 0;
for (; x; x -= lowbit(x)) res = max(res, tr[x]);
return res;
}
int main() {
n = read();
rep(i, 1, n * 2) a[i] = read();
rep(i, 1, n) v[i] = read();
rep(i, 1, n * 2)
if (p[a[i]]) pre[i] = p[a[i]];
else p[a[i]] = i;
rep(i, 1, n * 2)
if (!pre[i]) pm[i] = pm[i - 1];
else {
f[i][0] = pm[pre[i] - 1] + v[a[i]];
f[i][1] = query(pre[i] - 1) + v[a[i]];
add(pre[i], f[i][0]);
pm[i] = max(pm[i - 1], max(f[i][0], f[i][1]));
}
printf("%lld\n", pm[n * 2]);
return 0;
}
P1948 [USACO08JAN] Telephone Lines S
考虑一个 DP，令 \(f_{i, j}\) 表示从 \(1\) 到 \(i\)，\(j\) 条边免费，其中不免费的最大边的最小值。
那么 \(max(f_{i, j}, w_{i, k}) \to f_{k, j}\) 还有 \(f_{i, j} \to f_{k, j + 1}\)，其中 \(k\) 为 \(i\) 的邻点，前一种转移对应 \((i, k)\) 不免费，后一种对应免费。
但这实际上有后效性，因为图上可能有环。但我们可以运用迭代的思想，借助 SPFA 进行动态规划，直至不能再更新为止。从最短路问题出发理解，其实可以看成二维结点 \((i, j)\) 作为图上的结点的分层图上跑最短路，一共是 \(N\times K\) 个结点和 \(M\times K\) 个边。
最短路算法可以使用 SPFA 也可以堆优化 dijkstra，但是为了防止被卡还是后者好，毕竟这是一张正权图。
本题还有另一种方法，由于本题答案显然具有单调性，所以可以二分答案，问题就转化为判定是否存在合法的方案。假设当前二分到了 \(mid\)，我们考虑将所有边权大于 \(mid\) 的边权置为 \(1\)，小于等于的置为 \(0\)，由于大于的一定要免费，所以我们可以求出最短路看看是否小于 \(K\)。对于这种 \(0,1\) 类型的最短路可以通过双端队列 BFS 解决。代码我没有写过。
const int N = 1010, M = 20010;
int n, m, k;
int h[N], e[M], ne[M], w[M], idx;
int d[N][N];
bool vis[N][N];
priority_queue<pair<int, PII> > q;
void add(int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
void dijkstra(int st) {
memset(d, 0x7f, sizeof d); d[st][0] = 0;
q.push({0, {st, 0}});
while (q.size()) {
int i = q.top().second.first, j = q.top().second.second;
q.pop();
if (vis[i][j]) continue;
vis[i][j] = true;
for (int _ = h[i]; ~_; _ = ne[_]) {
int y = e[_], z = w[_];
if (d[y][j] > max(d[i][j], z)) {
d[y][j] = max(d[i][j], z);
q.push(make_pair(-d[y][j], make_pair(y, j)));
}
if (j < k && d[y][j + 1] > d[i][j]) {
d[y][j + 1] = d[i][j];
q.push(make_pair(-d[y][j+1], make_pair(y, j+1)));
}
}
}
}
int main() {
n = read(), m = read(), k = read();
memset(h, -1, sizeof h);
while (m --) {
int a = read(), b = read(), c = read();
add(a, b, c); add(b, a, c);
}
dijkstra(1);
int ans = 0x7f7f7f7f;
for (int i = 0; i <= k; i ++) ans = min(ans, d[n][i]);
printf("%d\n", ans == 0x7f7f7f7f ? -1 : ans);
return 0;
}
[NOIP 2009 提高组] 最优贸易
考虑题意要求一条从 \(1\) 到 \(n\) 的路径使得路径上有两个点 \(p\) 和 \(q\)，满足 \(p < q\) 且使得 \(c_q - c_p\) 最大。求这个最大值。
考虑枚举分界点 \(i\)，我们可以求出 \(1 \sim i\) 的最小值和 \(i \sim n\) 的最大值，两者相减。然后对于所有分界点枚举一遍即可。
那么如何求这些最小值和最大值呢？一种方法是直接 DP，但可能有环，所以考虑缩点。另一种方式是建一张反图，然后分别在原图从 \(1\) 开始，反图从 \(n\) 开始做就可以了。计算过程中只要把 SPFA 中 d[x] + w(x, y) 更新 d[y] 改成 min(d[x], price[y]) 即可。注意本题不能使用 dijkstra，这和负权图其实是一个道理，即 dijkstra 中第一次访问某个点时不能的得到最短路，那么正确性就会出现问题，因为 dijkstra 的复杂度是通过只访问每个点一次来保证的。
代码写复杂了，其实可以通过对每个边设置类型少写一遍 spfa。
const int N = 100010;
int n, m, c[N];
vector<int> G1[N], G2[N];
int d1[N], d2[N];
bool vis[N];
void spfa() {
memset(d1, 0x3f, sizeof d1); memset(d2, -0x3f, sizeof d2);
queue<int> q; q.push(1); vis[1] = true, d1[1] = c[1];
while (q.size()) {
int u = q.front(); q.pop();
vis[u] = false;
for (auto v : G1[u])
if (d1[v] > min(d1[u], c[v])) {
d1[v] = min(d1[u], c[v]);
if (!vis[v]) vis[v] = true, q.push(v);
}
}
while (!q.empty()) q.pop();
memset(vis, false, sizeof vis);
q.push(n); vis[n] = true, d2[n] = c[n];
while (q.size()) {
int u = q.front(); q.pop();
vis[u] = false;
for (auto v : G2[u])
if (d2[v] < max(d2[u], c[v])) {
d2[v] = max(d2[u], c[v]);
if (!vis[v]) vis[v] = true, q.push(v);
}
}
}
int main() {
n = read(), m = read();
for (int i = 1; i <= n; i ++) c[i] = read();
while (m --) {
int a = read(), b = read(), op = read();
G1[a].push_back(b); G2[b].push_back(a);
if (op == 2) G1[b].push_back(a), G2[a].push_back(b);
}
spfa();
int ans = 0;
for (int i = 1; i <= n; i ++) ans = max(ans, d2[i] - d1[i]);
printf("%d\n", ans);
return 0;
}
P3008 [USACO11JAN] Roads and Planes G
考虑题目给出的是一张带有负权边的图，如果正常跑最短路只能 SPFA，但是会被卡掉。
然而我们发现题目给了一些很好的性质，概括一下就是有一堆边权为正的双向边，和一堆边权为负的单向边，而且保证一条单向边如果可以从 \(A\) 到 \(B\) 就一定不存在路径可以从 \(B\) 到 \(A\)。我们考虑把所有连通的双向边组成的连通块看作一个结点，整张图就变成了一张 DAG，就可以直接拓扑排序做。然后连通块内的点可以直接跑 dijkstra，复杂度就对了。
同时尽量不要使用所谓的 SLF 之类的优化 SPFA，它的复杂度没法保证，看 lyd 的课学到了通过一堆三角形来把 SLF 优化卡成指数级别。
const int N = 25010, M = 150010;
int n, m1, m2, s;
int h[N], e[M], ne[M], w[M], tp[M], idx;
int d[N], degs[N], c[N], cnt;
vector<int> a[N];
bool vis[N];
priority_queue<PII, vector<PII>, greater<PII> > heap;
queue<int> q;
void add(int a, int b, int c, int op) {
e[idx] = b, w[idx] = c, tp[idx] = op, ne[idx] = h[a], h[a] = idx ++;
}
void dfs(int u) {
c[u] = cnt;
a[cnt].push_back(u);
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (tp[i] == 1) continue;
if (!c[v]) dfs(v);
}
}
void dijkstra(int B) {
for (auto u : a[B]) heap.push({d[u], u});
while (heap.size()) {
int u = heap.top().second; heap.pop();
if (vis[u]) continue;
vis[u] = true;
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (tp[i] == 0) {
if (d[v] > d[u] + w[i]) {
d[v] = d[u] + w[i];
heap.push({d[v], v});
}
} else {
d[v] = min(d[v], d[u] + w[i]);
if (-- degs[c[v]] == 0) q.push(c[v]);
}
}
}
}
int main() {
n = read(), m1 = read(), m2 = read(), s = read();
memset(h, -1, sizeof h);
while (m1 --) {
int a = read(), b = read(), c = read();
add(a, b, c, 0);
add(b, a, c, 0);
}
while (m2 --) {
int a = read(), b = read(), c = read();
add(a, b, c, 1);
}
for (int i = 1; i <= n; i ++)
if (!c[i]) { cnt ++; dfs(i); }
for (int u = 1; u <= n; u ++)
for (int i = h[u]; ~i; i = ne[i])
if (tp[i] == 1) degs[c[e[i]]] ++;
for (int i = 1; i <= cnt; i ++)
if (!degs[i]) q.push(i);
memset(d, 0x3f, sizeof d);
d[s] = 0;
while (q.size()) {
int u = q.front(); q.pop();
dijkstra(u);
}
for (int i = 1; i <= n; i ++)
if (d[i] > n * 10000) puts("NO PATH");
else printf("%d\n", d[i]);
return 0;
}
P1347 排序
思路很板的一道题，考虑小于关系可以传递，所以相当于一个传递闭包。\(n\) 的范围也很小，所以直接 Floyd 维护传递闭包即可。
const int N = 35;
int n, m;
int d[N][N];
char s[N];
int floyd() {
rep(k, 0, n - 1) rep(i, 0, n - 1) rep(j, 0, n - 1) {
d[i][j] |= d[i][k] & d[k][j];
if (d[i][j] == d[j][i] && d[i][j] == 1 && i != j) return -1;
}
rep(i, 0, n - 1) rep(j, 0, n - 1)
if (d[i][j] == d[j][i] && d[i][j] == 0 && i != j) return 0;
return 1;
}
void solve() {
memset(d, 0, sizeof d);
bool flag = false;
rep(i, 1, m) {
scanf("%s", s);
if (s[0] == s[2]) {
printf("Inconsistency found after %d relations.\n", i);
flag = true;
}
if (flag) continue;
d[s[0] - 'A'][s[2] - 'A'] = 1;
int res = floyd();
if (res == -1) printf("Inconsistency found after %d relations.\n", i), flag = true;
else if (res == 1) {
printf("Sorted sequence determined after %d relations: ", i);
pair<int, char> ans[N];
rep(j, 0, n - 1) ans[j] = {0, j + 'A'};
rep(i, 0, n - 1) rep(j, 0, n - 1)
if (d[i][j]) ans[j].first ++;
sort(ans, ans + n);
rep(i, 0, n - 1) printf("%c", ans[i].second);
puts(".");
flag = true;
}
}
if (!flag) puts("Sorted sequence cannot be determined.");
}
int main() {
while (scanf("%d%d", &n, &m) == 2, n || m) solve();
return 0;
}
P10927 Sightseeing trip
这个题很巧妙，我们先来重申一下 Floyd 中 \(D_{i, j}\) 的定义，这也是很多人没有在意的。
即经过若干个编号不超过 \(k\) 的节点，从 \(i\) 到 \(j\) 的最短路，其中 \(k\) 就是阶段，所以要放在最外层循环。所以状态表示中本来是有三维的，只是省掉了一维。
对于本题，考虑在每次外层循环 \(k\) 新开始的时候 \(D\) 中是存了经过编号不超过 \(k - 1\) 的最短路的。显然，\(\underset{1 \leq i < j < k}{\min}\{ d_{i, j} + a_{j,k} + a_{k, i} \}\) 就是满足编号不超过 \(k\) 的结点组成且经过 \(k\) 的最小环长度，理由是 \(i\) 和 \(j\) 可以看做枚举了环上两个离 \(k\) 最近的点。
const int N = 110, M = 20010;
int n, m;
int d[N][N], a[N][N], p[N][N];
vector<int> path;
void get_path(int i, int j) {
if (!p[i][j]) return;
get_path(i, p[i][j]);
path.push_back(p[i][j]);
get_path(p[i][j], j);
}
int main() {
n = read(), m = read();
memset(a, 0x3f, sizeof a);
rep(i, 1, n) a[i][i] = 0;
rep(i, 1, m) {
int u = read(), v = read(), w = read();
a[u][v] = a[v][u] = min(a[u][v], w);
}
memcpy(d, a, sizeof a);
LL ans = INF;
rep(k, 1, n) {
rep(i, 1, k - 1) rep(j, i + 1, k - 1) {
if ((LL)d[i][j] + a[j][k] + a[k][i] < ans) {
ans = (LL)d[i][j] + a[j][k] + a[k][i];
path.clear();
path.push_back(i);
get_path(i, j);
path.push_back(j);
path.push_back(k);
}
}
rep(i, 1, n) rep(j, 1, n)
if (d[i][j] > d[i][k] + d[k][j])
d[i][j] = d[i][k] + d[k][j], p[i][j] = k;
}
if (ans == INF) puts("No solution.");
else {
for (auto u : path) printf("%d ", u);
puts("");
}
return 0;
}
P2886 [USACO07NOV] Cow Relays G
考虑边数只有 \(100\)，但点数很多，所以离散化一下点的编号。
首先考虑一个简单 DP，令 \(f_{i, j}\) 表示经过 \(i\) 条边从 \(s\) 到 \(i\) 的最短路。有转移 \(f_{i, j} + w \to f_{i + 1, k}\)，其中 \(k\) 为 \(j\) 的邻点。你会发现这其实就是 Bellman-Ford。直接做是 \(O(NT)\) 的，卡卡能过，但是太不优雅了。
我们考虑使用倍增优化。但上面的式子显然不是很好倍增优化，因为记录的是 \(s\) 到 \(j\)。我们考虑改变状态为 \(f_{i, x, y}\) 表示从 \(x\) 到 \(y\) 经过 \(2^i\) 条边的最短路，这就很好倍增了，枚举一下中转点 \(k\)，则有 \(f_{i, x, y} = \min\{f_{i - 1, x, k} + f_{i - 1, k, y} \}\)。这样做由于经过了离散化，所以是 \(O(T^3logN)\) 的。
我们再次观察一下转移式，这个东西其实可以看做一个广义“矩阵乘法”，即将求和看做取 min，相乘看做加。这么做显然满足结合律，所以我们可以直接跑矩阵快速幂。记 \(A^i\) 为经过任意两点经过 \(i\) 条边的最短路，只需要计算出 \(A^n\) 即可。时间复杂度依然是 \(O(T^3logN)\) 的。
const int N = 210;
int n, m, s, e, p;
int d[N][N], ans[N][N];
int a[N], b[N], c[N];
vector<int> alls;
int find(int x) {
return lower_bound(alls.begin(), alls.end(), x) - alls.begin() + 1;
}
void mul(int a[N][N], int b[N][N]) {
int c[N][N]; memset(c, 0x3f, sizeof c);
for (int i = 1; i <= p; i ++)
for (int j = 1; j <= p; j ++)
for (int k = 1; k <= p; k ++)
c[i][j] = min(c[i][j], a[i][k] + b[k][j]);
memcpy(a, c, sizeof c);
}
int main() {
n = read(), m = read(), s = read(), e = read();
rep(i, 1, m) {
c[i] = read(), a[i] = read(), b[i] = read();
alls.push_back(a[i]); alls.push_back(b[i]);
}
alls.push_back(s); alls.push_back(e);
sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());
p = alls.size();
memset(d, 0x3f, sizeof d);
rep(i, 1, m) {
a[i] = find(a[i]), b[i] = find(b[i]);
d[a[i]][b[i]] = d[b[i]][a[i]] = min(d[a[i]][b[i]], c[i]);
}
s = find(s), e = find(e);
memset(ans, 0x3f, sizeof ans); ans[s][s] = 0;
while (n) {
if (n & 1) mul(ans, d);
n >>= 1;
mul(d, d);
}
printf("%d\n", ans[s][e]);
return 0;
}
ABC395D Pigeon Swap
考虑维护 \(p_x\) 表示 \(x\) 现在被换到了哪个窝里，\(c_x\) 表示第 \(x\) 个窝里的鸟现在在哪里，\(f_x\) 表示第 \(x\) 个窝现在装着哪个窝的鸟。
const int N = 1000010, Q = 300010;
int n, q;
int p[N], c[N], f[N];
int main() {
n = read(), q = read();
rep(i, 1, n) p[i] = c[i] = f[i] = i;
while (q --) {
int op = read(), x = read(), y;
if (op == 1 || op == 2) y = read();
if (op == 1) p[x] = f[y];
else if (op == 2) swap(c[f[x]], c[f[y]]), swap(f[x], f[y]);
else printf("%d\n", c[p[x]]);
}
return 0;
}
ABC395E Flip Edge
与上面那个 P1948 非常类似，先列出 DP 式子，然后正反图分层跑最短路即可。
const int N = 200010, M = 400010;
int n, m, x;
int h[N], e[M], ne[M], mark[M], idx;
LL d[N][2], st[N][2];
void add(int a, int b, int tp) {
e[idx] = b, mark[idx] = tp, ne[idx] = h[a], h[a] = idx ++;
}
LL dijkstra() {
priority_queue<pair<LL, PII>> q;
q.push({0, {1, 0}});
memset(d, 0x3f, sizeof d); d[1][0] = 0;
while (q.size()) {
int u = q.top().second.first, p = q.top().second.second; q.pop();
if (st[u][p]) continue;
st[u][p] = true;
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (mark[i] == p) {
if (d[v][p] > d[u][p] + 1) {
d[v][p] = d[u][p] + 1;
q.push({-d[v][p], {v, p}});
}
} else {
if (d[v][p ^ 1] > d[u][p] + x + 1) {
d[v][p ^ 1] = d[u][p] + x + 1;
q.push({-d[v][p ^ 1], {v, p ^ 1}});
}
}
}
}
return min(d[n][0], d[n][1]);
}
int main() {
n = read(), m = read(), x = read();
memset(h, -1, sizeof h);
while (m --) {
int a = read(), b = read();
add(a, b, 0); add(b, a, 1);
}
LL res = dijkstra();
printf("%lld\n", res);
return 0;
}
ABC395F Smooth Occlusion
考虑题目给出的一个非常好的信息时每次刷牙只能减少 \(1\) 牙齿长度，不会增加。所以假设求出一个 \(H\)，那么你的代价就应该是 \(\sum(u_i + d_i) - n \times H\)，要让代价最小只要让 \(H\) 最大即可。考虑二分答案，那么 check 可以贪心。
考虑每个 \(u_i\)，维护一个 \(a_i\) 和 \(b_i\) 表示这颗牙齿的上限和下限，那么 \(a_i = \min(a_{i - 1} + X, u_i)\)，其中 \(X\) 是题目中给出的差值。注意牙齿只能变短，所以上限不能超出 \(u_i\)。同样地，有 \(b_i = \max(b_{i - 1} - X, H - d_i)\)，这里下限的 \(H - d_i\) 是因为要让 \(u_i\) 尽可能地小并且 \(d_i\) 无法增大，所以只能在 \(d_i\) 不做任何改变时取到 \(u_i\) 的最小值。
注意 long long。
const int N = 200010;
LL n, m, u[N], d[N];
bool check(LL x) {
LL a = u[1], b = x - d[1];
rep(i, 2, n) {
a = min(a + m, u[i]), b = max(b - m, x - d[i]);
if (a < b) return false;
}
return true;
}
int main() {
n = read(), m = read();
LL l = 0, r = 1e18, ans = 0;
rep(i, 1, n) u[i] = read(), d[i] = read(), r = min(r, u[i] + d[i]);
while (l <= r) {
LL mid = l + r >> 1;
if (check(mid)) l = mid + 1, ans = mid;
else r = mid - 1;
}
LL res = -n * ans;
rep(i, 1, n) res += u[i] + d[i];
printf("%lld\n", res);
return 0;
}
AGC052A Long Common Subsequence
考虑 \(n\) 个 \(0\) 和 \(n\) 个 \(1\) 再加一个 \(0\) 一定可以被构造出来。
假设在 \(S\) 中的 \(n\) 个 \(0\) 的位置分别是 \(p_1\), \(p_2\), \(...\), \(p_n\)，那么在 \(S + S\) 的第二个 \(S\) 中 \(0\) 的位置就是 \(p_1 + 2n, p_2 + 2n, ..., p_n + 2n\)，那么 \(p_n + 2n\) 与 \(p_n\) 中间一定存在 \(n\) 个 \(1\)，同时再取 \(p_n + 2n\) 这个 \(0\) 就可以满足上述构造方案。
int main() {
int T = read();
while (T --) {
int n; cin >> n;
string a, b, c; cin >> a >> b >> c;
rep(i, 1, n) cout << 0;
rep(i, 1, n) cout << 1;
cout << 0 << endl;
}
return 0;
}
P11159 【MX-X6-T5】 再生
首先根据树链剖分 \(top\) 的定义，所以给出 \(top\) 相等的点一定在一条链上，其中 \(top\) 等于本身的点就是链的最顶端。假设链的长度为 \(k\)，那链内部的排列方式就是 \((k - 1)!\)。
所以问题相当于现在有很多个链，我们只需要考虑链和链的连接。容易发现对于两条长分别为 \(x,y\ (x > y)\) 的链，一定是 \(y\) 挂在 \(x\) 上。同时为了保证重链一定是 \(x\) 对应的链，那么 \(y\) 就不能挂在链 \(x\) 深度在 \(x - y\) 以下的结点上，所以 \(y\) 挂 \(x\) 的方案为 \((x - y) !\)。
那么我们可以按照链的长度排序，设有 \(m\) 个链，\(h_i\) 为链 \(i\) 的长度，答案就应该是：
不难发现可以预处理阶乘，同时前缀和优化掉内部的求和。
const int N = 500010, Mod = 20051131;
LL n, top[N], h[N], s[N], fac[N];
int main() {
n = read();
rep(i, 1, n) top[i] = read();
rep(i, 1, n) h[top[i]] ++;
sort(h + 1, h + 1 + n, [&](LL a, LL b) {
return a > b;
});
fac[0] = 1;
rep(i, 1, n) fac[i] = fac[i - 1] * i % Mod;
LL ans = fac[h[1] - 1], S = h[1];
for (int i = 2; i <= n && h[i]; i ++) {
ans = ans * fac[h[i] - 1] % Mod * ((S - (i - 1) * h[i]) % Mod) % Mod;
S += h[i];
}
printf("%lld\n", ans);
return 0;
}
ARC193A Complement Interval Graph
一个分类讨论题。
题目求从区间 \(S\) 走到 \(T\) 的最小点权。
考虑从 \(S\) 走到 \(T\) 的最小点权有三种情况：
- 如果 \(S\) 和 \(T\) 没有交集，那么可以直接从 \(S\) 走到 \(T\) 一定最小，否则考虑 \(2\) 和 \(3\)
- 从 \(S\) 走到不被 \(S\) 和 \(T\) 包含的区间 \(P\)，再从 \(P\) 走到 \(T\)
- 从 \(S\) 走到不交 \(S\) 的区间 \(P_1\)，再从 \(P_1\) 走到不交 \(T\) 的区间 \(P_2\)，再走到 \(T\)
首先第一种方式如果符合条件肯定就是最小值。接着考虑，如果除开 \(S\) 和 \(T\) 后点权最小的点为 \(P\)，且 \(P\) 和 \(S、T\) 没有交集，肯定选 \(P\) 即情况二。否则我们就得退而求其次，考虑不交 \(S\) 的最小点 \(P_1\)，如果 \(P_1\) 不交 \(T\) 那么就相当于情况二；如果交的话再找一个不与 \(T\) 交的最小区间 \(P_2\)，此时 \(S\to P_1\to P_2 \to T\) 一定是一条合法的路径。因为如果 \(P_1\) 与 \(P_2\) 相交的话一定存在情况二的做法。
考虑 \(S\) 和 \(T\) 有交集那么 \(L_S \leq L_T \leq R_S \leq R_T\)，然后由于 \(S\) 和 \(P_1\)，\(T\) 和 \(P_2\) 都不交，而两个区间 \(Line_1\) 和 \(Line_2\) 不交有两种情况，一种是 \(R_1 < L_2\) 一种是 \(R_2 < L_1\)，所以回到我们一共有四种情况。假设 \(R_S < L_{P_1}, R_T < L_{P_2}\)，那么一定有 \(R_S < L_{P_2}\)，即 \(S\) 和 \(P_2\) 不交，就可以使用情况二的做法了，一定比情况三的更优，因为少走了一个 \(P_1\)。其它三种情况也是同理，这里就不过多赘述了。
我们可以将所有区间按照 \(L\) 排序维护点权后缀最小值，再按照 \(R\) 排序维护一个点权前缀最大值，然后对于每个询问对以上情况取最小值即可。
注意到我们其实并不需要 \(sort\) 两遍，因为题目保证区间的 \(L, R \leq 2N\)。
贪心题的证明总是很复杂，累死了喵。
const int N = 200010;
int n, q;
int l[N], r[N];
LL w[N], pre[N << 1], suf[N << 1];
int main() {
n = read();
rep(i, 1, n) w[i] = read();
rep(i, 1, n) l[i] = read(), r[i] = read();
rep(i, 0, n * 2 + 1) suf[i] = pre[i] = 1e18;
rep(i, 1, n) {
pre[r[i]] = min(pre[r[i]], w[i]);
suf[l[i]] = min(suf[l[i]], w[i]);
}
rep(i, 1, n << 1) pre[i] = min(pre[i], pre[i - 1]);
fro(i, n << 1, 1) suf[i] = min(suf[i], suf[i + 1]);
q = read();
while (q --) {
int s = read(), t = read();
if (r[s] > r[t]) swap(s, t);
if (r[s] < l[t]) printf("%lld\n", w[s] + w[t]);
else {
LL res = min(suf[r[t] + 1], pre[min(l[s], l[t]) - 1]);
res = min(res, suf[r[s] + 1] + pre[l[t] - 1]);
if (res == 1e18) puts("-1");
else printf("%lld\n", res + w[s] + w[t]);
}
}
return 0;
}
最近更新：2024/3/11
浙公网安备 33010602011771号