Forever you~ 
  • 首页
  • 归档
  • 分类
  • 标签
  • 关于
  •     
Dominator Tree
问题引入 题目要求解决的模型: 给定有向图G(可能有环)和图中的一个点r,对于G中的任意一个点x,求从r到x的路径上(可能有很多条)必须经过的点集。 Flow Graph:若有向图G中存在一点r,从r出发可到达G中所有的点,则称G是Flow Graph,记为(G,r)。 必经点(dom):若在(G,r)中从r到y的路径一定经过点x,则称x是从r到达y的必经点,记为x dom y。 从r出发到达
 2018-09-14
算法学习
图论
Knapsack and Queries
来自Petrozavodsk Winter-2018. AtCoder Contest里的D题 题意是说,有QQQ次操作,分为两种,一是添加一个重量为www,价值为vvv的物品,保证插入的www单增,二是删除当前重量最小的物品。每次操作完之后,都有一个询问,询问能否从已有物品中选出一个子集,使得重量之和在模MMM之后在区间[l,r][l,r][l,r]内,并且价值和最大。 数据范围,Q≤10000
 2018-09-12
散装题解
背包 单调队列
超实用!Stern-Brocot tree总结奉上
关于Stern-Brocot tree网上的资料较少(后记:实际上并不少,只是竞赛中讨论的不多),能够找到的资源有Wikipedia以及《具体数学》上的介绍,这里大概总结一下这个树形结构的性质。 Stern-Brocot tree: Stern-Brocot tree构成了一个无限的二叉排序树,可以将所有的正有理数从小到大列举出来。 构造方法可以理解为:先在左边写上01\frac{0}{1}10
 2018-09-11
算法学习
Stern-Brocot tree
线段树合并
适用条件:动态开点的(权值)线段树。 关于时间复杂度的结论: 每次合并的代价是两棵树的公共节点数。 若有n棵含有单个元素的树,经过n-1次merge操作,将他们合并成一棵树的代价是O(nlogn)O(nlogn)O(nlogn)或O(nlogC)O(nlogC)O(nlogC)的 单次merge操作开销可大可小,均摊下一次就是一个log的。 关于空间复杂度,普通版本是O(nlogn)O(nlo
 2018-09-05
算法学习
线段树
2017 西安网络赛 A题 TREE
最近想起来这么一道题,当时q神没rush出来,赛后几分钟AC掉的 题目链接:https://nanti.jisuanke.com/t/17114 题意是树上有NNN个点,每个点的点权是一个01矩阵,有QQQ次询问,每次问树上从x到y这条路径上的矩阵依次乘起来的结果是多少(模2意义下)。数据范围N≤3000,Q≤30000N\le 3000,Q\le 30000N≤3000,Q≤30000,矩阵大小
 2018-08-31
散装题解
LCA bitset
高维偏序问题
最近做了几道高维偏序的简单题。 对于这类题目一般有三种通用方法,一是cdq分治,维数越多嵌套次数就越多,总体来说思路就是对时间分治,每次统计出左半区间的贡献点对右半区间的询问点的贡献,这样对于每个询问点来说,它前面的所有对它造成影响的点就都会被算到。二是用bitset优化暴力,应该只能处理计数问题,但优点是好写,适合做高维偏序。三是KDtree,emmmm,这个没怎么写过,多校训练十分艰难的写过一
 2018-08-30
算法学习
偏序
偏序集
偏序关系 首先回顾一下偏序,集合X上的偏序是一个自反、反对称且传递的关系 如果对于X中所有的x,都有x R x,则R是自反的 如果对于X中所有x和y,若x R y和y R x同时成立则x=y,则R是反对称的 对于X中所有的x,y和z,只要x R y且y R z,就有x R z,则R是传递的 通常用≤\le≤取代R来表示偏序关系,常见的偏序关系有集合的包含,小于等于,整除等。<<&
 2018-08-29
算法学习
偏序
类欧几里得算法
推导 有时候需要快速计算如下式子(比如数据范围都是 10910^9109 ) f(a,b,c,n)=∑i=0n⌊ai+bc⌋f(a,b,c,n)=\sum_{i=0}^{n}\lfloor\frac{ai+b}{c}\rfloor f(a,b,c,n)=i=0∑n​⌊cai+b​⌋ g(a,b,c,n)=∑i=0ni⌊ai+bc⌋g(a,b,c,n)=\sum_{i=0}^{n}i\lfloor
 2018-08-28
算法学习
math
后缀自动机学习笔记
写在前面 推荐hihocoder上的讲解,可以说是十分清楚了。 用好后缀自动机不是十分容易,但看完本文的总结应该能至少达到签到水平…
 2018-08-18
算法学习
后缀自动机
诗词两首
西江月 瑟瑟微风夜半,潇潇细雨黎明。雄鸡一唱与谁听?几度茫然光景。 壮志还须努力,何时乡返功成。椟中美玉尚无名,待得他人相赠。 七绝·四季 漫漫冰霜眼底收, 西风萧瑟欲何求。 独怜明媚绝非夏, 四季如春花满楼。 第一首是词的作业,第二首是诗词格律与写作期末题,这学期另作了一首五古,质量不高,就不放出来了=、= 关于诗词创作就到这里了(撒花)
 2018-06-22
个人随笔
诗词
1234

搜索

Hexo Fluid