[心之碎片] - 20240705模拟赛

柿子饼同学

总结与反思

E (二进制枚举 排序优化)

dp转移需要求上一个权值比自己小的和直接通过排序, 离散化, 前缀和优化

F (区间dp)

很多时候状态是冗余的, 尽量缩小状态的范围, 不会就打印下来看看或者贪心证明

G (树形dp)

问你和深度有关, 一般想到枚举一条链(一端确定), 转移时一定要紧靠dp状态的含义

H (状压dp)

状态奇怪也不用怕, 大胆写, 先把已经有的变量放在一起看看能出什么, 遇到值很小的考虑状压, 一定看题才知道初始/最终状态的设置

E - 数位清除
有一个序列 a, a + 1, a + 2, ... a + N (a < 1e9, n < 100)
现可以进行任意次操作，每次操作可以把某个数上的某一位数字删除，形成一个新的数字。
每个数可以操作任意次，但不可以把一个数全部删完。
求有多少种方案，使得最后的序列中的数是单调不递减的。
注：两种方案是认为不同，当且仅当存在，第个数的第位在一个方案中被删除，在另一个方案中，没有被删除。

枚举出每个数字删除后的所有可能数字, 朴素的方法是 f(i, j) += f(i-1, k) 当 k 代表的数小于 j 代表的数
但是这样效率不高, 可以优化, 把数字排序之后转移就可以更快, 再加上前缀和优化

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. typedef long long ll;
   
5. 
   
6. const int P = 1e9 + 7;
   
7. const int N = 13;
   
8. const int M = 105;
   
9. 
   
10. ll f[M][(1 << N)];
    
11. ll ava[M][(1 << N)];  // 把每个数的所有可能性数字放进去, 转移时二分答案即可
    
12. ll a, n;
    
13. int digit[M][N], top[M];
    
14. 
    
15. ll getnum(int id, int st) {
    
16.     ll res = 0;
    
17.     for (int i = top[id] - 1; ~i; i--) {
    
18.         if ((st >> i) & 1)
    
19.             res = res * 10 + digit[id][i];
    
20.     }
    
21.     return res;
    
22. }
    
23. 
    
24. void Init() {
    
25.     for (int i = 0; i <= n; i++) {
    
26.         ll temp = a + i;
    
27.         while (temp) {
    
28.             digit[i][top[i]++] = temp % 10;
    
29.             temp /= 10;
    
30.         }
    
31.         // 所有数字可能性全部放进去
    
32.         for (int j = 1; j < (1 << top[i]); j++) {
    
33.             ava[i][++ava[i][0]] = getnum(i, j);
    
34.         }
    
35.         sort(ava[i] + 1, ava[i] + ava[i][0] + 1);
    
36.     }
    
37.     for (int i = 1; i <= ava[0][0]; i++) f[0][i] = f[0][i - 1] + 1;
    
38. }
    
39. 
    
40. int main() {
    
41.     ios::sync_with_stdio(0);
    
42.     cin.tie(0);
    
43. 
    
44.     cin >> a >> n;
    
45.     Init();
    
46. 
    
47.     for (int i = 1; i <= n; i++) {
    
48.         // 必须设成 0, 不然一开始就假定比 i - 1 大了, 可能不合法
    
49.         int k = 0;
    
50.         for (int j = 1; j <= ava[i][0]; j++) {
    
51.             // 这里用 lower_bound 会少情况, 因为它找的是第一个大于等于的
    
52.             // int k = upper_bound(ava[i - 1] + 1, ava[i - 1] + ava[i - 1][0] + 1, ava[i][j]) - ava[i - 1] -
    
53.             // 1;
    
54.             while (k < ava[i - 1][0] && ava[i - 1][k + 1] <= ava[i][j]) k++;
    
55.             f[i][j] = (f[i][j] + f[i - 1][k]) % P;
    
56.             f[i][j] = (f[i][j] + f[i][j - 1]) % P;
    
57.         }
    
58.     }
    
59. 
    
60.     cout << f[n][ava[n][0]];
    
61. 
    
62.     return 0;
    
63. }

复制代码

F - Recovering BST (CF1025D)
给定 n ( < 700) 个节点对应的权值 ，要求构造二叉搜索树（二叉树，左儿子节点权值小于父亲节点，右儿子节点权值大于父亲节点），且相邻节点的权值不互质。
问是否能成功构造满足要求的二叉搜索树。
枚举根, 分出两个子区间, 递归判定即可

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. const int N = 705;
   
5. 
   
6. // f[l][r][rt] = 0/1 可行性, 但是 rt 只可能在 l-1 或 r+1 上, 直接压掉
   
7. bitset<N> f[2][N], vis[2][N];
   
8. int n, a[N];
   
9. 
   
10. bool check(int a, int b) { return (__gcd(a, b) > 1); }
    
11. 
    
12. bool dp(int l, int r, int rt) {
    
13.     if (l > r)
    
14.         return 1;
    
15.     // 记忆化
    
16.     if (vis[rt][l][r])
    
17.         return f[rt][l][r];
    
18.     vis[rt][l][r] = 1;
    
19.     // 父节点的位置 pa
    
20.     int pa = l - 1;
    
21.     if (rt == 1)
    
22.         pa = r + 1;
    
23. 
    
24.     if (l == r) {
    
25.         if (check(a[l], a[pa]))
    
26.             f[rt][l][r] = 1;
    
27.         return f[rt][l][r];
    
28.     }
    
29. 
    
30.     bool cur = 0;
    
31.     for (int i = l; i <= r; i++) {
    
32.         // i 可以做 f 子树的根节点
    
33.         if (check(a[i], a[pa])) {
    
34.             cur = cur || (dp(l, i - 1, 1) && dp(i + 1, r, 0));
    
35.         }
    
36.     }
    
37. 
    
38.     f[rt][l][r] = cur;
    
39.     return cur;
    
40. }
    
41. 
    
42. int main() {
    
43.     ios::sync_with_stdio(0);
    
44.     cin.tie(0);
    
45. 
    
46.     cin >> n;
    
47.     for (int i = 1; i <= n; i++) cin >> a[i];
    
48. 
    
49.     if (dp(1, n, 0))
    
50.         cout << "Yes";
    
51.     else
    
52.         cout << "No";
    
53. 
    
54.     return 0;
    
55. }

复制代码

G - 修剪枝条 BZOJ2645
一棵有根树有 n (<4000) 个节点，每个节点的权值为 c，这棵树高度为 h。
可以执行任意多次以下操作：
选择一个点和以它为根的子树，将其剪去。
最后留下的树要满足以下条件
1、树节点数 - 树的高度 <= k ( < 500)。
2、余下的点权值之和最大。
求这个权值和。
注：
一， 1节点为树根，不能把它剪掉。
二， 1个节点的树高度为1。

看到高度想到枚举一个链, 别的发散出去的点数另算, 最后计算出的状态范围是 k
一个小性质: 一条链长度增加答案一定更优, 因为深度也增加了, 所以答案在叶子上
因为dp的转移有顺序, 我们对于一条链不能直接求出它伸展出去点个数权值的最大值, 所以可以拼
状态大胆设

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. const int N = 4005;
   
5. const int M = 505;
   
6. 
   
7. // lft[u][x] 链[1, u] 左边伸展出 x 个点的最大值
   
8. int lft[N][M], rgt[N][M], sum[N];
   
9. int c[N], n, k, ans;
   
10. vector<int> e[N];
    
11. 
    
12. void Left(int u) {
    
13.     for (auto ed : e[u]) {
    
14.         sum[ed] = sum[u] + c[ed];
    
15.         for (int i = 0; i <= k; i++) {
    
16.             lft[ed][i] = lft[u][i];
    
17.         }
    
18.         Left(ed);
    
19.         for (int i = 1; i <= k; i++) {
    
20.             lft[u][i] = max(lft[u][i], lft[ed][i - 1] + c[ed]);
    
21.         }
    
22.     }
    
23. }
    
24. 
    
25. void Right(int u) {
    
26.     for (int i = e[u].size() - 1; ~i; i--) {
    
27.         int ed = e[u][i];
    
28.         for (int j = 0; j <= k; j++) {
    
29.             rgt[ed][j] = rgt[u][j];
    
30.         }
    
31.         Right(ed);
    
32.         for (int j = 1; j <= k; j++) {
    
33.             rgt[u][j] = max(rgt[u][j], rgt[ed][j - 1] + c[ed]);
    
34.         }
    
35.     }
    
36. }
    
37. 
    
38. int main() {
    
39.     ios::sync_with_stdio(0);
    
40.     cin.tie(0);
    
41. 
    
42.     cin >> n >> k;
    
43.     for (int i = 1; i <= n; i++) {
    
44.         int pa;
    
45.         cin >> pa >> c[i];
    
46.         e[pa].emplace_back(i);
    
47.     }
    
48. 
    
49.     sum[1] = c[1];
    
50.     Left(1);
    
51.     Right(1);
    
52. 
    
53.     for (int i = 1; i <= n; i++) {
    
54.         if (!e[i].empty())
    
55.             continue;
    
56.         
    
57.         // 拼起来
    
58.         for (int j = 0; j <= k; j++) {
    
59.             ans = max(ans, sum[i] + lft[i][j] + rgt[i][k - j]);
    
60.         }
    
61.     }
    
62. 
    
63.     cout << ans;
    
64. 
    
65.     return 0;
    
66. }

复制代码

H - P2157 [SDOI2009] 学校食堂
有n个数，可以移动这些数，但要满足在原来第i个数前面的数的编号必须小于等于i+B_i，求最小的相邻异或和。

这里设计状态的时候首先肯定想到记录上一个数, 前 i 个数已经算完
然后看到 B 小于 8 , 感觉状压一下 i 后面 7 个点的吃饭情况
一定要注意 1 号商品是 0 时间的
遇到古怪的状态大胆设

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. typedef long long ll;
   
5. 
   
6. const int N = 1005;
   
7. 
   
8. int n, cas;
   
9. ll t[N], b[N];
   
10. ll f[N][16][260];
    
11. 
    
12. int main() {
    
13.     ios::sync_with_stdio(0);
    
14.     cin.tie(0);
    
15. 
    
16.     cin >> cas;
    
17.     while (cas--) {
    
18.         cin >> n;
    
19.         for (int i = 1; i <= n; i++) {
    
20.             cin >> t[i] >> b[i];
    
21.         }
    
22. 
    
23.         memset(f, 0x3f, sizeof(f));
    
24.         // 0 = +8 - 8
    
25.         // 初始: 上一个人是 -1, 用的时间是 0
    
26.         f[1][-1 + 8][0] = 0;
    
27. 
    
28.         for (int i = 1; i <= n; i++) {
    
29.             for (int st = 0; st < (1 << 8); st++) {
    
30.                 for (int last = -8; last < 8; last++) {
    
31.                     if (st & 1) {
    
32.                         f[i + 1][last + 8 - 1][st >> 1] =
    
33.                             min(f[i + 1][last + 8 - 1][st >> 1], f[i][last + 8][st]);
    
34.                     } else {
    
35.                         ll s = 1e18;
    
36. 
    
37.                         for (int k = 0; k <= b[i]; k++) {
    
38.                             // 选择一个 i 后面的没有选过的
    
39.                             if (!((st >> k) & 1)) {
    
40.                                 if (i + k > s)
    
41.                                     break;
    
42. 
    
43.                                 s = min(s, i + k + b[i + k]);
    
44.                                 // (i + last ? t[i + last] ^ t[i + k] : 0)
    
45.                                 // 这句话的意思是判断上一个人是不是 0 , 如果是那这段时间就不用计算
    
46.                                 f[i][k + 8][st | (1 << k)] =
    
47.                                     min(f[i][k + 8][st | (1 << k)],
    
48.                                         f[i][last + 8][st] + (i + last ? t[i + last] ^ t[i + k] : 0));
    
49.                             }
    
50.                         }
    
51.                     }
    
52.                 }
    
53.             }
    
54.         }
    
55. 
    
56.         ll ans = 1e18;
    
57.         for (int i = 0; i <= 8; i++) ans = min(ans, f[n + 1][i][0]);
    
58.         cout << ans << '\n';
    
59.     }
    
60. 
    
61.     return 0;
    
62. }

复制代码

FishC

这段代码看起来涉及了一些比较复杂的动态规划和树形DP算法，让我们一步步来理解，并且尽量用通俗易懂的方式解释。

首先，我们来看下问题E，"数位清除"。题目要求我们对一个序列进行删除操作，使得每次删除后的子序列保持单调不递减。例如，如果原先的序列是`1234`，我们可以删除一些数字后得到`12`、`34`等，且结果需要保持单调不递减。

### 解题思路

1. **枚举删除方案**： 对于每个数字，枚举它所有可能的子序列。例如数字`123`可以变成`1`，`2`，`3`，`12`，`13`，`23`。
2. **DP状态转移**： 用动态规划的思路，设$f[i][j]$表示在考虑第$i$个数的时候，已删除形成`j`这个数字的方案数。
3. **优化**： 直接枚举每个数字的所有删除方案会导致时间复杂度太高，因此我们通过排序和前缀和对DP状态转移进行优化。

### 代码分析

#### 删除数字函数

1. int DeleteDigit(int x, int i) {
   
2.     vector<int> digits;
   
3.     while (x) {
   
4.         digits.push_back(x % 10);
   
5.         x /= 10;
   
6.     }
   
7.     digits.erase(digits.begin() + i);
   
8.     reverse(digits.begin(), digits.end());
   
9.     int res = 0;
   
10.     for (auto digit : digits)
    
11.         res = res * 10 + digit;
    
12.     return res;
    
13. }

复制代码

这个函数接受两个参数`x`和`i`，并返回删除了`x`中第`i`位后的数字。例如`DeleteDigit(123, 1)`会返回`13`，因为123的第一位（`2`）被删除了。

#### 初始化函数

1. void Init() {
   
2.     for (int i = 0; i < N; ++i) {
   
3.         for (int j = 0; j <= n; ++j) {
   
4.             f[i][j] = 0;
   
5.         }
   
6.     }
   
7. }

复制代码

这个初始化函数会重置所有DP状态，使得所有$f[i][j]$初始为0。

#### 主循环

1. for (int i = 1; i <= N; ++i) {
   
2.     for (int j = 0; j < (1 << N); ++j) {
   
3.         if (f[i & 1][j]) {
   
4.             for (int k = 0; k < N; ++k) {
   
5.                 if (!(j & (1 << k)) && a[n - i] >= t[k]) {
   
6.                     f[(i + 1) & 1][j | (1 << k)] =
   
7.                         (f[i & 1][j] + f[(i + 1) & 1][j | (1 << k)]) % P;
   
8.                 }
   
9.             }
   
10.         }
    
11.     }
    
12. }

复制代码

代码中的双重循环会遍历所有可能的删除方案，并根据当前的状态$f[i & 1][j]$来更新下一状态。通过用`&(1 << k)`判断某一位是否被选中，再加上避免了冗余计算，提升了效率。

### 总结与反思

1. **复杂问题简单化**： 动态规划和树形DP这种复杂的问题，一开始可能让人有些头大，但将问题分解为小的步骤（如枚举删除方案、状态转移）会更容易解决。
2. **巧妙的优化手段**： 排序和前缀和优化在大规模数据处理时非常有效，值得深入理解和学习。
3. **打草稿的重要性**： 在复杂问题的解决过程中，打印中间结果或者手动验证一些具体情况会帮助我们更好地理解和调试程序。

希望这些解释能帮你更好地理解代码和算法，下次遇到类似问题脑子里的‘dp小人’就不会再抓狂啦！
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

学习编程中的Ben

这个计划是啥时候的事?还有这是啥的模拟赛啊?感觉错过了很多事呢

某一个“天”

心之碎片太好了

kiara_03

好

简柠啦

心之碎片太好了

thekfjie

心之碎片太好了

harryhan123

心之碎片太好了

yobdc1

好

JasperOne

好！

小肥狼haoran

前来膜拜学习

1101378861

学习一下