威风镰鼬

题解

/ 注册

全部文章 / 题解（共4篇）

题解 | #没有上司的舞会#

思路树形dp基础题型，dp[i][0]表示i不选中时的最大快乐指数，dp[i][1]表示i选中时的最大快乐指数，所以我们只要先找到一个根节点，然后向下dfs，dp[root][0]和dp[root][1]的较大值就是答案。从下往上状态转移，我们先搜索到叶子节点，然后求出父节点的dp[i][0]和d...

dfs 树普及组图论树形dp

2021-06-16

1 430

题解 | #[NOIP2004]FBI树#

思路题目要求的是后序遍历，我们可以从根结点出发，查找左右子树，达到叶子结点时返回类型flag，然后决定父节点的类型。代码 #include<bits/stdc++.h> using namespace std; int len,n; string s; void f(string...

树二分字符串

2021-06-16

1 497

题解 | #小G有一个大树#

思路题目都没看懂就莫名其妙A了，“如果结点数相同输出编号小的”，是指平衡点的编号吗？下面题解是按照这样理解的。我先讲一下做题思路吧，数据规模很小，1e3，所以可以把每一个节点当作根去找树的最大深度，最大深度最小的第一个节点可以作为平衡点。找到平衡点之后再来一个push_up对他每一个子节点计算树的...

dfs 树图论

2021-06-16

1 703

题解 | #树上子链#

思路对于一个起始点x，最大子链是从x开始或者从x的子节点开始的最大子链。答案是从x作为起始点得到的最大子链的最大值，起点在dfs过程中走一遍就不会超时了。然后就是树形dp的问题啦。坑点:要开ll，同时注意所有点权值都为负数的情况。代码 #include<bits/stdc++.h> ...

dfs 树图论树形dp

2021-06-16

1 481