重生之我要当分子

分类

题解(3)

/ 注册

全部文章（共295篇）

题解 | [ZJOI2010]COUNT 数字计数

解题思路对于大范围内的数字统计，需要使用数位DP的方法：将问题转化为求，表示到中每个数字出现的次数则区间的答案为对于计算：考虑每一位的贡献例如对于数字：个位：每个数，各出现次十位：每个数，每个数字在十位上出现次百位：每个...

2024-12-27

0 27

题解 | 串

解题思路本题要求计算长度不超过且包含子序列 "us" 的小写字母字符串数量。可以使用动态规划解决：状态定义：表示长度为时的状态 : 还未出现 : 已经出现，还未出现 : 已经出现状态转移： // 前一个状态未出现，新字母不是 ...

2024-12-27

0 11

题解 | 数位染色

解题思路核心思想：将数字转为字符串，计算所有数位之和如果能找到一些数位，使其和为，则可以实现要求本质是一个子集和问题解决方案：先判断总和是否为偶数（如果为奇数则无解）使用状态压缩DP或DFS判断是否存在子集和为由于数据范围较小（最多18位数字），可以直接DFS ...

2024-12-24

1 28

题解 | 郊区春游

解题思路核心思想：使用状态压缩DP解决，状态表示为，其中表示当前点，表示已访问点集合表示当前在点，已经访问了表示的点集合时的最小花费通过二进制表示已访问的点集合状态转移：对于当前状态，枚举下一个要访问的点代码 cpp java p...

2024-12-24

1 24

题解 | 打家劫舍(三)

解题思路核心思想：对于每个节点，有两种状态：选择或不选择如果选择当前节点，则不能选择其子节点如果不选择当前节点，则可以选择或不选择其子节点状态定义：表示不选择节点时的最大金额表示选择节点时的最大金额状态转移：对所有子节点对所有子节点 ...

2024-12-24

1 19

题解 | 二叉树中的最大路径和

解题思路核心思想：对于每个节点，需要考虑经过该节点的最大路径和路径可以是：左子树->节点->右子树，或者左子树->节点，或者右子树->节点需要自底向上计算，使用DFS 关键点：每个节点需要返回：从该节点出发的最大路径和（只能选择一个子树）同时需要更新...

2024-12-24

1 25

题解 | 小红的树

解题思路核心思想：使用DFS预处理每个节点的子树中红色节点数量对于每次查询直接返回预处理的结果实现步骤：根据父节点数组构建树（邻接表） DFS遍历树，统计每个节点子树中的红色节点数处理查询代码 cpp java python #include &l...

2024-12-24

1 18

题解 | 红和蓝

解题思路核心思想：使用数组标记配对关系：表示节点和需要染成相同颜色通过两次DFS完成配对和染色第一次DFS (dfs1)：确定配对关系从根节点开始，自底向上处理对于叶子节点或未配对的节点：如果其父节点已配对，则无解否则，将该节点与其父节点配对（赋予相同的...

2024-12-24

1 26

题解 | 旅游

解题思路这是一个树形DP问题：表示不选择节点时，以为根的子树能访问的最大天数表示选择节点时，以为根的子树能访问的最大天数状态转移：当选择时 ()：必须选择所有子节点的不选择状态 () 当不选择时 ()：每个子节点可以选择或不选择，取边界条...

2024-12-24

1 21

题解 | 取数游戏

解题思路状态定义：表示当前剩余区间能获得的最大价值当前是第次取数转移方程：边界条件：时，代码 c++ java python #include <bits/stdc++.h> using namespace std; ...

2024-12-24

1 14