首页 > 金字塔
开通博客写题解
头像 issue是云哥的小迷×呀
发表于 2020-11-06 16:17:49
传送门 一棵树每个节点用一个字母表示 已知序,求树的可能结构 害,本来想到了区间,冲动了啊 定义表示根为的合法树的数目 此时要求,意思是在原来树的根上再加一个节点 然后枚举一个使得 有转移 意思是仍然以为根,子树之一是 那么现在,区间也是一个相同的子问题了 状态的理解需要非常准确. #inclu 展开全文
去ta的博客 赞 (6) 回复(0) 收起
头像 Kur1su
发表于 2020-11-06 17:01:05
Description 虽然探索金字塔是极其老套的剧情，但是有一队探险家还是到了某金字塔脚下。经过多年的研究，科学家对这座金字塔的内部结构已经有所了解。首先，金字塔由若干房间组成，房间之间连有通道。如果把房间看作节点，通道看作边的话，整个金字塔呈现一个有根树结构，节点的子树之间有序，金字塔有唯一的一 展开全文
去ta的博客 赞 (6) 回复(0) 收起
头像 __故人__
发表于 2020-11-05 17:55:58
分析 设 为字符串中从 到 部分为一整棵树时的方案数。那么考虑子树的划分，那么 ，考虑子树在 处回到根节点。 代码 #include<bits/stdc++.h> using namespace std; #define ll long long const int mod = 展开全文
去ta的博客 赞 (5) 回复(0) 收起
头像 lifehappy
发表于 2020-11-05 21:49:31
金字塔 利用dfs序的通性，如果[l, r]是一颗完整的子树，一定有str[l] = str[r]，接下来就是考虑如何划分子树了。 考虑对[l, r]的子树进行划分，枚举中间划分值mid，那么因为dfs序一定有str[l] = str[mid] = str[r]。我们定义dp[l][r]，为区间[l 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 louhc
发表于 2019-08-25 22:22:59
思路 设为字符串中从到部分为一整棵树时的方案数.我们可以枚举第一棵子树,也就是为一棵子树,其它子树在为剩余的子树(与为根节点,同时也是的根节点,也就是说这两个点是同一个点).然后乘法原理与加法原理计算出答案即可.可以发现,一般情况下,很多状态是无用的.所以用记忆化搜索效率更高. 代码 #includ 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 sunrise__sunrise
发表于 2020-11-07 16:25:43
题目描述 给你一个字符串，并且告诉你这个是一棵树的一次 DFS 遍历序列，使用颜色标记节点，并且不保证每个节点颜色不同，也就是存在相同颜色的节点。你需要输出合法的树结构存在几个？ Solition 首先这是一个类 DFS 序，那么是不是可以得到结论，使用区间 [ l, r] 构造的树，一定会存在一些 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 阿里嘎多懒羊羊桑_
发表于 2020-11-12 20:48:11
题意： 给定序列表示dfs一棵树遍历得到的顺序，每次经过一个节点都输出该节点对应的字母，求有多少棵树满足此序列。 思路： 首先根据dfs的过程可以得到如果一棵树有n个节点的话，他的序列长度为2n-1；所以如果给出的长度为m的话，节点数量n=(m+1)/2。所以如果说给出的序列长度是偶数的话，答案一定 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 rk_no
发表于 2020-11-05 20:20:58
题目： 给一个类似序的序列。（经过一个结点记录一次颜色）。问有多少棵有根树满足（结点子树之间有序）。答案输出。 做法： 设为序列区间对应有根树的方案数，答案即为。转移思路：我们枚举区间对应的有根树里，第一棵子树的区间，设为，则其他子树对应区间。不难发现，合法的转移中，此时有最后加上只有一棵子树的情 展开全文
去ta的博客 赞 (1) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”