题目

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

题意

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

资料

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

为什么

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

题目

https://www.hackerrank.com/challenges/newyear-game

题意

给一列数，A 和 B 轮流取，如果每个人取的数之和之差的绝对值被 3 整除，则 B 赢，反之 A 赢。

题目

https://www.hackerrank.com/challenges/summing-pieces

题意

给定一列数，分割成任意多段，某一种分法的值为每一段的数字和和段长之积之和，求所有方案的值的总和。

题目

https://www.hackerrank.com/challenges/sherlocks-array-merging-algorithm/problem

题解

• 每一列的数在原数列中是连续且单调增的
• 每一列数的个数是单调减的

题目

https://www.hackerrank.com/challenges/prime-xor

题意

给 n 个介于 3500 和 4500 之间的数，求不同子集（可以包含重复元素）的总数，使得子集异或和是质数。

题目

https://www.hackerrank.com/challenges/fair-cut

题意

给 n 个数，分成 k 和 n - k 两组，使得两个组之间任意数对之差的绝对值之和最小。

题目

https://www.hackerrank.com/challenges/prime-xor

题意

定义一种新的数值表示方法，每一位权值和二进制一样，但是每一位都可以是 0～9。问第 k 大的数是几（如果表示的数值一样大的话，再看做十进制比较）。

题目

https://www.hackerrank.com/challenges/yet-another-minimax-problem

题意

给出 n 个整数，求一个排列使得相邻两数的异或值的最大值最小，输出该值。

你好，世界！