Zerol's Notes

【题解】HackerRank - Demanding Money

Posted on 2017-11-17 In ACM Disqus:

题目

https://www.hackerrank.com/challenges/borrowing-money/problem

题意

无向图上每个结点有个权值，求权最大的独立集的权及其方案数。

【题解】HackerRank - Recurrent on a Tree

Posted on 2017-07-20 Edited on 2017-11-17 In ACM Disqus:

题目

https://www.hackerrank.com/contests/w34/challenges/recurrent-on-tree

题意

给一棵树，每个点有一个值。求任意两个顶点（可以相同）路径上的值的和经过 f 函数后的和。f(x) 是斐波那契数列第 x 项。

【题解】HackerRank - Lena Sort

Posted on 2017-07-08 Edited on 2017-11-13 In ACM Disqus:

题目

https://www.hackerrank.com/challenges/lena-sort

题意

题目中用伪代码给出一个排序算法，要求构造 1～n 的一个排列，使得排序过程中恰好比较了 k 次。

【题解】HackerRank - synchronous-shopping

Posted on 2017-11-12 In ACM Disqus:

题目

https://www.hackerrank.com/challenges/synchronous-shopping/problem

题意

有 k 种商品，简单图上每个点上有若干种商品，购买商品不需要时间，两个人同时从 1 出发最后在 n 汇合，使得两人购买的商品囊括了所有的 k 种。注意数据范围。

【题解】HackerRank - Unique Colors

Posted on 2017-11-01 Edited on 2017-11-12 In ACM Disqus:

题目

https://www.hackerrank.com/challenges/unique-colors

题意

给定一棵树，树上每一个点都有一种颜色。定义一条路径的价值为路径上不同颜色的点的个数。对于树上的每个结点，输出从该结点出发的所有路径的价值之和。

算法 - 线段树

Posted on 2017-10-29 Edited on 2017-10-30 In Algorithms Disqus:

代码详见模板库。模板题 EOJ 3389-3393。

Q: 要不要把 n 补成 2 的幂？
A: 这个无所谓，但如果要写成自底向上，那么还是需要的，否则无法直接定位叶节点。
Q: pushdown 之后要不要立即 maintain？
A: 不用立即 maintain，但迟早是要的。但是立即 maintain 很可能会重复 maintain，增加超时风险。
Q:query 的时候要不要 pushdown？
A: 如果不要的话，查询时应该把之前访问到的结点的标签的效果累加起来，并作为参数递归下去。如果要的话，代码会更加具有普适性（比如 treap 只能选择 pushdown 标签，因为结点之间相对位置会改变）。
Q: maintain 的时候是否考虑当前结点的标签？
A: 都可以。如果考虑了，那么查询的时候就不要考虑当前结点的标签了，反之亦然。
Q: query 的时候先考虑 set 标签还是先考虑查询区间包含当前区间？
A: 都可以，但是先考虑 set 会快一些。
Q: 根节点是 0 还是 1？
A: 都可以，但好像 1 比较符合人性。
Q: 听说空间开三倍就够了？
A: 那可能就 GG 了，实测 4 倍是必要的。

其他注意事项：

maintain 函数要写得保证即便是重复调用也不会出错。
pushdown 子节点必须 maintain，尤其是那个没有递归下去的子节点。
打完 set 标记后 add 标记必须清空。

【题解】HackerRank - Counting On a Tree

Posted on 2017-10-28 Edited on 2017-10-29 In ACM Disqus:

题目

https://www.hackerrank.com/challenges/counting-on-a-tree

题意

给一棵树，树上的每一个点都有一个数字，询问对于给定的两条树上路径，有多少对不同的且分别属于两条路径的点满足对应数字相等。

算法 - 二进制分组

Posted on 2017-08-04 In Algorithms Disqus:

资料

具体见 2013 年集训队论文《浅谈数据结构题的几个非经典解法》（作者：许昊然）。

为什么

题目要求支持修改和查询操作。
但是你只有一种不支持修改的算法，往往是通过预处理来支持快速查询操作。
如果直接使用这种算法，可能要预处理很慢却要常常进行，查询很快却没几个，时间复杂度分配很不合理。
于是你想到，可以通过分块使时间复杂度变得均匀合理。就是把每 \(\sqrt n\) 个修改操作（假设修改操作共 \(n\) 个）分为一组，然后每次需要预处理的长度上限就变小了，作为代价，增加了查询的时间。
二进制分组是一种更为优秀的分组策略（具体和预处理复杂度和查询复杂度相关）。如果当前有 k 个修改操作，会按照 2 的幂将 k 分解从大到小的若干组。如果增加一个操作，分组的变化通过暴力删除和重建进行（当然如果可以合并的话那就只需要合并了）。(如 5 = 4 + 1, 6 = 4 + 2，从 5 增加到 6 就把原来那个大小为 1 的组删了，再将原来最后一个和新增加的那一个建一个大小为 2 的组)
复杂度：
- 单次查询复杂度 \(\times \log n\)，毕竟最多只有 \(\log n\) 组嘛。
- 总的预处理复杂度是单次的 \(\log n\) 倍，具体证明见论文。