louhc

分类

未归档(78) 题解(81)

/ 注册

全部文章（共160篇）

题解 | 算法竞赛进阶指南荷马史诗

思路先不考虑的长度,就是一个叉哈夫曼树.题中要求没有是的前缀恰好对应了这一点,因为所有单词编码都是叶子节点,不会出现某字符串是另一字符串前缀的情况.因为需要的长度尽量小,我们在合并的时候尽量选深度小的即可. 代码 #include<bits/stdc++.h> using namesp...

堆贪心

2019-08-28

0 716

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

写在前面表示的子串.这里的下标从1开始.i的上一个匹配:一个位置j,满足.下面黑线表示字符串,其中红框中包含的字符相等(这是自然，同一个字符串嘛).j还要满足(注意啦两条黑线表示同一个字符串，只是位置不同)(其实这也算是KMP的复习吧...)下面图中红框中都表示相同. 算法 KMP.由于这不...

KMP

2019-08-28

0 578

题解 | 算法竞赛进阶指南 Genius ACM

思路根据贪心,从开始,该块能增加一个数就再加一个数,直到不合法为止,然后开下一块.如果暴力做的话随随便便就能卡到,肯定过不去.所以要用倍增,每次能加个数就加,不然.这样复杂度为,有点危险.我们可以只对新增的数排序,然后与当前块已有元素归并,复杂度就变成了. 代码 #include<bits/...

倍增

2019-08-28

0 612

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

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

并查集可持久化数据结构

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