0%

资料

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

为什么

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

题目

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

题意

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

Read more »

题目

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

题意

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

Read more »

题目

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

题意

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

Read more »

题目

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

题意

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

Read more »

题目

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

题意

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

Read more »

你好,世界!