赫he

分类

题解(3)

/ 注册

全部文章（共55篇）

题解 | #红和蓝#

#include <iostream> #include <cstring> using namespace std; const int N = 1e5 + 10; int n; int e[N * 2], ne[N * 2], h[N], idx; // sons[i] ...

2023-11-15

0 335

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

思路对于二叉树种任一节点k，如果k作为某个路径上的一个点，这个路径的方向分两个方向： 1）从节点k到k的父节点的方向。因为k的父节点dfs(par(k)))需要用到dfs(k)，需要返回这个方向上的值，需要从k的左右子树中选择大的(要和0比较，贪心)那个子树再加上val(k) 2）不到k的父节...

2023-11-04

2 362

题解 | #小红的树#

遍历每个颜色red[i]: 如果red[i]=1 (R)：将自身以及它的父节点，以及父节点的父节点... 让他们的cnt[父->父]++ 每次询问直接输出cnt[q]即可 #include <iostream> #include <cstring> using nam...

2023-11-03

0 270

题解 | #打家劫舍(三)#

树状dp，一般需要遍历树。方式是深度遍历。这个题，节点用输入数值的下标来表示，如图所示： f[i][0]表示以i为根的子树，并且不包括节点i（最大值不包括节点的值）的最大值，该状态可以来自于左右子树（如果存在）的max(f[左子树][0], f[左子树][1])+max(f[右子树][0], ...

2023-09-18

0 259

题解 | #合并回文子串#

#include <iostream> #include <cstring> using namespace std; const int N = 55; const int M = 110; int n; char a[N]; char b[N]; int dp[N][N]...

2023-09-01

0 342

题解 | #加分二叉树#

#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 30; int n; ...

2023-08-31

0 516

题解 | #[CQOI2007]涂色PAINT#

题解定义dp[i][j]是区间str[i~j]上的最少涂色次数。区间dp的核心思想是由一个个小区间合并成大区间，所在在dp时应该从长度最短的区间考虑，就是长度为1的区间。 1.长度为1的区间涂色次数为1 2.长度为2的区间它可以由两个长度为1的区间合并，这个题的特殊地方在于一次可以涂一个连...

2023-08-31

0 377

题解 | #括号区间匹配#

区间dp dp[i][j]: 区间[i~j]的字符串匹配所插入的字符数最少为dp[i][j] 区间dp，枚举区间长度来遍历i和j。初始时，区间长度为1时，dp[i][i]=1。长度不为1时，dp[i][j] = inf 当s[i]和s[j]匹配时，dp[i][j] = dp[i+1][j-1] ...

2023-08-19

0 490

题解 | #装箱问题#

#include <iostream> using namespace std; const int N = 2*1e4+10; int dp[N]; //dp[k]表示容量为v时，最大能装多大体积的物品 int nums[31]; int main() { int v,n; ...

2023-08-17

0 292

c++题解 | #分割等和子集#

思路转移：从一个数组中取数字，每个数字只能取一次，问取出的数字之和与未取出的数字之和能否相等。分析：一个数组中的所有数字分为两部分，问两部分的和能否相等，很明显，如果整个数组的和(s)是奇数，必然不能。当为偶数，则判断是否能在数组中取出一些数，使得它们的和为s/2。这样问题转移为：容量为s/2的...

2023-08-17

0 374