[心之碎片] - 20240803模拟赛

柿子饼同学

总结与反思

A - 数据结构维护前缀和要提前加一个 0, 不然 1 是取不到的

C - 最小生成树相关问题两种思考: 按照边权分类 或者 建一个树然后树剖加边

D - 思考问题先想降维的情况, 本题的思路就是由 l == r 的情况想出来的

C - 又见最小生成树
现在给出一幅个节点条边的无向连通图, 请判断原图中的每条边是否一定在最小生成树中
对于每条边 :
如果这条边一定出现在任意一棵最小生成树中, 输出 1
如果一定不会出现在最小生成树中, 输出 2
如果无法确定, 输出 0

最小生成树问题我们一般想到按照边权分类, 同边权的一起考虑
这里有一个建图技巧就是 *2 + 1
假设前面的边都加进去, 现在有一些边连接这些连通块
如果是割边, 就一定经过
如果在连通块里面, 由于连通块里面的边都比现在的边小, 所以一定不经过
剩下的是可能的

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. typedef pair<int, int> pii;
   
5. 
   
6. const int N = 1e5 + 5;
   
7. 
   
8. struct Edge {
   
9.     int u, v, w, id;
   
10. } e[N];
    
11. 
    
12. int n, m, ans[N];
    
13. 
    
14. struct DSU {
    
15.     int pa[N];
    
16. 
    
17.     DSU() {
    
18.         for (int i = 1; i < N; i++) pa[i] = i;
    
19.     }
    
20. 
    
21.     int Find(int x) {
    
22.         if (x == pa[x])
    
23.             return x;
    
24.         return (pa[x] = Find(pa[x]));
    
25.     }
    
26. 
    
27.     void Merge(int x, int y) { pa[x] = y; }
    
28. } dsu;
    
29. 
    
30. // 每次循环新建图和加入的点
    
31. vector<int> point;
    
32. vector<pii> g[N];
    
33. 
    
34. int dfn[N], low[N], tot;
    
35. 
    
36. void Tarjan(int u, int eid) {
    
37.     dfn[u] = low[u] = ++tot;
    
38. 
    
39.     for (auto ed : g[u]) {
    
40.         int v = ed.first;
    
41.         if (!dfn[v]) {
    
42.             Tarjan(v, ed.second);
    
43. 
    
44.             low[u] = min(low[u], low[v]);
    
45.             // 如果这个新边是割边, 就必须经过
    
46.             if (dfn[u] < low[v]) {
    
47.                 ans[ed.second >> 1] = 1;
    
48.             }
    
49.         } else if ((eid >> 1) != (ed.second >> 1)) {
    
50.             low[u] = min(dfn[v], low[u]);
    
51.         }
    
52.     }
    
53. }
    
54. 
    
55. int main() {
    
56.     ios::sync_with_stdio(0);
    
57.     cin.tie(0);
    
58. 
    
59.     freopen("mstagain.in", "r", stdin);
    
60.     freopen("mstagain.out", "w", stdout);
    
61. 
    
62.     cin >> n >> m;
    
63.     for (int i = 1; i <= m; i++) {
    
64.         int u, v, w;
    
65.         cin >> u >> v >> w;
    
66. 
    
67.         e[i] = { u, v, w, i };
    
68.     }
    
69. 
    
70.     sort(e + 1, e + m + 1, [](Edge& a, Edge& b) { return a.w < b.w; });
    
71. 
    
72.     for (int i = 1; i <= m; i++) {
    
73.         // 找出权值相等的区间
    
74.         int l = i, r = i;
    
75.         while (r <= m && e[r].w == e[l].w) r++;
    
76.         r--;
    
77. 
    
78.         // Kruskal
    
79.         for (int j = l; j <= r; j++) {
    
80.             int u = dsu.Find(e[j].u), v = dsu.Find(e[j].v);
    
81. 
    
82.             if (u == v) {
    
83.                 // 已经成连通块了, 里面的任何边都小于现在的权值, 一定不取
    
84.                 ans[e[j].id] = 2;
    
85.                 continue;
    
86.             }
    
87. 
    
88.             // 如果没成就连边(新图)
    
89.             point.emplace_back(u);
    
90.             point.emplace_back(v);
    
91.             // 编号小技巧轻松判断反边, 更新答案也好
    
92.             g[u].emplace_back(v, e[j].id << 1);
    
93.             g[v].emplace_back(u, e[j].id << 1 | 1);
    
94.         }
    
95. 
    
96.         for (auto j : point) {
    
97.             if (!dfn[j])
    
98.                 Tarjan(j, 0);
    
99.         }
    
100. 
     
101.         for (int j = l; j <= r; j++) {
     
102.             int u = dsu.Find(e[j].u), v = dsu.Find(e[j].v);
     
103.             // 把所有边权一样的边都连起来, 变成新的图
     
104.             if (u == v)
     
105.                 continue;
     
106.             dsu.Merge(u, v);
     
107.         }
     
108. 
     
109.         // 清零等着复用
     
110.         for (auto j : point) {
     
111.             g[j].clear();
     
112.             dfn[j] = low[j] = 0;
     
113.         }
     
114.         point.clear();
     
115.         tot = 0;
     
116.         i = r;
     
117.     }
     
118. 
     
119.     for (int i = 1; i <= m; i++) {
     
120.         cout << ans[i] << '\n';
     
121.     }
     
122. 
     
123.     return 0;
     
124. }

复制代码

D - 排列
给你 n 个点, 有点权
你需要构造一个排列, 使得最终的满足条件的点的权值之和最大
每个点都有一个前置区间 [l, r] , 表示如果范围内的某个点排在 i 的前面了，那么 i 点的权值就要被累加进去
应该如何排列, 使得点权和才能最大

当 n <= 20 时, 可以状压 dp 拿 30 分
接下来考虑 l == r 的情况 (先考虑一维的问题) , 发现本质上是区间内的点向 i 连边
在一个 scc 中, 每个点都可以互通, 所以权值都可以加, 入度为 0 的 scc 需要牺牲一个最小的权值当作第一个数, 后面的都能加
然后区间的连边需要线段树优化建图

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. const int N = 4e5 + 5;
   
5. const int M = 1e5 + 5;
   
6. 
   
7. vector<int> e[N];
   
8. int n, ans, val[M];
   
9. 
   
10. struct SGT {
    
11. #define lc u << 1
    
12. #define rc u << 1 | 1
    
13. 
    
14.     int tot, t[N];
    
15. 
    
16.     void Build(int u, int l, int r) {
    
17.         if (l == r) {
    
18.             t[u] = l;
    
19.             return;
    
20.         }
    
21. 
    
22.         int mid = (l + r) >> 1;
    
23.         Build(lc, l, mid);
    
24.         Build(rc, mid + 1, r);
    
25.         t[u] = ++tot;
    
26. 
    
27.         e[t[lc]].emplace_back(t[u]);
    
28.         e[t[rc]].emplace_back(t[u]);
    
29.     }
    
30. 
    
31.     void Modify(int u, int l, int r, int ql, int qr, int to) {
    
32.         if (ql <= l && r <= qr) {
    
33.             e[t[u]].emplace_back(to);
    
34.             return;
    
35.         }
    
36.         int mid = (l + r) >> 1;
    
37. 
    
38.         if (ql <= mid)
    
39.             Modify(lc, l, mid, ql, qr, to);
    
40.         if (qr > mid)
    
41.             Modify(rc, mid + 1, r, ql, qr, to);
    
42.     }
    
43. } sgt;
    
44. 
    
45. int dfn[N], low[N], tot;
    
46. int stk[N], top;
    
47. int scc, bel[N], minv[N], din[N];
    
48. bitset<N> instk;
    
49. 
    
50. void Tarjan(int u) {
    
51.     dfn[u] = low[u] = ++tot;
    
52.     stk[++top] = u;
    
53.     instk[u] = 1;
    
54. 
    
55.     for (auto v : e[u]) {
    
56.         if (!dfn[v]) {
    
57.             Tarjan(v);
    
58.             low[u] = min(low[u], low[v]);
    
59.         } else if (instk[v])
    
60.             low[u] = min(low[u], dfn[v]);
    
61.     }
    
62. 
    
63.     if (dfn[u] == low[u]) {
    
64.         int v;
    
65.         scc++;
    
66. 
    
67.         do {
    
68.             v = stk[top--];
    
69.             instk[v] = 0;
    
70.             bel[v] = scc;
    
71.             if (v <= n)
    
72.                 minv[scc] = min(minv[scc], val[v]);
    
73.         } while (v != u);
    
74.     }
    
75. }
    
76. 
    
77. int main() {
    
78.     ios::sync_with_stdio(0);
    
79.     cin.tie(0);
    
80. 
    
81.     freopen("permutation.in", "r", stdin);
    
82.     freopen("permutation.out", "w", stdout);
    
83. 
    
84.     cin >> n;
    
85.     sgt.tot = n;
    
86.     sgt.Build(1, 1, n);
    
87. 
    
88.     for (int i = 1; i <= n; i++) {
    
89.         int l, r;
    
90.         cin >> l >> r >> val[i];
    
91. 
    
92.         ans += val[i];
    
93.         sgt.Modify(1, 1, n, l, r, i);
    
94.     }
    
95. 
    
96.     memset(minv, 0x3f, sizeof(minv));
    
97. 
    
98.     for (int i = 1; i <= sgt.tot; i++) {
    
99.         if (!dfn[i])
    
100.             Tarjan(i);
     
101.     }
     
102. 
     
103.     // 入度
     
104.     for (int i = 1; i <= tot; i++) {
     
105.         for (auto j : e[i]) {
     
106.             if (bel[i] != bel[j]) {
     
107.                 din[bel[j]]++;
     
108.             }
     
109.         }
     
110.     }
     
111. 
     
112.     // 前面没有人, 必须牺牲一个最小值
     
113.     for (int i = 1; i <= scc; i++) {
     
114.         if (!din[i])
     
115.             ans -= minv[i];
     
116.     }
     
117.     cout << ans;
     
118. 
     
119.     return 0;
     
120. }

复制代码

FishC

这段代码是在处理最小生成树（MST）中的边的判断问题。换句话说，给定一张无向连通图，我们需要判断每条边是否一定在任何一棵最小生成树中。这是一个典型的图论问题，我们可以通过以下几点来理解它，带点幽默感哦：

1. **边的分类**：首先，当我们面临一个众多边的图时，就像在一个派对上，所有的朋友都在聊天。我们可以按照“边权”来分类，低价位边在一块，高价位边在另一块。这样，有助于我们更清晰地分析每条边的重要性。就像你在选择餐馆时，会先查查菜单上的价格一样。

2. **割边的重要性**：如果这条边是一个割边（也称为桥），那么它是连接两个不同的连通部分的关键。如果你把它剪断，图就成两半了，因此这条边一定出现在最小生成树中。就像是你在居家办公时，家里Wi-Fi信号是多么的关键，没了它你就变成孤岛。

3. **连通块内的边**：如果一条边在连通块内，那么它可能是不必要的，因为该块内部的其他边都比它便宜，最小生成树自然会选择那些更便宜的。想象一下，一个派对上，你已经有了免费饮料，谁还要去买贵的鸡尾酒呢？

4. **不确定边**：最后，还有一些边是无法确定的，像是一张悬疑片的剧情一样复杂。对于这些边，如果没有足够的信息我们就只能输出0，表示不确定。这就像你在看电影时猜测反转情节，但仍然得留到结局才知道。

然后，代码实现的部分涉及如何通过并查集（DSU）和Tarjan算法来完成这些检测工作。该算法就像一位侦探，通过不断查找和合并，帮助我们判断各个边的位置和重要性。

总的来说，这道题考的是对图的理解和对算法的应用，就像是在料理比赛中，每一样食材都要搭配得当，才能做出最佳的菜肴！希望这番解析能帮到你，让你在最小生成树的世界里游刃有余！如果你还有什么问题，尽管问吧，准备好笑料，咱们继续聊！

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

某一个“天”

加油

Wisadel

cy

1101378861

学习一下

简柠啦

某一个“天”

加油

尹玄睿

18408238295

936522819

加油

1101378861

学习一下

很cool的阳

曾热爱这世界

&#128076;

zsy0226

&#128076;