louhc

题解

未归档(78)

/ 注册

全部文章 / 题解（共81篇）

题解 | 算法竞赛进阶指南可持久化并查集

思路说是可持久化并查集,实际上就是把并查集使用的数组变成可持久化数组.当然,可持久化并查集路径压缩不现实,这样可能总共需要修改个值,空间复杂度可能不好过去.想象当初学并查集时使用的优化,出了路径压缩,还有按秩合并.这样一次只需要修改个值,而且复杂度基本一样.这样子时间复杂度为,空间复杂度为. 代码...

并查集可持久化数据结构

2019-08-28

0 631

题解 | 算法竞赛进阶指南最大异或和

思路可持久化入门题.首先,如果不是区间,而是整体询问的话,我们可以直接建,从高位到低位枚举,答案的这一位能是1就为1,不然只能为0.区间询问的话其实相差不大.使用可持久化树,这样就知道每个前缀序列构成的树.还需要记录每个节点总共经过了几次.然后在两棵树上跑,这里判断是否有节点作差即可(类似于前缀和...

字典树可持久化数据结构

2019-08-28

1 605

题解 | 算法竞赛进阶指南普通平衡树

FHQ Treap FHQ Treap （%%%发明者范浩强年年NOI金牌）是一种神奇的数据结构，也叫非旋Treap，它不像Treap zig zag搞不清楚（所以叫非旋嘛），也不像Splay完全看不懂，而且它能完成Treap与Splay能完成的所有事，代码短，理解也容易。基本操作 FHQ Tr...

平衡树

2019-08-28

3 1098

题解 | 算法竞赛进阶指南装备购买

思路可以像线性基那样做(只不过把二进制换成1000进制而已).因为要求代价最小,我们需要对所有装备按照代价从小到大排序,某件装备尽量被已选装备消去靠前的属性,然后如果遇到某一位不能被消为零,就选该装备并且记录答案.过程基本上和线性基差不多,具体过程参考代码.复杂度为,虽然过亿,但是跑不满,还是可以...

线性空间

2019-08-28

0 552

题解 | 算法竞赛进阶指南球形空间产生器SPHERE

思路设圆心为,点坐标为.因为点到圆心的距离的平方为.这样有个式子.这些式子两两相减可以得到个元一次方程组,这样直接跑高斯消元解出圆心坐标即可.复杂度为. 代码 #include<bits/stdc++.h> using namespace std; #define Re registe...

高斯消元

2019-08-27

2 570

题解 | 算法竞赛进阶指南 Polygon

思路很明显的区间DP.环形处理可以使用枚举断哪条边(复杂度为,比较危险)或者复制一遍接在后面(复杂度为).这里采用后者.转移时乘法需要注意负数,因为负负得正可能反而比两个最大值相乘更大,因此需要同时记录区间能得到的最大值和最小值.加法转移:乘法转移:然后在取最大值即可. 代码 #include&l...

动态规划区间动态规划

2019-08-27

0 784

题解 | 算法竞赛进阶指南 Color a Tree

思路比较难的贪心题.首先,对于权值最大的节点(不算根节点),染了它的父亲之后的第一步肯定是先染它.因此可以将这两个点缩起来(反正染的步骤是连续的).下一步该怎么办呢?仍然是找权值最大的点,不过要稍加变换.假设缩起来的点的权值为,与第三者的权值比较,先染的话代价为,先染$的话代价为,作差后为,那么只...

贪心

2019-08-27

0 785

题解 | 算法竞赛进阶指南计算重复

思路这题可以使用倍增解决.预处理出表示从的第个字符开始匹配,匹配个需要的个数与个最后一位匹配到的哪个位置.然后就可以求出最大的使能由生成.然后即为答案.复杂度为,表示字符集大小.具体实现细节参考代码. 代码 #include<bits/stdc++.h> using namespace...

倍增

2019-08-27

0 634

题解 | 算法竞赛进阶指南 Naptime

思路我们可以分情况讨论. 第N个小时正在休息这种情况就是一个DP题.设表示当前处理到第个小时,已经休息了个小时,最后一维为表示第个小时正在休息,否则不在休息.转移也不难: ,这个时刻不休息的话前面休不休息无所谓. ,这个时刻休息的话要考虑前一个小时休不休息.如果前一个小时休息的话这个小时休息是有...

动态规划

2019-08-27

0 594

题解 | 算法竞赛进阶指南疫情控制

思路显而易见,答案具有单调性,时间越长,越容易控制疫情.所以很容易想到二分时间.首先,占据一个点肯定不如占据这个点的父亲,因此时间内到达不了号节点的尽力往上跳就可以了(暴力跳可不行,需要使用倍增).还有一些军队可能会经过号节点到达其他号节点的儿子节点.先来证明一个结论:若些军队的集合不经过号节点能...

树上倍增

2019-08-27

1 760