house_cat

ACM

JAVA(5) 其他(3) 文(1) 算法导论(2) 计算机图形学(4) 面试(2) 题解(2)

/ 注册

全部文章 / ACM （共6篇）

【lca+输入】Attack on Alpha-Zet

Attack on Alpha-Zet 题目描述 Space pirate Captain Krys has recently acquired a map of the artificial and highly secure planet Alpha-Zet which he has bee...

树 LCA

2018-09-12

0 458

[HDU多校]Ridiculous Netizens

[HDU多校]Ridiculous Netizens 点分治分成两个部分：对某一点P，连通块经过P或不经过P．经过P采用树形依赖背包不经过P的部分递归计算树型依赖背包 v点必须由其父亲u点转移过来即必须经过P...

点分治树

2019-08-14

0 424

Escape from the Hell

Escape from the Hell [JAG Asia 2016] 容易证明优先选择差值大的更优对于最后一瓶我们可以枚举枚举最后一瓶，然后在树状数组上消去它的影响，然后线段树check是否出现被追上的情况，即查询区间最小值。需要用到两个线段树，因为当二分找到的位置在最后一瓶后面...

树树状数组线段树

2019-09-14

0 431

Random Access Iterator

Random Access Iterator 树型概率DP dp[u]代表以当前点作为根得到正确结果的概率将深度最深的几个点dp[u]很明显是1 然后很简单的转移有k次，但我们要先看一次的情况，然后再推到k次，k次中只要有一次就可以正确，所以求出k次全失败的概率，用1去减即可 #in...

概率树动态规划

2019-09-14

0 424

[平衡树-Splay]营业额统计

题目 https://loj.ac/problem/10143 题解一眼就能看出这题就是找Splay的前驱和后继通过这题可以体会到为什么要加入一个无穷小的点和一个无穷大的点，加入可以防止出坑代码 #pragma GCC optimize(2) #pragma GCC o...

树查找二叉树 Splay

2020-03-05

0 687

[学习笔记]树套树

引言树套树，顾名思义，就是要将两种或多种树形数据结构结合起来，解决一些单独无法解决的问题。如果说要解决区间上的问题，如最大值，区间修改等，肯定会想到线段树。但是线段树不能查询第k大，不能查询一个数在区间的排名，自然也不能查询前驱和后继。平衡树可以解决查询排名、前驱、后继等问题，但其不...

线段树树查找二叉树 Splay 学习笔记树套树

2020-03-07

0 537