louhc

分类

未归档(78) 题解(81)

/ 注册

全部文章（共4篇）

题解 | 算法竞赛进阶指南生日礼物

思路该题可以转换为数据备份.首先,根据贪心,如果按正负将所有数分成若干连续的段,每一段的正负号相同(这里出现0似乎没什么卵用,你过滤掉也好,看做正数也好,都没有什么问题),那么每一段要么全选,要么都不选.这个很好理解,因为如果是正数段,能选当然一起选最优,如果是负数段,选该段的负数肯定是因为要将两...

堆贪心

2019-08-29

0 570

题解 | 算法竞赛进阶指南数据备份

思路显而易见的一点是,选取相连的任意两栋办公楼肯定是相邻的,于是我们先将距离两两相减得到序列,最后答案即为序列中选个元素,选的任意两个元素不能相邻.如果只有一个数,直接选这个数即可.如果有三个数,要么选中间的,要么选两边.这样一直推下去可以得到一种做法,每次选最小的数,但是实际答案并不一定选该数,...

堆贪心

2019-08-29

0 988

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

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

堆贪心

2019-08-28

0 724

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

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

贪心

2019-08-27

0 798