[心之碎片] - 20240810模拟赛

柿子饼同学

总结与反思

A - 递归要贴合意义, 敢写

B - 树上问题应该多画画图找性质

D - 遇到必须经过小于 w 的边之类问题想到 kruskal 重构树, dsu 预处理每个点的答案

A - 括号翻转
给定给一个字符串，其中含有很多括号，括号里的内容会被翻转，输出这个字符串去掉括号的结果。

没啥好说的...

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. const int N = 5e5 + 5;
   
5. 
   
6. string s;
   
7. int L[N], R[N], n;
   
8. stack<int> stk;
   
9. 
   
10. void dfs(int l, int r, int rev) {
    
11.     if (l > r)
    
12.         return;
    
13.     if (rev) {
    
14.         for (int i = r; i >= l; i--) {
    
15.             if (s[i] != '(' && s[i] != ')')
    
16.                 cout << s[i];
    
17.             else
    
18.                 dfs(L[i] + 1, i - 1, rev ^ 1), i = L[i];
    
19.         }
    
20.     } else {
    
21.         for (int i = l; i <= r; i++) {
    
22.             if (s[i] != '(' && s[i] != ')')
    
23.                 cout << s[i];
    
24.             else
    
25.                 dfs(i + 1, R[i] - 1, rev ^ 1), i = R[i];
    
26.         }
    
27.     }
    
28. }
    
29. 
    
30. int main() {
    
31.     ios::sync_with_stdio(0);
    
32.     cin.tie(0);
    
33. 
    
34.     freopen("bracket.in", "r", stdin);
    
35.     freopen("bracket.out", "w", stdout);
    
36. 
    
37.     cin >> s;
    
38.     n = s.size();
    
39.     s = '-' + s;
    
40. 
    
41.     for (int i = 1; i <= n; i++) {
    
42.         if (s[i] == '(')
    
43.             stk.push(i);
    
44.         if (s[i] == ')') {
    
45.             int x = stk.top();
    
46.             stk.pop();
    
47. 
    
48.             R[x] = i, L[i] = x;
    
49.         }
    
50.     }
    
51. 
    
52.     dfs(1, n, 0);
    
53. 
    
54.     return 0;
    
55. }

复制代码

B - 香蕉
在一个树上给出 a, b, c, d, 问 a, b 和 c, d 之间的路径是否有相交

考试时候无脑线段树, 其实有很简单的做法, 画画图找出性质

1. for (int i = 1; i <= m; i++) {
   
2.         int u, v, x, y;
   
3.         cin >> u >> v >> x >> y;
   
4.         int S = getlca(u, v), T = getlca(x, y);
   
5.         if (dep[S] < dep[T]) {
   
6.             swap(S, T), swap(u, x), swap(v, y);
   
7.         }
   
8.         if (getlca(S, x) == S || getlca(S, y) == S)
   
9.             cout << "YES\n";
   
10.         else
    
11.             cout << "NO\n";
    
12.     }

复制代码

C - 排列盒子
原题可以转化，构造一个排列，设定一个大小关系，使得逆序对的数量最小。

发现总颜色数很小, 考虑状压安排顺序
考试的时候没有搞出来预处理逆序对, tle 了, 可惜啊

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 M = 20;
   
8. 
   
9. // cnt[i][j] 表示 i 优先于 j 产生的逆序对个数
   
10. ll cnt[M][M], sum[M];
    
11. int n, k;
    
12. ll f[(1 << M)];
    
13. 
    
14. ll Cost(int x, int st) {
    
15.     ll res = 0;
    
16.     for (int i = 0; i < k; i++) {
    
17.         if ((st >> i) & 1)
    
18.             continue;
    
19.         // x 优先于 i
    
20.         res += cnt[x][i];
    
21.     }
    
22.     return res;
    
23. }
    
24. 
    
25. int main() {
    
26.     ios::sync_with_stdio(0);
    
27.     cin.tie(0);
    
28. 
    
29.     freopen("box.in", "r", stdin);
    
30.     freopen("box.out", "w", stdout);
    
31. 
    
32.     cin >> n >> k;
    
33.     for (int i = 1; i <= n; i++) {
    
34.         int x;
    
35.         cin >> x;
    
36.         x--;
    
37. 
    
38.         for (int j = 0; j < k; j++) {
    
39.             if (j == x)
    
40.                 continue;
    
41.             // 假设 x 优先于 j, 那 x 前面的 j 的个数就是贡献
    
42.             cnt[x][j] += sum[j];
    
43.         }
    
44.         sum[x]++;
    
45.     }
    
46. 
    
47.     memset(f, 0x3f, sizeof(f));
    
48. 
    
49.     f[0] = 0;
    
50. 
    
51.     for (int st = 0; st < (1 << k); st++) {
    
52.         for (int i = 0; i < k; i++) {
    
53.             if ((st >> i) & 1)
    
54.                 continue;
    
55. 
    
56.             f[st | (1 << i)] = min(f[st | (1 << i)], f[st] + Cost(i, st | (1 << i)));
    
57.         }
    
58.     }
    
59. 
    
60.     cout << f[(1 << k) - 1];
    
61. 
    
62.     return 0;
    
63. }

复制代码

乱搞做法, 直接取最小值安排顺序, 但是有可能成环

1. 
   
2.     for (int i = 1; i <= n; i++) {
   
3.         int x;
   
4.         cin >> x;
   
5. 
   
6.         for (int j = 1; j <= k; j++) {
   
7.             if (x != j) {
   
8.                 p[x][j] += sum[j];
   
9.             }
   
10.         }
    
11.         sum[x]++;
    
12.     }
    
13. 
    
14.     for (int i = 1; i <= k; i++) {
    
15.         for (int j = i + 1; j <= k; j++) {
    
16.             ans += min(p[i][j], p[j][i]);
    
17.         }
    
18.     }
    
19. }

复制代码

D - 花园
Mr. Panda 有 N 个花园，编号从 1 到 N 。对于编号为 i 的花园，花园里只有一朵花，颜色为  。花园与花园之间有道路连接（道路是双向的）。每条道路都有一个花费，表示经过该道路花费的时间。
Mr. Panda 喜欢在他的N个花园中转悠，然后采尽可能多的同种颜色的花
然而，有时候他并不想花太多时间走同一段路
现在问题来了，每一次 Mr. Panda 会告诉你：他从哪个花园开始出发和他能忍受的走同一段路的花费的最大值w（也就是说，只有费用不超过w的道路可以通行）
请你判断Mr. Panda最多能采到的花是哪种颜色的花。如果有多种颜色符合条件，选择颜色编号最小的输出

这种的关于路径最大值最小要想最小生成树, 进而想到 kruskal 重构树
那么 lca 就是边权最大值, 每次询问在 lca 的子树内就是活动范围
那么怎么知道答案? 时间太大, 只能看看能不能提前全出来, 那就用 dsu 吧

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. const int N = 1e5 + 5;
   
5. const int M = 2e5 + 5;
   
6. const int K = 3e5 + 5;
   
7. 
   
8. // 和最大边权最小有关, 考虑 kruskal 重构树
   
9. // 建出来之后对于 u, 她的活动范围就是最大的权值不超过 w 的点的子树
   
10. // 然后就是询问区间众数, 这里用树上启发式合并来做, 求出每个点所在子树的答案, 也可以用线段树合并
    
11. 
    
12. // Global
    
13. int n, m, type, c[N];
    
14. 
    
15. // Kruskal tree
    
16. vector<int> e[M];
    
17. int val[M];
    
18. 
    
19. struct Kru {
    
20.     int u, v, w;
    
21. } edges[K];
    
22. 
    
23. struct DSU {
    
24.     int f[M], tot;
    
25. 
    
26.     void Init() {
    
27.         iota(f, f + M, 0);
    
28.         tot = n;
    
29.     }
    
30. 
    
31.     int Find(int x) {
    
32.         if (x == f[x])
    
33.             return x;
    
34.         return (f[x] = Find(f[x]));
    
35.     }
    
36. 
    
37.     int Merge(int x, int y) {
    
38.         x = Find(x), y = Find(y);
    
39. 
    
40.         if (x == y)
    
41.             return 0;
    
42. 
    
43.         tot++;
    
44.         f[x] = tot, f[y] = tot;
    
45.         e[tot].emplace_back(x);
    
46.         e[tot].emplace_back(y);
    
47.         return tot;
    
48.     }
    
49. } dsu;
    
50. 
    
51. void Kruskal() {
    
52.     dsu.Init();
    
53.     val[0] = 1e9;
    
54. 
    
55.     sort(edges + 1, edges + m + 1, [](Kru& a, Kru& b) { return a.w < b.w; });
    
56. 
    
57.     for (int i = 1; i <= m; i++) {
    
58.         int cur = dsu.Merge(edges[i].u, edges[i].v);
    
59.         if (cur)
    
60.             val[cur] = edges[i].w;
    
61.     }
    
62. }
    
63. 
    
64. // DSU on tree
    
65. int cnt[M], tot, ans[M], mxid, mxap;
    
66. int f[M][18], hc[M], dfn[M], rdfn[M], siz[M];
    
67. 
    
68. void dfs0(int u, int pa) {
    
69.     f[u][0] = pa;
    
70.     siz[u] = 1;
    
71.     dfn[u] = ++tot;
    
72.     rdfn[tot] = u;
    
73. 
    
74.     for (int i = 1; i < 18; i++) {
    
75.         f[u][i] = f[f[u][i - 1]][i - 1];
    
76.     }
    
77. 
    
78.     for (auto ed : e[u]) {
    
79.         if (ed == pa)
    
80.             continue;
    
81.         dfs0(ed, u);
    
82. 
    
83.         siz[u] += siz[ed];
    
84.         if (siz[hc[u]] < siz[ed])
    
85.             hc[u] = ed;
    
86.     }
    
87. }
    
88. 
    
89. void Modify(int col) {
    
90.     cnt[col]++;
    
91.     if (cnt[col] == mxap) {
    
92.         mxid = min(mxid, col);
    
93.     } else if (cnt[col] > mxap) {
    
94.         mxap = cnt[col];
    
95.         mxid = col;
    
96.     }
    
97. }
    
98. 
    
99. void Add(int u) {
    
100.     for (int i = dfn[u]; i < dfn[u] + siz[u]; i++) {
     
101.         if (rdfn[i] > n)
     
102.             continue;
     
103.         Modify(c[rdfn[i]]);
     
104.     }
     
105. }
     
106. 
     
107. void Del(int u) {
     
108.     mxap = 0, mxid = 1e9;
     
109. 
     
110.     for (int i = dfn[u]; i < dfn[u] + siz[u]; i++) {
     
111.         if (rdfn[i] <= n)
     
112.             cnt[c[rdfn[i]]] = 0;
     
113.     }
     
114. }
     
115. 
     
116. void Solve(int u, int pa, bool keep) {
     
117.     for (auto ed : e[u]) {
     
118.         if (ed == pa || ed == hc[u])
     
119.             continue;
     
120.         Solve(ed, u, 0);
     
121.     }
     
122. 
     
123.     if (hc[u])
     
124.         Solve(hc[u], u, 1);
     
125. 
     
126.     for (auto ed : e[u]) {
     
127.         if (ed == pa || ed == hc[u])
     
128.             continue;
     
129. 
     
130.         Add(ed);
     
131.     }
     
132.     if (u <= n)
     
133.         Modify(c[u]);
     
134. 
     
135.     ans[u] = mxid;
     
136. 
     
137.     if (keep)
     
138.         return;
     
139. 
     
140.     Del(u);
     
141. }
     
142. 
     
143. int main() {
     
144.     ios::sync_with_stdio(0);
     
145.     cin.tie(0);
     
146. 
     
147.     freopen("garden.in", "r", stdin);
     
148.     freopen("garden.out", "w", stdout);
     
149. 
     
150.     cin >> n >> m >> type;
     
151.     for (int i = 1; i <= n; i++) {
     
152.         cin >> c[i];
     
153.     }
     
154.     for (int i = 1; i <= m; i++) {
     
155.         int u, v, w;
     
156.         cin >> u >> v >> w;
     
157.         edges[i] = { u, v, w };
     
158.     }
     
159. 
     
160.     Kruskal();
     
161.     for (int i = dsu.tot; i; i--) {
     
162.         if (!dfn[i]) {
     
163.             dfs0(i, 0);
     
164.             Solve(i, 0, 0);
     
165.         }
     
166.     }
     
167. 
     
168.     int last = 0, q;
     
169. 
     
170.     cin >> q;
     
171.     while (q--) {
     
172.         int x, w;
     
173.         cin >> x >> w;
     
174. 
     
175.         if (type) {
     
176.             x ^= last;
     
177.             w ^= last;
     
178.         }
     
179. 
     
180.         for (int i = 17; i >= 0; i--) {
     
181.             if (val[f[x][i]] <= w)
     
182.                 x = f[x][i];
     
183.         }
     
184.         last = ans[x];
     
185. 
     
186.         cout << ans[x] << '\n';
     
187.     }
     
188. 
     
189.     return 0;
     
190. }

复制代码

FishC

看起来你在进行一些关于算法和数据结构的深入探讨，特别是在模拟赛中的总结与反思部分。让我试着用更幽默的方式来解释你提到的一些重要观点，尤其是关于括号翻转的问题。

### 括号翻转简单明了的小故事

想象一下，你有一个神奇的盒子，里面住着一群括号（当然它们都是有性格的）。这个盒子里有两种括号：左括号（`(`）和右括号（`)`），它们总是成对出现，就像一对恋人。当然，这些括号决定了他们的命运——如果它们不在一起，就会产生混乱，比如变成“（）”就好像分开散步的情侣。

#### 算法大冒险：DFS与括号翻转

你决定要把这些括号里的内容翻转过来，让它们体验一下“逆风翻盘”的感觉。你使用深度优先搜索（DFS）这一神奇的工具，带着勇气深入这个盒子。以下是你旅程中的几个关键步骤：

1. **递归函数（dfs）**：就像你在幽暗的森林中探险，每深入一步就要考虑周围的环境。如果你到了一个括号的开头，就打个叉，然后反向跟随它的伙伴，直到找到结尾。在这个过程中，你就能把里面的内容翻转过来了。

2. **翻转的时机**：当你看到左括号时，就要准备好翻转；而当你遇到右括号时，你要立刻把想要翻转的内容倒过来，正如在聚会上突然转身跳舞那样令人惊讶！

3. **输出结果**：最后，当你翻转完所有内容，所有的括号都重新组合的时候，你会感到无比自豪，就像看到所有情侣成功重聚的那一瞬间！你可以愉快地打印出最终结果，呼喊出“成功翻转，我是最棒的！”

### 结尾小贴士

每次在处理这种括号问题时，多画图、多理解其中的逻辑，总会让你的代码像魔术般流畅。而且，别忘了在适当的时候，给自己来一段轻松的笑话，这样即使面对复杂的问题，也能保持心情愉快，就像“为什么括号不喜欢上课？因为它们不想被分开！”

希望这段小故事能让你在算法的海洋中游得更顺畅！如果你有其他问题或想法，随时欢迎交流哦！

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

柿子饼同学

FishC 发表于 2024-8-10 21:15
看起来你在进行一些关于算法和数据结构的深入探讨，特别是在模拟赛中的总结与反思部分。让我试着用更幽默的 ...

再来 5 个笑话, 每个大约 60 字

FishC

柿子饼同学 发表于 2024-08-14 18:03
再来 5 个笑话, 每个大约 60 字

当然可以！以下是五个轻松幽默的笑话，希望能让你会心一笑：

1. 有一天，一个程序员去海边度假。他看到海浪在拍打沙滩，忍不住感叹：“这也太简单了吧，只需要输入‘波’和‘涛’，就能生成这么美的画面！”旁边的渔民听了，默默记下了新钓鱼技巧。

2. 一只鸡去上计算机课，老师问：“你为什么要学编程？”鸡回答：“我想要跳出这道‘程序’的框框，体验一下‘自由’的‘外面’！”全班顿时面面相觑，鸡却已飞走了。

3. 两个二进制数在酒吧喝酒，其中一个醉了，满脸困惑地说：“我感觉自己好像变成了十进制！”另一个二进制一脸不屑：“别傻了，你其实只是加了一点‘余数’而已！”

4. 一位工程师对同事说：“我正在研究如何让猫与狗共处一室。”同事好奇问：“如何实现？”工程师回答：“其实很简单，只需把它们的命令反转就好。你叫猫，它就跑；你叫狗，它就静。”

5. 有一天，一颗萝卜被问：“你为何总是待在土里，不出来晒太阳？”萝卜无奈地答：“我也是想尝试阳光下的生活，不过我的‘土豆朋友’提醒我：‘小心，不要被切片了！’”

希望这些笑话让你的心情更加愉快！如果还想要更多轻松的话题，尽管告诉我！

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

芜湖666

不会

18408238295

向大佬学习学习

很cool的阳

lwh0602

1101378861

学习一下

shuaijun

西安

磷酸

trinityee

厉害了楼主

森林格格屋

谢谢