重生之我要当分子

分类

题解(3)

/ 注册

全部文章（共295篇）

题解 | 括号区间匹配

解题思路状态定义：表示使区间的括号序列合法所需插入的最少括号数转移方程：当和匹配时：否则：代码 c++ java python #include <bits/stdc++.h> using namespace std; i...

2024-12-24

1 23

题解 | [CQOI2007]涂色PAINT

解题思路状态定义：表示区间染色需要的最少次数转移方程：当时：当时：实现要点：字符串下标从开始，方便处理初始化数组为较大值长度为的区间初始化为代码 c++ java python #include <b...

2024-12-24

1 15

题解 | 小红取数

解题思路问题分析：需要从数组中选择一些数，使其和为的倍数且最大可以转化为求模运算的动态规划问题对于每个数，可以选择或不选择动态规划设计：状态定义：表示考虑前个数，和除以余时的最大值状态转移：不选第个数：选第个数：最终答案：，如果为 ...

2024-12-23

0 17

题解 | 字母收集

解题思路问题分析：只能向右或向下移动，是典型的路径DP问题每个字母有固定的分值：l=4, o=3, v=2, e=1 需要找到得分最高的路径动态规划设计：状态定义：表示从起点到达位置的最大得分状态转移：边界条件：第一行和第一列只能从一个方向到达实现要点：预处...

2024-12-23

0 25

题解 | 【模板】二维差分

解题思路问题分析：需要对矩阵进行多次子矩阵区域修改直接修改会导致时间复杂度可以使用二维差分数组优化到二维差分数组优化：对于区域加上，需要：最后通过二维前缀和还原原矩阵实现要点：差分数组需要多开一行一列注意数据范围，使用类型注意下...

2024-12-23

0 22

题解 | 【模板】差分

解题思路问题分析：需要对数组进行多次区间修改直接修改会导致时间复杂度可以使用差分数组优化到差分数组优化：构建差分数组，其中对区间加上时，只需要：最后通过前缀和还原原数组实现要点：注意差分数组需要多开一个位置注意数据范围，使用类...

2024-12-23

0 18

题解 | 【模板】二维前缀和

解题思路问题分析：需要多次查询矩阵子区域的和直接累加会导致时间复杂度可以使用二维前缀和优化到二维前缀和优化：预处理矩阵，计算二维前缀和对于查询，结果为：预处理时间，每次查询实现要点：注意前缀和可能超出范围，使用注意输入的下标从开始使...

2024-12-23

0 21

题解 | 【模板】前缀和

解题思路问题分析：需要多次查询数组区间和直接累加会导致时间复杂度可以使用前缀和优化到前缀和优化：预处理数组，计算前缀和对于查询，结果为预处理时间，每次查询实现要点：注意前缀和可能超出范围，使用注意输入的下标从开始代码 c...

2024-12-23

0 31

题解 | abb

解题思路动态规划设计：状态定义：表示处理到第个位置时：：作为的数量：作为的数量：作为的数量（最终答案）状态转移：对于每个新字符，可以：作为：更新作为（与前面的配对）：更新作为第二个（与前面的配对）：更新代码 c+...

2024-12-23

0 15

题解 | 装箱问题

解题思路这是一个01背包问题的变体：问题分析：目标：从个物品中选择若干个，使得总体积不超过的情况下，尽可能接近本质：求最接近箱子容量的物品组合方案关键点：需要找到所有可能的组合中，不超过且最接近的值解题步骤：使用动态规划，类似01背包表示体积 ...

2024-12-23

0 25