鱼C论坛

 找回密码
 立即注册
查看: 2256|回复: 12

[心之碎片] - 计数dp综合

[复制链接]
回帖奖励 6 鱼币 回复本帖可获得 3 鱼币奖励! 每人限 1 次
发表于 2024-8-29 15:56:39 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 柿子饼同学 于 2024-8-29 15:59 编辑
各种计数... 但是没有那么难
对于描述状态要细分, 少了什么就加, 注意别重复
首先确定阶段, 即如何完成任务
然后描述状态分类, 转移
计数类问题要想哪些和哪些是无关的, 可以一起算
对于状态的变化, 考虑是由哪些操作变出来的, 提供转移的思路
正难则反
总情况数减去不合法情况数
计算贡献

A - 网格删边
f[i, j, 0/1] 前 i 列, 删除 j 个边, 是否连通的方案数

B - 染色边
发现只有同对角线上的才会互相影响, 每个对角线是并列的
于是预处理每个对角线长度的方案数, 然后预处理乘积


C - 分段 i

D - 神秘密码

状压

E - 树上连通块个数
给定一棵树
记 f(i, j) 表示所有编号在区间 [i, j] 的点在树上形成的联通块的个数。
对于所有的区间[i. j]的f(i, j)求和

一个结论, 一些点构成的连通块个数等于 这些点的个数 - 这些点直接相互连边的个数
然后先求总数, 对于每条边减去贡献

  1. cin >> n;

  2. // 假设没有边, 那么所有的 f 的和
  3. for (int i = 1; i <= n; i++) {
  4.     ans += 1ll * (n - i + 1) * i;
  5. }
  6. // 有边了, 减去一些东西
  7. for (int i = 1; i < n; i++) {
  8.     ll u, v;
  9.     cin >> u >> v;
  10.     if (u > v)
  11.         swap(u, v);

  12.     ans -= u * (n - v + 1);
  13. }
  14. cout << ans;
复制代码


F - 灵魂之树的三重考验
高维的运算可以由低维的堆出来
  1. // 现在对于一个点 u, 她的子树 (包括她的父节点上面的那个树) 大小分别是 a[1]...a[n]
  2. // f[i] 表示第 3 个数是 a[i], 前面两个数是 x, y (在 1...i-1 选) 的和
  3. // 不好求, 降维
  4. // g[i] 表示第 2 个数是 a[i], 前面一个数是 x (在 1...i-1 选) 的和
  5. // 现在 f[i] = a[i] * g[i]
  6. // g[i] = a[i] * s[i], s 是 a 的前缀和, 完成了
  7. // s[i] = s[i - 1] + a[i]
  8. // ans += f[i]
复制代码


G - 区间表达式
  1. #include <bits/stdc++.h>
  2. using namespace std;

  3. typedef long long ll;

  4. const ll P = 998244353;

  5. string s;
  6. ll cur, sum, digit_s, k;
  7. ll ans;

  8. int main(){
  9.     ios::sync_with_stdio(0);
  10.     cin.tie(0);
  11.    
  12.     cin >> s;
  13.     for(auto i : s){
  14.         if(isdigit(i)){
  15.             digit_s++;
  16.             // i 自己也算
  17.             k++;

  18.             // cur 计算的是连续数字段的所有贡献
  19.             // 这样子可以和 sum 拼起来就是完整的贡献
  20.             cur = (cur*10 + k * (i - '0')) % P;
  21.             // ... + ... + ... ](1) + ... * ... * ..i
  22.             // i是右端点, 左端点可以取 (1) 处
  23.             // 左端点可以取 (1) + 1 到 i 处
  24.             ans = (ans + sum + cur) % P;
  25.         }
  26.         else if(i == '+'){
  27.             // 如果是加号, 后面的每个数字会被算 (前面有几个数字) 次
  28.             // sum 代表 i 前面的所有表达式的和, 连续乘积不能算进去
  29.             sum += cur;
  30.             k = digit_s;
  31.             cur = 0;
  32.         }
  33.         else{
  34.             // 如果是乘号, 后面的每个数会被计算 cur 次
  35.             k = cur;
  36.             cur = 0;
  37.         }
  38.     }
  39.     cout << ans;
  40.    
  41.     return 0;
  42. }
复制代码

I - 色子
遇到小的数字想状压, 然后对于取不到的需要加上取不到的概率

J - 小数拆分
对于一个集合增长我们需要总结出经过了哪几类操作

K - 狼人
树形背包, 注意不能实时更新 f , 并且注意转移顺序
对于这种连边限制的题想想是否是一款树


L - 火柴棒等式
数据范围变成了 3e4

可以考虑同时枚举两个数, 算上进位

  1. // l 代表是否是第 1 位(不是第一位的话填 0 就无法截断, 第一位的话填什么都行) , d 代表进位, a, b 分别代表 A, B 是否截断了
  2. int dfs(int sum, bool l, bool d, bool a, bool b) {
  3.     if (a && b)
  4.         // 可能有进位
  5.         return (!d && !sum) || (d && sum == 2);

  6.     int& res = f[sum][l][d][a][b];
  7.     if (~res)
  8.         return res;
  9.     res = 0;

  10.     for (int x = 0; x <= (a ? 0 : 9); x++)
  11.         for (int y = 0; y <= (b ? 0 : 9); y++) {
  12.             int z = (x + y + d) % 10;
  13.             int nsum = sum - (a ? 0 : t[x]) - (b ? 0 : t[y]) - t[z];
  14.             bool nd = x + y + d > 9;

  15.             // 分类讨论能否给 A, B 截断处理
  16.             if (nsum < 0)
  17.                 continue;
  18.             if (!a && !b)
  19.                 Add(res, dfs(nsum, 0, nd, 0, 0));
  20.             if (!a && (y || b || l))
  21.                 Add(res, dfs(nsum, 0, nd, 0, 1));
  22.             if ((x || a || l) && !b)
  23.                 Add(res, dfs(nsum, 0, nd, 1, 0));
  24.             if ((x || a || l) && (y || b || l))
  25.                 Add(res, dfs(nsum, 0, nd, 1, 1));
  26.         }

  27.     return res;
  28. }
复制代码


本帖被以下淘专辑推荐:

小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

发表于 2024-8-29 15:56:53 | 显示全部楼层
鱼油,你好!以下是有关计数DP综合问题的简要解答:

### A - 网格删边
#### 题目理解:
在一个网格中,我们需要确定删除一定数量的边后,仍然保持连通的方案数。

#### 思路:
1. **确定阶段**:按列处理删除边的数目。
2. **描述状态**:`f(i, j)`表示前i列,删除j个边后连通的方案数。
3. **状态转移**:需根据前一列的状态及当前列的操作来决定。

### B - 染色边
#### 题目理解:
要对边进行染色,考虑到只会影响同一对角线上的边。

#### 思路:
1. **确定独立部分**:每个对角线上的边是独立的,可以单独考虑。
2. **预处理**:对每个对角线长度预先计算出染色方案数。
3. **组合**:将这些预处理好的方案数进行组合。

### C - 分段i
#### 题目理解:
尚不明确,请进一步补充题目信息。

### D - 神秘密码
#### 题目理解:
给定一个包含加号和乘号的表达式,求解特定贡献。

#### 思路:
1. **状态压缩**:`状压`可以帮我们管理复杂的状态变化。
2. **动态规划**:通过计算数字连续段和操作符号累积贡献。

### E - 树上连通块个数
#### 题目理解:
在一个树结构中,对于任意区间的点,求它们组成的连通块数。

#### 思路:
1. **初始假设**:假设没有边,总共的连通块数。
2. **减少不合法情况**:对于每条边,减去它在各区间的贡献。
3. **计算公式**:总结连通块数为点数减去连边数。

#### 示例代码:
  1. cin >> n;
  2. for (int i = 1; i > u >> v;
  3.     if (u > v) swap(u, v);
  4.     ans -= u * (n - v + 1);
  5. }
  6. cout << ans / 2 << endl; //每个区间计算两次要除以2
复制代码


希望这些解答能帮到你!如有进一步疑问,请随时提问。

以上回复来自 FishC AI 小助理,如未能正确解答您的问题,请继续追问。
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2024-8-29 16:20:50 | 显示全部楼层

回帖奖励 +3 鱼币

orz!!!
你应该是报名 S 组吧?
今天刚刚把 J 组的知识点学完
老师和我说明天开始让我打模拟赛了嘤嘤嘤
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2024-8-29 16:21:51 | 显示全部楼层
我去,我竟然看懂了一丢丢.
昨天老师给我布置的作业就是 DP 综合练习。。。
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2024-8-29 18:24:38 | 显示全部楼层

回帖奖励 +3 鱼币

看看动规
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2024-8-29 18:56:49 | 显示全部楼层
学习编程中的Ben 发表于 2024-8-29 16:20
orz!!!
你应该是报名 S 组吧?
今天刚刚把 J 组的知识点学完

是的, 打完就退役, 年纪大了
你加油
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2024-8-31 16:35:04 | 显示全部楼层

回帖奖励 +3 鱼币

小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

发表于 2024-9-1 09:35:03 | 显示全部楼层

回帖奖励 +3 鱼币

小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

发表于 2024-9-1 09:43:22 | 显示全部楼层

回帖奖励 +3 鱼币

看啦
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

发表于 2024-9-4 17:40:43 | 显示全部楼层

回帖奖励 +3 鱼币

谢谢
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

发表于 2024-9-10 08:25:20 | 显示全部楼层

回帖奖励 +3 鱼币

小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

发表于 2024-9-13 20:26:13 | 显示全部楼层
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

发表于 2024-10-7 22:51:47 | 显示全部楼层

回帖奖励 +3 鱼币

小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-4-27 17:12

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表