首页
题库
公司真题
专项练习
面试题库
在线编程
面试
面试经验
AI 模拟面试
简历
求职
学习
课程
专栏·文章
竞赛
搜索
我要招人
发布职位
发布职位、邀约牛人
更多企业解决方案
在线笔面试、雇主品牌宣传
登录
/
注册
Disukal
获赞
0
粉丝
2
关注
3
看过 TA
0
西安电子科技大学
2023
C++
IP属地:浙江
暂未填写个人简介
私信
关注
拉黑
举报
举报
确定要拉黑Disukal吗?
发布(2)
刷题
Disukal
2020-04-09 20:46
已编辑
C++
【每日一题】树
Step 0 原本错误思路:模拟染色过程。把树构建出来,由题意初步模拟为,为了使同颜色(x,y)任意两点到达对方,应该由根结点开始染色,但凡染出一条路径,该根的其他结点则只有两个选择:染同样的颜色或必须换新颜色。每遇到一个根结点(分岔口)都会面临这样的选择。即时统计染色点数,看是否染完。1)复杂度近似2^n。2)构建树有困难,需要确定根结点才能确定父子的方向。但树的输入又是无向的,以邻接链表储存会无法分清其父其子。而模拟的染色是父向子的方向。 Step 1 题目是求解染色方案数,并不在意实际染色情况,尝试把题目抽象成数字。以上述的根向其子结点染色的过程面临的不同选择,即是可能的新方案数。所以应...
0
点赞
评论
收藏
转发
Disukal
2020-04-08 21:24
已编辑
C++
黑白树
这大概是清楚姐姐的题解的题解。看着清楚姐姐的题解和代码做的个人笔记。因为不太会写= =。(这里绝壁是最菜最菜最菜的一员) Step 0(个人错误) 审题问题,初步没有注意到是该结点i至根的链的染色,以为有向上和向下,对于结点的染色选择就迷茫了。 关于数据处理。对于染色与否,及整棵树的关系,当时想用结构体,包含fa,dis,flag,vec。 1)flag:想直接用flag来模拟染色过程。然而属于无用信息,浪费内存,只需要数字位置抽象化即可。 2)vec/fa:储存的是向下的和向上的,想用单结点函数染色所有关联结点。有重复染色,不可取。 3)树的结构是以一点为中心扩散,无法遍历,无法找到根结点...
0
点赞
评论
收藏
转发
1
工具箱
TA的圈子
暂未加入圈子
TA的圈子
TA的笔记
暂无笔记
TA的笔记
登录
0
天
已登录
0
天
连续登录
0
人
今日访客
牛客网
牛客企业服务