sunrise__sunrise
sunrise__sunrise
全部文章
题解
未归档(12)
读书笔记(1)
归档
标签
去牛客网
登录
/
注册
刘晟的博客
记录产出的算法题解和知识分享地址
全部文章
/ 题解
(共5篇)
2021牛客暑期多校训练营7 F、xay loves trees
来自专栏
题目大意 给出棵以为根的树,你要在第一棵树上选择若干个点,并且在第二棵树上选择相同编号的点。 现在要求你在第一棵树上选择的点,把他们连接的边全部找出来必须构成一条链; 并且你在第二棵树上选择的点,不能存在任何两个点他们之间有祖先关系,换句话说就是某个点选了,它全部的子树节点都不能选了。 现在要你输出...
线段树
时间戳
2021-08-25
0
502
2021牛客暑期多校训练营6 H、Hopping Rabbit
来自专栏
题目大意 小兔子在一个二维的格点图中跳跃,每次它都会沿着正负方向共个方向移动个单位长度。 现在地图中有个陷阱,陷阱是以矩阵的方式存在的,问你有没有一种方法让小兔子在某个起点随意乱跳的情况下都不会掉入任何一个陷阱,你要输出这个起点,或者。 Solution 考点:线段树维护扫描线 首先由于地图本质上是...
线段树
扫描线
2021-08-24
0
458
2021牛客暑期多校训练营4 E、Tree Xor
来自专栏
题目大意 你有一个一颗树节点数,树上的边有一个边权,点有一个点权,你要保证有直接父子关系的点之间,并且树上每个点他的点权选取范围为,现在请问你能构造出多少颗不同的树,有任何一个不同就认为是一颗不同的树。 Solution 考点:线段树区间性质 首先树上边权关系给你了,所以当我们顶下后整棵树后续的都会...
线段树
2021-08-20
1
618
【每日一题】3月2日区区区间 线段树
来自专栏
解题思路 整个题面一看就有着溢出屏幕的线段树的味道。那么任何使用线段树维护区间,我们使用线段树又要维护什么呢?显然对于我们每次的修改,都是存在一定规律的,既公差的等差数列,并且每次求解的都是一段区间的和,那么我们就用标记推迟往下赋值的时间,并且使用记录区间的和,因为给出了首项,项数可以通过的距离求解...
线段树
2021-03-01
1
881
【每日一题】1月14日New Year Tree 线段树、dfs序、状压
来自专栏
题目描述 给你的一棵树,每个节点有自己的颜色。下面有两种操作。操作一:把一个节点及其子树全部改成颜色。操作二:输出一个节点及它子树中一共有几种颜色。题目涉及的颜色种类。 Solution 观察颜色种类就是这个题目的切入点,看到最大不超过种的颜色,就在指引我们去状压这个颜色了。那么维护数上子节点,这个...
线段树
2021-01-19
1
654