[心之碎片] - 20240814模拟赛

柿子饼同学

总结与反思

B - 要反过来考虑贡献

C - 换根题通常想分类, 然后对于每个点求一个子树的答案, 一个子树外的答案, 树上问题一定要画图, 分类

D - dfs填数独实际上是对于一个点的队列来填, 只需要安排好搜索顺序,
带着全局变量的搜索搜到答案一定要给下一个赋值为现在这个, 因为回溯不一定是从头开始
警惕排序等会让位置变化的东西, 位置会变化导致无法按照原来的编号查询

B - 加号
给定一个长度为 n 的数字字符串，每个字符是'0'~'9'。
现在有k个加号，可以插入到字符串中，每个加号只能在两个数字之间。
每一种插入方案，都对应一个表达式，可以计算出一个值。
求所有方案的值之和。

插入加号的具体不好算, 考虑计算每个数字作为个位/十位...的总贡献, 这样就使得她后面的几个位置不能填 + , 其他位置随便
所以预处理组合数, 上前缀和

1. // sum[i] 表示 1 为第 i 位的贡献
   
2. // 垒前缀和即可 O(1) 计算
   
3. for (int i = 1; i <= n; i++) {
   
4.     sum[i] = sum[i - 1];
   
5.     sum[i] = sum[i] + math.p10[i - 1] % P * math.C(n - i - 1, k - 1) % P;
   
6. }
   
7. // 注意考虑 i 这个位置后面不放 +, 要单独算
   
8. for (int i = 1; i <= n; i++) {
   
9.     ans = (ans + (s[i] * (math.p10[n - i] * math.C(i - 1, k) % P + sum[n - i]) % P)) % P;
   
10. }
    
11. 
    
12. cout << ans;

复制代码

C - 疯狂动态树
换根 + 查询子树内的点到根的距离和 + 查询链上的点到根的距离和

分类讨论, 对于子树问题分类 : 根在 u 上, u 的子树内, u 的子树外
对于链, 求出根到链的最短路和接入根的点, 然后路径分成两半求个等差数列
对于点到链的两端加上这个链, 三个路径的交点是三个点的 lca 中去掉两个相同的值

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. const int N = 1e5 + 5;
   
5. 
   
6. int ID, n, m, rt;
   
7. vector<int> e[N];
   
8. 
   
9. // up, dn 分别代表除了子树, 子树内的节点到 x 的距离和
   
10. int siz[N], up[N], dn[N], dep[N], dfn[N], tot;
    
11. int f[N][18];
    
12. 
    
13. void dfs1(int u, int pa) {
    
14.     dfn[u] = ++tot;
    
15.     siz[u] = 1;
    
16.     f[u][0] = pa;
    
17.     dep[u] = dep[pa] + 1;
    
18. 
    
19.     for (int i = 1; i < 18; i++) {
    
20.         f[u][i] = f[f[u][i - 1]][i - 1];
    
21.     }
    
22. 
    
23.     for (auto v : e[u]) {
    
24.         if (v == pa)
    
25.             continue;
    
26. 
    
27.         dfs1(v, u);
    
28.         siz[u] += siz[v];
    
29.         dn[u] += siz[v] + dn[v];
    
30.     }
    
31. }
    
32. 
    
33. void dfs2(int u, int pa) {
    
34.     // pa 头顶上的 up[pa] 每个点都要走 pa-> u 一次, 总共 n - siz[pa] 次
    
35.     // pa 先去掉 u 子树的答案, 再加上除了 u 子树的点从 pa -> u 的次数, 即
    
36.     // up[u] = (up[pa] + (n - siz[pa])) + (dn[pa] - dn[u] - siz[u] + siz[pa] - siz[u]);
    
37. 
    
38.     if (u != 1)
    
39.         up[u] = (n - siz[u]) + up[pa] + dn[pa] - dn[u] - siz[u];
    
40. 
    
41.     for (auto v : e[u]) {
    
42.         if (v == pa)
    
43.             continue;
    
44.         dfs2(v, u);
    
45.     }
    
46. }
    
47. 
    
48. int Up(int x, int d) {
    
49.     for (int i = 17; i >= 0; i--) {
    
50.         if ((d >> i) & 1)
    
51.             x = f[x][i];
    
52.     }
    
53.     return x;
    
54. }
    
55. 
    
56. int lca(int u, int v) {
    
57.     if (dep[u] < dep[v])
    
58.         swap(u, v);
    
59. 
    
60.     u = Up(u, dep[u] - dep[v]);
    
61. 
    
62.     if (u == v)
    
63.         return u;
    
64. 
    
65.     for (int i = 17; i >= 0; i--) {
    
66.         if (f[u][i] == f[v][i])
    
67.             continue;
    
68.         u = f[u][i];
    
69.         v = f[v][i];
    
70.     }
    
71. 
    
72.     return f[u][0];
    
73. }
    
74. 
    
75. int dist(int u, int v) { return (dep[u] + dep[v] - dep[lca(u, v)] * 2); }
    
76. 
    
77. int sigma(int x) { return ((1 + x) * x / 2); }
    
78. 
    
79. bool issub(int x, int y) { return (dfn[y] >= dfn[x] && dfn[y] < dfn[x] + siz[x]); }
    
80. 
    
81. int Query_path(int u, int v) {
    
82.     // cut 意为 rt 到路径的最近点
    
83.     int cut = lca(u, rt) ^ lca(v, rt) ^ lca(u, v);
    
84.     int res = 0;
    
85. 
    
86.     res += sigma(dist(u, cut)) + sigma(dist(v, cut));
    
87.     res += dist(rt, cut) * (dist(u, v) + 1);
    
88. 
    
89.     return res;
    
90. }
    
91. 
    
92. int Query_subt(int u) {
    
93.     if (rt == u) {
    
94.         return (up[u] + dn[u]);
    
95.     }
    
96. 
    
97.     if (issub(u, rt)) {
    
98.         int c = Up(rt, dep[rt] - dep[u] - 1);
    
99.         return (up[u] + dn[u] - dn[c] - siz[c] + dist(rt, u) * (n - siz[c]));
    
100.     }
     
101. 
     
102.     return (dn[u] + dist(rt, u) * siz[u]);
     
103. }
     
104. 
     
105. int main() {
     
106.     ios::sync_with_stdio(0);
     
107.     cin.tie(0);
     
108. 
     
109.     freopen("crazy.in", "r", stdin);
     
110.     freopen("crazy.out", "w", stdout);
     
111. 
     
112.     rt = 1;
     
113.     cin >> ID >> n >> m;
     
114.     for (int i = 1; i < n; i++) {
     
115.         int u, v;
     
116.         cin >> u >> v;
     
117.         e[u].emplace_back(v);
     
118.         e[v].emplace_back(u);
     
119.     }
     
120. 
     
121.     dfs1(1, 0);
     
122.     dfs2(1, 0);
     
123. 
     
124.     while (m--) {
     
125.         int op, x, y;
     
126.         cin >> op >> x;
     
127. 
     
128.         if (op == 0) {
     
129.             rt = x;
     
130.         } else if (op == 1) {
     
131.             cin >> y;
     
132.             cout << Query_path(x, y) << '\n';
     
133.         } else {
     
134.             cout << Query_subt(x) << '\n';
     
135.         }
     
136.     }
     
137. 
     
138.     return 0;
     
139. }

复制代码

D - 聪明格
n*n 的棋盘, 每个格子填 1-n 的数, 每行每列没有重复数字, 满足给出的连通块中的数字乘积是连通块的值(mp上的值)
求字典序最小的解

搜索优化: 必须满足每行每列不冲突, 按照连通块排序(从好填到不好填, 按照连通块大小和乘积因数个数排序)

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. typedef pair<int, int> pii;
   
5. 
   
6. const int N = 12;
   
7. const int M = 305;
   
8. const int dx[] = { -1, 0, 1, 0 };
   
9. const int dy[] = { 0, 1, 0, -1 };
   
10. 
    
11. int mp[N][N], n;
    
12. 
    
13. // 首先给连通块排序, 重新分配每个点的搜索顺序, 确定每个点属于的连通块编号
    
14. struct Block {
    
15.     int siz, facs;
    
16.     vector<pii> node;
    
17. } blk[N * N];
    
18. 
    
19. int cnt_blk, id[N][N];
    
20. // 注意 blk 是要排序的, 后面没法直接查询 siz, 所以这里记录一下
    
21. int siz[N * N];
    
22. 
    
23. int Factors(int x) {
    
24.     int res = 0;
    
25.     for (int i = 1; i * i <= x; i++) {
    
26.         if (!(x % i))
    
27.             res++;
    
28.     }
    
29.     return res;
    
30. }
    
31. 
    
32. bool Check(int x, int y) { return (x > 0 && x <= n && y > 0 && y <= n && !id[x][y]); }
    
33. 
    
34. void Explore(int x, int y) {
    
35.     id[x][y] = cnt_blk;
    
36.     blk[cnt_blk].siz++;
    
37.     blk[cnt_blk].node.emplace_back(x, y);
    
38. 
    
39.     for (int i = 0; i < 4; i++) {
    
40.         int nx = x + dx[i], ny = y + dy[i];
    
41.         if (Check(nx, ny) && mp[x][y] == mp[nx][ny]) {
    
42.             Explore(nx, ny);
    
43.         }
    
44.     }
    
45. }
    
46. 
    
47. vector<pii> q;
    
48. int m;
    
49. 
    
50. void Assign_points() {
    
51.     for (int i = 1; i <= n; i++) {
    
52.         for (int j = 1; j <= n; j++) {
    
53.             if (!id[i][j]) {
    
54.                 cnt_blk++;
    
55.                 blk[cnt_blk].facs = Factors(mp[i][j]);
    
56.                 Explore(i, j);
    
57.                 siz[cnt_blk] = blk[cnt_blk].siz;
    
58.             }
    
59.         }
    
60.     }
    
61. 
    
62.     sort(blk + 1, blk + cnt_blk + 1, [](Block& x, Block& y) {
    
63.         if (x.siz == y.siz)
    
64.             return x.facs < y.facs;
    
65.         return x.siz < y.siz;
    
66.     });
    
67. 
    
68.     for (int i = 1; i <= cnt_blk; i++) {
    
69.         for (auto x : blk[i].node) {
    
70.             q.emplace_back(x);
    
71.         }
    
72.     }
    
73. 
    
74.     m = q.size();
    
75. }
    
76. 
    
77. // 现在开始 dfs 填数, 记录答案编号方便回答字典序的要求
    
78. bitset<N> visx[N], visy[N];
    
79. int cnt[N * N], mul[N * N];
    
80. int ans[M][N][N], sum = 0;
    
81. set<int> st;
    
82. 
    
83. bool Check(int x, int y, int a) { return (!visx[x][a] && !visy[y][a] && !((mp[x][y] / mul[id[x][y]]) % a)); }
    
84. 
    
85. void dfs(int pos) {
    
86.     if (pos == m) {
    
87.         st.emplace(sum++);
    
88.         // 一定要注意这里, 当前走成功了之后要给接下来的图赋值
    
89.         // 因为下一次走成功不一定是从头开始走的, 可能某一个小分支就又有了
    
90.         for (int i = 1; i <= n; i++) {
    
91.             for (int j = 1; j <= n; j++) {
    
92.                 ans[sum][i][j] = ans[sum - 1][i][j];
    
93.             }
    
94.         }
    
95.         return;
    
96.     }
    
97. 
    
98.     int x = q[pos].first, y = q[pos].second;
    
99.     int c = id[x][y];
    
100. 
     
101.     cnt[c]++;
     
102.     for (int i = 1; i <= n; i++) {
     
103.         // 能取吗?
     
104.         if (Check(x, y, i)) {
     
105.             mul[c] *= i;
     
106.             // 真能取吗?
     
107.             if (cnt[c] < siz[c] || (cnt[c] == siz[c] && mul[c] == mp[x][y])) {
     
108.                 ans[sum][x][y] = i;
     
109.                 visx[x][i] = 1, visy[y][i] = 1;
     
110. 
     
111.                 dfs(pos + 1);
     
112. 
     
113.                 visx[x][i] = 0, visy[y][i] = 0;
     
114.             }
     
115.             mul[c] /= i;
     
116.         }
     
117.     }
     
118.     cnt[c]--;
     
119. }
     
120. 
     
121. void Solve() {
     
122.     for (int i = 0; i <= n * n; i++) {
     
123.         mul[i] = 1;
     
124.     }
     
125.     dfs(0);
     
126. }
     
127. 
     
128. int Select() {
     
129.     for (int i = 1; i <= n; i++) {
     
130.         for (int j = 1; j <= n; j++) {
     
131.             int minv = 1e9;
     
132. 
     
133.             for (auto v : st) {
     
134.                 minv = min(minv, ans[v][i][j]);
     
135.             }
     
136. 
     
137.             for (auto it = st.begin(); it != st.end();) {
     
138.                 if (ans[*it][i][j] > minv) {
     
139.                     it = st.erase(it);
     
140.                 } else {
     
141.                     it++;
     
142.                 }
     
143.             }
     
144.         }
     
145.     }
     
146. 
     
147.     return *st.begin();
     
148. }
     
149. 
     
150. int main() {
     
151.     ios::sync_with_stdio(0);
     
152.     cin.tie(0);
     
153. 
     
154.     freopen("smart.in", "r", stdin);
     
155.     freopen("smart.out", "w", stdout);
     
156. 
     
157.     cin >> n;
     
158.     for (int i = 1; i <= n; i++) {
     
159.         for (int j = 1; j <= n; j++) {
     
160.             cin >> mp[i][j];
     
161.         }
     
162.     }
     
163. 
     
164.     Assign_points();
     
165.     Solve();
     
166.     int best = Select();
     
167. 
     
168.     cout << sum << '\n';
     
169.     for (int i = 1; i <= n; i++) {
     
170.         for (int j = 1; j <= n; j++) {
     
171.             cout << ans[best][i][j] << ' ';
     
172.         }
     
173.         cout << '\n';
     
174.     }
     
175. 
     
176.     return 0;
     
177. }

复制代码

FishC

鱼油你好，以下是你提到的四道题目的总结与思路解析:

### B - 加号问题
**问题描述**：给定一个长度为 `n` 的数字字符串，每个字符是'0'~'9'。现在有 `k` 个加号，可以插入到字符串中，每个加号只能在两个数字之间。要求所有方案的值之和。

**解题思路**：
1. **计算贡献**：每个数字在表达式中的位置会决定它的贡献，考虑每个数字作为个位、十位等位置的贡献。
2. **使用前缀和与组合数进行预处理**：
   - 用前缀和快速计算子字符串的和。
   - 用组合数计算插入加号的方案数。
3. **复杂度控制**：通过预处理和有效的计算方式，确保算法在 O(n) 或 O(n log n) 的时间内完成。

1. // 伪代码简化
   
2. int calculate_total_value(string s, int k) {
   
3.     int n = s.size();
   
4.     vector<long long> prefix_sum(n + 1, 0);
   
5.     long long total_value = 0;
   
6.    
   
7.     // 计算前缀和
   
8.     for (int i = 1; i <= n; ++i) {
   
9.         prefix_sum[i] = prefix_sum[i - 1] * 10 + (s[i - 1] - '0');
   
10.     }
    
11.    
    
12.     // 计算每个位置的贡献
    
13.     for (int i = 0; i < n; ++i) {
    
14.         long long place_value = 1;
    
15.         for (int j = i; j < n; ++j) {
    
16.             total_value += (s[j] - '0') * place_value;
    
17.             place_value *= 10;
    
18.         }
    
19.     }
    
20.    
    
21.     // 返回总值
    
22.     return total_value;
    
23. }

复制代码

### C - 换根树问题
**问题描述**：给定树和查询，每次询问需要计算某些节点的属性，比如子树的大小、路径上的权值等。

**解题思路**：
1. **分类处理**：每个查询根据性质分类，如子树内部和外部的计算。
2. **双DFS和LCA处理**：通过递归深度优先搜索（DFS），一次计算子树属性，二次根据换根情况重新计算。

1. // 伪代码简化
   
2. int lca(int u, int v) {
   
3.     // 找到u和v的最近公共祖先
   
4. }
   
5. 
   
6. // 距离计算
   
7. int dist(int u, int v) {
   
8.     return dep[u] + dep[v] - 2 * dep[lca(u, v)];
   
9. }
   
10. 
    
11. // 处理每次查询的主函数
    
12. int Query_path(int u, int v) {
    
13.     int cut = lca(u, rt) ^ lca(v, rt) ^ lca(u, v);
    
14.     int res = 0;
    
15.     // 计算路径上的贡献
    
16.     return res;
    
17. }

复制代码

### D - 深度优先搜索填数独
**问题描述**：使用深度优先搜索（DFS）来填数独，确保每个填充操作的正确性。

**解题思路**：
1. **队列填充**：每次选择一个点进行填充，根据可能的选项填入。
2. **搜索顺序设计**：安排好回溯顺序，确保不重复或遗漏，尤其要注意全局变量的影响，每次搜索完成要更新状态。

1. // 伪代码简化
   
2. void dfs_fill_sudoku(...) {
   
3.     if (complete) return;
   
4.     for (int i = 0; i < n; ++i) {
   
5.         // 尝试填入每个可能的数字
   
6.         dfs_fill_sudoku(...);
   
7.     }
   
8. }

复制代码

### 反思与总结
- **性能优化**：在处理大规模数据时，需通过优化算法设计和使用合适的数据结构确保效率。
- **边界条件**：考虑各种输入的极端情况，确保算法能正确处理。
- **调试与测试**：多测试用例覆盖，尤其是边界和特殊情况，防止意外错误。

希望这些简洁的解释对你有所帮助！如果有更多问题或需要进一步的代码实现，请随时提出。

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

简柠啦

harryhan123

666

简柠啦

很cool的阳

磷酸

ooio

曾热爱这世界

&#128076;

zsy0226

/orz/orz

trinityee

厉害了楼主

森林格格屋

谢谢

XiaoMengXin-1

谢谢鱼币