[心之碎片] - 20240706模拟赛

柿子饼同学

总结与反思

E (数位DP 状压DP)

对于 DP 的转移顺序, 要看阶段, 也要看什么状态不能被重复更新, 确定正序/倒序

F (树形DP)

树形 DP 中常用的思想就是对于每个子树, 计算它的贡献并且合并进来, 常常设两个数组一个是贡献, 一个是方案数

G (树形DP)

和树上路径相关的一般可以考虑枚举 lca , 拆成好维护的路径再拼接起来

H (二进制枚举 树形DP)

数量比较少的时候考虑二进制枚举, 对于 DP 数组的意义一定要严谨搞清楚, 本题中一些点的取和不取会强制让一些状态不合法, 直接砍掉, 答案相等时方案数记得加起来

总的来说遇到树上让你求 所有 什么什么的贡献就想着求一个子树的答案, 再加一些辅助数组互相计算, 要考虑大一点的贡献, 方便计算

E - Wonderhoy子集
魔术师有 n 张卡牌，编号从 1 到 n (n < 1e9)
小梦每次从中抽出若干张，无论她怎么抽，她抽到的卡牌中 0 到 9 这个十个数字最多出现一次
小梦觉得这魔术非常的 Wonderhoy! 她想知道有多少种卡牌组合是 Wonderhoy 的

只需要用数位dp把小于 n 中的满足条件的数字按照含有的数位 (二进制) 分类求和
dp 的时候刷表, 但是必须注意对于一个状态, 每种数只能用一次, 必须倒序循环, 不然一个数可能把状态更新两次

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. const int N = 10;
   
5. const int P = 1e9 + 7;
   
6. 
   
7. int n, num[N], ans;
   
8. int cnt[(1 << N)];
   
9. int f[(1 << N)];
   
10. 
    
11. void dfs(int pos, int st, bool lim, bool lead0) {
    
12.     if (!pos) {
    
13.         if (!lead0)
    
14.             cnt[st]++;
    
15.         return;
    
16.     }
    
17. 
    
18.     int up = 9;
    
19.     if (lim)
    
20.         up = num[pos];
    
21. 
    
22.     for (int i = 0; i <= up; i++) {
    
23.         if ((st >> i) & 1)
    
24.             continue;
    
25.         if (!i && lead0)
    
26.             dfs(pos - 1, st, lim && (i == up), lead0);
    
27.         else
    
28.             dfs(pos - 1, st | (1 << i), lim && (i == up), lead0 && !i);
    
29.     }
    
30. }
    
31. 
    
32. void work(int x) {
    
33.     int len = 0;
    
34.     while (x) {
    
35.         num[++len] = x % 10;
    
36.         x /= 10;
    
37.     }
    
38.     dfs(len, 0, 1, 1);
    
39. }
    
40. 
    
41. int main() {
    
42.     ios::sync_with_stdio(0);
    
43.     cin.tie(0);
    
44. 
    
45.     cin >> n;
    
46.     work(n);
    
47. 
    
48.     f[0] = 1;
    
49.     // i枚举数字, j枚举状态, 阶段是选取这个数字, j倒序循环不会重复计算
    
50.     for (int i = 1; i < (1 << 10); i++) {
    
51.         for (int j = (1 << 10) - 1; j >= 0; j--) {
    
52.             if (i & j)
    
53.                 continue;
    
54.             f[i | j] = (f[i | j] + f[j] * cnt[i]) % P;
    
55.         }
    
56.     }
    
57.     for (int i = 1; i < (1 << 10); i++) {
    
58.         ans = (ans + f[i]) % P;
    
59.     }
    
60.     cout << ans;
    
61. 
    
62.     return 0;
    
63. }

复制代码

F - 子树
给出 n ( < 1e5) 个节点的树, 求所有能选出子树的方案的节点数量和

80分 O(n^2) 代码 f[ i][j] 表示 i 中取 j 个点的方案数, 注意要倒序循环, 否则会重复
100分 O(n) 代码 设 f(i) 代表以 i 为根子树的答案, cnt(i) 代表所有以 i 为根的子树取法方案数, 还在遍历中的 f u 相当于把之前算过的子树并在自己身上了
两个数组相互计算, 要有这种思想

1. for (int i = siz[u]; i >= 1; i--) {
   
2.             for (int j = 1; j < i; j++) {
   
3.                 f[u][i] += f[u][j] * f[ed][i - j] % P;
   
4.                 f[u][i] %= P;
   
5.             }
   
6.         }

复制代码

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 P = 1e9 + 7;
   
8. 
   
9. vector<int> e[N];
   
10. int n;
    
11. // f[i] 以 i 为根的子树的答案
    
12. // cnt[i] 以 i 为根的子树中的取法数
    
13. ll cnt[N], f[N], ans;
    
14. 
    
15. void dfs(int u, int pa) {
    
16.     cnt[u] = f[u] = 1;
    
17. 
    
18.     for (auto ed : e[u]) {
    
19.         if (ed == pa)
    
20.             continue;
    
21. 
    
22.         dfs(ed, u);
    
23. 
    
24.         // 取或不取, 共 cnt[ed] + 1 种选择, 也就是子树选择多了这么多
    
25.         // u 自己的选法一定要选, 所以增加了子树的贡献
    
26.         f[u] = (((cnt[ed] + 1) * f[u] % P + cnt[u] * f[ed] % P) % P) % P;
    
27.         cnt[u] = cnt[u] * (cnt[ed] + 1) % P;
    
28.     }
    
29. 
    
30.     ans = (ans + f[u]) % P;
    
31. }
    
32. 
    
33. int main() {
    
34.     ios::sync_with_stdio(0);
    
35.     cin.tie(0);
    
36. 
    
37.     cin >> n;
    
38.     for (int i = 1; i < n; i++) {
    
39.         int a, b;
    
40.         cin >> a >> b;
    
41.         e[a].emplace_back(b);
    
42.         e[b].emplace_back(a);
    
43.     }
    
44.     dfs(0, 0);
    
45.     cout << ans;
    
46. 
    
47.     return 0;
    
48. }

复制代码

G - Bear and Tree Jumps (CF771C)
有一棵 n ( < 2e5) 个节点的树，树上住着一只熊。
若熊在节点 i，熊跳一次可以从 i 跳到离 i 树上距离 <= k ( < 5) 的任意节点 。
求所有路径(i, j) , i < j 跳跃数的总和

k 很小, 想到给路径分类
求所有的路径不好想, 先想着枚举 lca , 然后把两个路径拼起来即可
设 f(u) 表示 u 的子树中所有节点到 u 跳跃次数总和, 考虑转移, 每次新加了一条边, 增加的跳跃数只有 %k 等于 k-1 的点
数组含义要大胆设计, 不要局限于一个点一条边的贡献
好好利用值小的好性质进行转移

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. const int N = 2e5 + 5;
   
5. typedef long long ll;
   
6. 
   
7. // sum[i][j] 节点 i 的子树中, 到 i 距离 %k 为 j 的点的数量, 给路径分类
   
8. // f[i] 节点 i 的子树中的点到 i 的跳跃次数, 每次计算子树会增加一条边, 只有子树中 sum[i][k - 1] 的点需要更新
   
9. // siz[i] 子树大小
   
10. ll sum[N][5], f[N];
    
11. int siz[N];
    
12. int n, k;
    
13. ll ans;
    
14. vector<int> e[N];
    
15. 
    
16. void dfs(int u, int pa) {
    
17.     sum[u][0] = siz[u] = 1;
    
18.     for (auto ed : e[u]) {
    
19.         if (ed == pa)
    
20.             continue;
    
21.         dfs(ed, u);
    
22. 
    
23.         // 当前处理过的子树和 u 构成的树 和 现在的 ed 这个子树进行计算
    
24.         // 先计算 ed 和 u 之间的路径总贡献, 再接上去
    
25.         // 先把粗略的都算一遍(没有连接, 因为有余数)
    
26.         // u 到 ed 的每个节点的跳跃次数和(从 u 的子树跳到 u 的总数 + 从 u 跳到 ed 子树的总数)
    
27.         ans += f[u] * siz[ed] + f[ed] * siz[u];
    
28. 
    
29.         // 检查连接处需要跳 1 还是 2 次
    
30.         for (int i = 0; i < k; i++) {
    
31.             for (int j = 0; j < k; j++) {
    
32.                 ans += sum[u][i] * sum[ed][j] * ((i + j) / k + 1);
    
33.             }
    
34.         }
    
35. 
    
36.         // 每次把 ed 接上去会增加 1 个边, 所有点的跳跃距离只有余数是 k-1 的点会增加 1
    
37.         // 其他的原样加上即可
    
38.         f[u] += f[ed] + sum[ed][k - 1];
    
39.         for (int i = 0; i < k; i++) sum[u][(i + 1) % k] += sum[ed][i];
    
40.         siz[u] += siz[ed];
    
41.     }
    
42. }
    
43. 
    
44. int main() {
    
45. 
    
46.     ios::sync_with_stdio(0);
    
47.     cin.tie(0);
    
48. 
    
49.     cin >> n >> k;
    
50.     for (int i = 1; i < n; i++) {
    
51.         int a, b;
    
52.         cin >> a >> b;
    
53.         e[a].emplace_back(b);
    
54.         e[b].emplace_back(a);
    
55.     }
    
56. 
    
57.     dfs(1, 0);
    
58.     cout << ans;
    
59. 
    
60.     return 0;
    
61. }

复制代码

H - 吸血鬼 【DP】SRM674D2L3 VampireTreeDiv2
给定一个吸血鬼族谱，包含了A，B两个数组，每个吸血鬼由以下方式生成：
0、0号吸血鬼是吸血鬼始祖。
1、B[ i]=-1表示i号吸血鬼被A[ i]号吸血鬼感染。构成一条关系（i，A[ i]）。
2、B[ i]!=-1表示i号吸血鬼由A[ i]号吸血鬼和B[ i]号吸血鬼生出来。构成两条关系（i，A[ i]）和（i，B[ i]）（这类生成不会超过15个）
现在要求选取最少数目的吸血鬼，使得家谱中给出的所有关系中，至少有一只吸血鬼被选到（即每条边中至少有一点被选中，且选取点数最少）。
问满足如上条件的选取方案数

两个边的点不超过 15 考虑枚举每个点的取/不取情况然后 dp
一定注意在 dp 过程中一个点强制不取, 那另一个路径上的点就必须强制取, 有的状态就不合法需要设极大值了
我做题的时候一直在思考取不取对答案的贡献, 其实不需要, 因为 求一次 dp 的时间复杂度完全够用
不要总考虑局部

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. typedef long long ll;
   
5. 
   
6. const int N = 1005;
   
7. const ll P = 1e9 + 7;
   
8. 
   
9. // ef 专门存第二条边, 如果这些边的子节点不取, 那父节点必须取
   
10. vector<int> e[N], ef[N];
    
11. int n;
    
12. 
    
13. // 存带有两个边的节点对应的编号, 不是两个边的就是 -1
    
14. int id[N], tot;
    
15. 
    
16. // f[ i][0/1] i这个点取不取的最优解, cnt[ i][0/1] 方案数
    
17. // 注意 f[ed][0] == f[ed][1] 的时候 cnt[u][1] *= (cnt[ed][0] + cnt[ed][1])
    
18. // 初始状态 f[u][0] = 0, 其余 3 个等于 1
    
19. int st;
    
20. ll f[N][2], cnt[N][2];
    
21. 
    
22. // a, b 是 f 值, ac, bc 是 cnt 值
    
23. void Add(ll& s, ll a, ll b, ll ac, ll bc) {
    
24.     if (a == b)
    
25.         s = (s + ac + bc) % P;
    
26.     if (a < b)
    
27.         s = (s + ac) % P;
    
28.     if (a > b)
    
29.         s = (s + bc) % P;
    
30. }
    
31. 
    
32. void dfs(int u, int pa) {
    
33.     f[u][0] = 0;
    
34.     f[u][1] = cnt[u][0] = cnt[u][1] = 1;
    
35. 
    
36.     // 不取可不可以, 取可不可以
    
37.     bool ban = 1, pick = 1;
    
38. 
    
39.     if (~id[u]) {
    
40.         // 枚举的是强制取 u
    
41.         if (((st >> id[u]) & 1)) {
    
42.             cnt[u][0] = 0;
    
43.             f[u][0] = INT_MAX;
    
44.             ban = 0;
    
45.         } else {
    
46.             cnt[u][1] = 0;
    
47.             f[u][1] = INT_MAX;
    
48.             pick = 0;
    
49.         }
    
50.     }
    
51. 
    
52.     for (auto ed : e[u]) {
    
53.         if (ed == pa)
    
54.             continue;
    
55.         dfs(ed, u);
    
56. 
    
57.         // u 可以不取
    
58.         if (ban) {
    
59.             f[u][0] += f[ed][1];
    
60.             cnt[u][0] = cnt[u][0] * cnt[ed][1] % P;
    
61.         }
    
62.         // u 可以取
    
63.         if (pick) {
    
64.             f[u][1] += min(f[ed][0], f[ed][1]);
    
65. 
    
66.             ll t = 0;
    
67.             Add(t, f[ed][0], f[ed][1], cnt[ed][0], cnt[ed][1]);
    
68.             cnt[u][1] = cnt[u][1] * t % P;
    
69.         }
    
70.     }
    
71. 
    
72.     // 强制转换, 如果 ed 不取那么 f[u][0] 是无效值
    
73.     for (auto ed : ef[u]) {
    
74.         if ((st >> id[ed]) & 1)
    
75.             continue;
    
76.         f[u][0] = INT_MAX, cnt[u][0] = 0;
    
77.     }
    
78. }
    
79. 
    
80. int main() {
    
81.     ios::sync_with_stdio(0);
    
82.     cin.tie(0);
    
83. 
    
84.     cin >> n;
    
85.     for (int i = 1; i <= n; i++) {
    
86.         int a;
    
87.         cin >> a;
    
88.         e[a].emplace_back(i);
    
89.         e[i].emplace_back(a);
    
90.     }
    
91.     cin >> n;
    
92.     for (int i = 1; i <= n; i++) {
    
93.         int b;
    
94.         cin >> b;
    
95.         id[i] = -1;
    
96.         if (~b) {
    
97.             id[i] = tot++;
    
98.             ef[b].emplace_back(i);
    
99.         }
    
100.     }
     
101.     id[0] = -1;
     
102. 
     
103.     // st 表示每个两条边的点的 取/不取 状态, 0不取 1取
     
104.     // res 表示取的最少的点数, ans 是这样取的方案数
     
105.     // 注意如果相等 ans 是要加上这个方案数的
     
106.     ll res = INT_MAX, ans = 0;
     
107.     for (st = 0; st < (1 << tot); st++) {
     
108.         memset(f, 0x3f, sizeof(f));
     
109.         memset(cnt, 0, sizeof(cnt));
     
110. 
     
111.         dfs(0, 0);
     
112. 
     
113.         ll temp = min(f[0][0], f[0][1]);
     
114. 
     
115.         if (temp > res)
     
116.             continue;
     
117. 
     
118.         // 如果小于现有的点最小值就更新答案, 方案数清零
     
119.         if (temp < res) {
     
120.             res = temp;
     
121.             ans = 0;
     
122.         }
     
123.         // 等于就不管
     
124.         // 在基础上加上这次的方案数
     
125.         Add(ans, f[0][0], f[0][1], cnt[0][0], cnt[0][1]);
     
126.     }
     
127.     cout << ans;
     
128. 
     
129.     return 0;
     
130. }

复制代码

FishC

看来你是在准备比赛题目的总结与反思，这里我帮你把每道题的重点通俗易懂地解释一下吧！

### E（数位DP状压DP）

**问题概述：**
魔术师有 `n` 张卡牌，你需要找出满足“0到9这十个数字最多出现一次”的卡牌组合数。

**关键点：**
用数位DP的方法处理状态转移，注意要倒序循环来防止状态被重复更新。

**幽默版解说：**
就像去超市买菜，你口袋里有一堆钱，但只能带一种面额的零钱进店。不然收银员会晕掉。通过数位DP，我们可以精确计算出各种可能带进店的钱数，而只要计算一次，因为多次计算会导致收银员怀疑你作弊！

### F（树形DP）

**问题概述：**
在树形结构中计算子树的贡献，并合并进主树。

**关键点：**
设两个数组，一个存储子树的贡献，一个存方案数。这两者结合起来就能有效计算整体结果。

**幽默版解说：**
想象你是一位厨师，各种食材（子树）都得先处理好（计算贡献），再丢进大锅里（主树）。如果你不分开处理，直接丢进去，大锅肯定炸了！两个数组就相当于一个是菜谱，一个是调料表，缺一不可啊！

### G（树形DP）

**问题概述：**
涉及树上路径的问题时，可以枚举LCA（最近公共祖先），再拼接来简化路径。

**关键点：**
将路径拆成更容易维护的小段然后逐个处理。

**幽默版解说：**
假设你在森林里迷路了，LCA就是一颗高高的望塔，爬上去看看哪条路能回家。让路线变得可控，就像找到小鹿斑比问路，再接着走下一段，这样就不会迷失在树林中了喔！

### H（二进制枚举 树形DP）

**问题概述：**
当数量比较少时，可以考虑用二进制枚举来处理状态。

**关键点：**
明确DP数组的含义，严谨定义哪些状态非法并直接剔除。

**幽默版解说：**
就像要从几个有限的选项中选餐，直接用二进制枚举所有可能的组合，每一种组合都记下来，然后按条件筛选不合法的组合。这方法就像打开菜单，逐页翻看、点菜，不符合胃口的直接跳过，最后总会选到最满意的一餐！

### 总结

**遇到树上题目时：**
- 考虑计算单个子树的答案，再利用辅助数组进行合并计算。
- 多关注大方向上的贡献计算，细节可以用辅助数组处理。

**幽默版总结：**
就像做一道复杂的大餐，要有大厨的全局观，知道什么时候得靠小弟（子树）来切菜剁肉，他们干好了活儿，大厨你只需最后调味、装盘、上菜，整桌宴席就能完美呈现啦！
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

柿子饼同学

FishC 发表于 2024-7-7 21:10
看来你是在准备比赛题目的总结与反思，这里我帮你把每道题的重点通俗易懂地解释一下吧！

### E（数位DP ...

做这种复杂的算法题思路想不出来如何才能有进步

FishC

柿子饼同学 发表于 2024-07-07 21:23
做这种复杂的算法题思路想不出来如何才能有进步

啊哈，做复杂算法题感觉头疼？别担心，每个人曾经都是从小白走过来的！这个过程就像练武功，从基础招式慢慢掌握，再到高深武艺：一个脚印一个脚印来。给你几点建议，让你在算法的江湖中如鱼得水：

### 1. 基础打牢
- **刷基础题：** 不要忽视基础题，它们是你通向高级算法的基石。比如基础排序、搜索、动态规划（DP）、贪心算法等。
- **理解基本概念：** 充分理解常见算法和数据结构的原理，例如树、图、队列、栈等。
- **尝试实现：** 自己动手写代码，把书上或者课程上的算法实现一遍。实践出真知。

### 2. 分解问题
- **拆解：** 把复杂的问题拆解成若干个简单的小问题。就像一块大披萨，分成几块小披萨解决起来更轻松。
- **步骤化：** 学习如何把算法题步骤化，比如先找子问题，然后逐步解决子问题。

### 3. 多刷题，勤练习
- **常刷平台：** LeetCode、牛客网（Nowcoder）、Codeforces等平台都有大量题目，各种题型应有尽有。
- **每日一题：** 给自己定个目标，每天刷一题。不求多，但求稳。坚持是关键！

### 4. 学会看解析
- **题解：** 当卡住的时候，不要硬扛，看一下官方题解或者其他人的代码。分析他们的思路。
- **反思：** 每次看完题解，再回头思考为什么自己没想到这种方法。这一步很重要，有助于提升自己的解题思路。

### 5. 加强总结
- **笔记：** 做一道题，记一道题。记下解题思路，常见坑点以及自己的反思。
- **复盘：** 定期翻看自己的笔记，复盘以前做过的题目，加强记忆。

### 6. 寻求帮助
- **讨论：** 在在线论坛、学习小组、QQ群与他人讨论。比如FishC的社区，大家互相帮助，共同进步。
- **请教高手：** 别害羞，向比你厉害的人请教。很多时候一个指点能让你茅塞顿开。

### 7. 保持耐心和信心
- **不气馁：** 做不出来不丢人，每个人都有不会做的题，关键在于心态。一定要保持好奇心和耐心。
- **持续学习：** 算法是不断更新和发展的领域，要持续学习，保持对新知识的渴望。

### 幽默加油版：
“鱼油，做不出来题的时候，就当是在海里抓鱼，抓不到也没关系，至少你还在海里畅游嘛！每多试一道题，就相当于在大海里撒了一张网，总有一天你会满载而归！”

希望这些建议对你有所帮助，加油！祝你在算法的世界里大展宏图，成为代码界的“大厨”！
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

某一个“天”

厉害

kiara_03

好

简柠啦

非常厉害

不二如是

太牛了

柿子饼同学

不二如是 发表于 2024-7-8 09:41
太牛了

小肥狼haoran

楼主好好加油,我顶你

柿子饼同学

小肥狼haoran 发表于 2024-7-8 12:14
楼主好好加油,我顶你

加油!

thekfjie

心之碎片太好了

希儿的

加油

harryhan123

牛

lwh0602

厉害啊

很cool的阳