[心之碎片] - 20240809模拟赛

柿子饼同学

总结与反思

F  - 最小生成树相关优先考虑按照边权分类

G - 不好枚举, 可以考虑构造搜索答案, 要注意阶段的区分, 数字太大考虑同余

H - 求很多点之间的最短路我们可以建立超级源点向每个关键点连边, 图论相关一定要注意图是否连通, 构建新图考虑一个点到另外一个点的花费等等

F - MST Unification
简单题, 考试时候用 kruskal 重构树水过去了, 后来才发现大家边求 mst 边求答案...
考虑什么时候会发生 mst 不唯一的情况, 当然也就是两个边权值一样, 但是一个边加了另一个边加不了的时候, 所以没了

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. const int N = 2e5 + 5;
   
5. 
   
6. struct DSU{
   
7.     int f[N];
   
8. 
   
9.     DSU(){ iota(f, f + N, 0); }
   
10. 
    
11.     int Find(int x){
    
12.         if(f[x] == x) return x;
    
13.         return (f[x] = Find(f[x]));
    
14.     }
    
15. 
    
16.     bool Iseq(int x, int y){
    
17.         x = Find(x), y = Find(y);
    
18.         return (x == y);
    
19.     }
    
20. 
    
21.     void Merge(int x, int y){
    
22.         f[Find(x)] = Find(y);
    
23.     }
    
24. } dsu;
    
25. 
    
26. struct Edge{
    
27.     int u, v, w;
    
28. } e[N];
    
29. 
    
30. int n, m, ans;
    
31. int stk[N], top;
    
32. 
    
33. int main(){
    
34.     ios::sync_with_stdio(0);
    
35.     cin.tie(0);
    
36.    
    
37.     cin >> n >> m;
    
38.     for(int i = 1; i <= m; i++){
    
39.         int u, v, w;
    
40.         cin >> u >> v >> w;
    
41.         e[i] = {u, v, w};
    
42.     }
    
43. 
    
44.     sort(e + 1, e + m + 1, [](Edge& a, Edge& b){ return a.w < b.w; });
    
45. 
    
46.     for(int i = 1; i <= m; i++){
    
47.         int l = i, r = i;
    
48.         while(r <= m && e[r].w == e[l].w) r++;
    
49.         r--;
    
50. 
    
51.         top = 0;
    
52.         for(int j = l; j <= r; j++){
    
53.             if(dsu.Iseq(e[j].u, e[j].v)) continue;
    
54.             stk[++top] = j;
    
55.         }
    
56. 
    
57.         // 相同边权, 本来有可能被加进去的, 现在加不进去所以必须让她边权 +1
    
58.         for(int j = 1; j <= top; j++){
    
59.             if(dsu.Iseq(e[stk[j]].u, e[stk[j]].v)){
    
60.                 ans++;
    
61.                 continue;
    
62.             }
    
63.             
    
64.             dsu.Merge(e[stk[j]].u, e[stk[j]].v);
    
65.         }
    
66. 
    
67.         i = r;
    
68.     }
    
69. 
    
70.     cout << ans;
    
71.    
    
72.     return 0;
    
73. }

复制代码

G - [ABC077D] Small Multiple
没想出来, 后来发现很简单
枚举 d 会超时, 就想着构造答案
每次 K*d 这个数可以 *10 或者 +1, 后者会对数位和产生贡献, 然后广搜, 要求是 k 的倍数, 所以数字 %k, 最后 %k == 0 的状态就是最优解
解释一下为什么不用考虑进位：进位的情况一定对应一种其他的情况，我们发现另一种情况各位和更小，所以这种情况一定是不优的，所以存在f里的不存在进位的影响。

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. // K*d 不好枚举 d, 考虑构造答案
   
5. // 这时不仅要想到 dp 还要想到搜索(记忆化)
   
6. // 构造数字有 +1 *10 两个操作, 只需要判断 %K == 0 即可
   
7. // 代价分别是 1, 0, 用 deque 跑 0/1bfs 就行了
   
8. // 构造的阶段就是一位一位的枚举
   
9. 
   
10. const int N = 1e5 + 5;
    
11. 
    
12. struct St{
    
13.     // %k 的余数, 现在的数位和
    
14.     int num, sum;
    
15. };
    
16. 
    
17. int f[N];
    
18. deque<St> q;
    
19. int k;
    
20. 
    
21. int main(){
    
22.     ios::sync_with_stdio(0);
    
23.     cin.tie(0);
    
24.    
    
25.     cin >> k;
    
26.     memset(f, 0x3f, sizeof(f));
    
27.     q.push_back({1, 1});
    
28.     f[1] = 1;
    
29. 
    
30.     int temp;
    
31.     while(!q.empty()){
    
32.         auto cur = q.front();
    
33.         q.pop_front();
    
34. 
    
35.         if(cur.num == 0){
    
36.             cout << cur.sum;
    
37.             return 0;
    
38.         }
    
39.         
    
40.         temp = cur.num*10 % k;
    
41.         if(cur.sum < f[temp]){
    
42.             f[temp] = cur.sum;
    
43.             q.push_front({temp, cur.sum});
    
44.         }
    
45.         
    
46.         temp = (cur.num + 1) % k;
    
47.         if(cur.sum + 1 < f[temp]){
    
48.             f[temp] = cur.sum + 1;
    
49.             q.push_back({temp, cur.sum + 1});
    
50.         }
    
51.     }
    
52.    
    
53.     return 0;
    
54. }

复制代码

G - Cheap Robot
没啥好说的, 没考虑搞超级源点, 写暴力也没判断是否连通, 挂了
我用了 kruskal 重构树, 其实求个最小生成树倍增求边上最大值一样的, 考虑两个点之间怎么走就出来了

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. typedef long long ll;
   
5. 
   
6. const int N = 1e5 + 5;
   
7. const int K = 2e5 + 5;
   
8. const int M = 3e5 + 5;
   
9. 
   
10. struct Node {
    
11.     int id;
    
12.     ll w;
    
13. 
    
14.     bool operator<(const Node& t) const { return w > t.w; }
    
15. };
    
16. 
    
17. struct Kru {
    
18.     int u, v;
    
19.     ll w;
    
20. } edges[M << 1];
    
21. int cnt;
    
22. 
    
23. int n, m, k, q;
    
24. vector<Node> g[N];
    
25. vector<int> e[K];
    
26. ll dist[N], val[K];
    
27. bitset<N> vis;
    
28. priority_queue<Node> p;
    
29. int f[K][19], dep[K];
    
30. 
    
31. void Dijkstra() {
    
32.     memset(dist, 0x3f, sizeof(dist));
    
33.     p.push({ 0, 0 });
    
34.     dist[0] = 0;
    
35. 
    
36.     while (!p.empty()) {
    
37.         auto u = p.top().id;
    
38.         p.pop();
    
39. 
    
40.         if (vis[u])
    
41.             continue;
    
42.         vis[u] = 1;
    
43. 
    
44.         for (auto ed : g[u]) {
    
45.             int v = ed.id;
    
46.             ll w = ed.w;
    
47.             if (dist[u] + w < dist[v]) {
    
48.                 dist[v] = dist[u] + w;
    
49.                 if (!vis[v])
    
50.                     p.push({ v, dist[v] });
    
51.             }
    
52.         }
    
53.     }
    
54. }
    
55. 
    
56. struct DSU {
    
57.     int f[K], tot;
    
58. 
    
59.     void Init() {
    
60.         iota(f, f + K, 0);
    
61.         tot = n;
    
62.     }
    
63. 
    
64.     int Find(int x) {
    
65.         if (x == f[x])
    
66.             return x;
    
67.         return (f[x] = Find(f[x]));
    
68.     }
    
69. 
    
70.     int Merge(int x, int y) {
    
71.         x = Find(x), y = Find(y);
    
72.         if (x == y)
    
73.             return 0;
    
74. 
    
75.         tot++;
    
76.         f[x] = tot;
    
77.         f[y] = tot;
    
78. 
    
79.         e[tot].emplace_back(x);
    
80.         e[tot].emplace_back(y);
    
81.         e[x].emplace_back(tot);
    
82.         e[y].emplace_back(tot);
    
83.         return tot;
    
84.     }
    
85. } dsu;
    
86. 
    
87. void Kruskal() {
    
88.     dsu.Init();
    
89. 
    
90.     for (int i = 1; i <= n; i++) {
    
91.         for (auto j : g[i]) {
    
92.             if (j.id > 0) {
    
93.                 edges[++cnt] = { i, j.id, dist[i] + dist[j.id] + j.w };
    
94.             }
    
95.         }
    
96.     }
    
97. 
    
98.     sort(edges + 1, edges + cnt + 1, [](Kru& a, Kru& b) { return a.w < b.w; });
    
99. 
    
100.     int u, v, w, cur;
     
101.     for (int i = 1; i <= cnt; i++) {
     
102.         u = edges[i].u;
     
103.         v = edges[i].v;
     
104.         w = edges[i].w;
     
105.         cur = dsu.Merge(u, v);
     
106. 
     
107.         if (cur)
     
108.             val[cur] = w;
     
109.     }
     
110. }
     
111. 
     
112. void dfs(int u, int pa) {
     
113.     f[u][0] = pa;
     
114.     dep[u] = dep[pa] + 1;
     
115. 
     
116.     for (int i = 1; i < 19; i++) {
     
117.         f[u][i] = f[f[u][i - 1]][i - 1];
     
118.     }
     
119. 
     
120.     for (auto ed : e[u]) {
     
121.         if (ed == pa)
     
122.             continue;
     
123.         dfs(ed, u);
     
124.     }
     
125. }
     
126. 
     
127. int lca(int x, int y) {
     
128.     if (dep[x] < dep[y])
     
129.         swap(x, y);
     
130. 
     
131.     int d = dep[x] - dep[y];
     
132.     for (int i = 18; i >= 0; i--) {
     
133.         if ((d >> i) & 1) {
     
134.             x = f[x][i];
     
135.         }
     
136.     }
     
137. 
     
138.     if (x == y)
     
139.         return x;
     
140. 
     
141.     for (int i = 18; i >= 0; i--) {
     
142.         if (f[x][i] != f[y][i]) {
     
143.             x = f[x][i];
     
144.             y = f[y][i];
     
145.         }
     
146.     }
     
147. 
     
148.     return f[x][0];
     
149. }
     
150. 
     
151. int main() {
     
152.     ios::sync_with_stdio(0);
     
153.     cin.tie(0);
     
154. 
     
155.     cin >> n >> m >> k >> q;
     
156.     for (int i = 1; i <= m; i++) {
     
157.         int u, v, w;
     
158.         cin >> u >> v >> w;
     
159.         g[u].push_back({ v, w });
     
160.         g[v].push_back({ u, w });
     
161.     }
     
162.     for (int i = 1; i <= k; i++) {
     
163.         g[0].push_back({ i, 0 });
     
164.         g[i].push_back({ 0, 0 });
     
165.     }
     
166. 
     
167.     Dijkstra();
     
168.     Kruskal();
     
169.     dfs(dsu.tot, 0);
     
170. 
     
171.     while (q--) {
     
172.         int x, y;
     
173.         cin >> x >> y;
     
174.         cout << val[lca(x, y)] << '\n';
     
175.     }
     
176. 
     
177.     return 0;
     
178. }

复制代码

学习编程中的Ben

大佬收下我的膝盖

sfqxx

@zhangjinxuan

简柠啦

lwh0602

很cool的阳

lwh0602

18408238295

学习学习

曾热爱这世界

&#128076;

zsy0226

膜拜大佬/orz/orz

trinityee

唉，高山啊高山

森林格格屋

谢谢