Solution

去年超算队招新唯一没有解决的一道题，今在 Gemini 老师的帮助下成功解决，决定重写一份题解报告。 Description 题目传送门 题目要求参赛者优化一个 C 语言函数 rotate_the_bit_vector，函数功能是对一个 bit vector 中的一个指定子区间进行循环旋转操作。 具体而言，题目给的 bit_vector 是一种内存紧凑的数据结构，将 8 个 bit 打包存储到一个字节中。参赛者需要在只修改 submit_func.c 一个文件的前提下重写其中的 rotate_the_bit_vector 函数，使其在大规模数据时尽可能快。 最后评分程序会通过三个不同的 benchmark (-s, -m, -l) 来衡量，每个测试中的数据规模会随着层数的增加而几何级增长，最终的得分取决于规定时间内能到达的“层数”，层数越高。说明性能越好，最终分数也越高。 Analysis Three-Reversal Algorithm 假设要移动的区间长度为 $ n $ ，需要移动 $ k $ 位；由于向右旋转 $ k $ 位可以等效于向左旋转 $ n-k $ 位，因此只讨论向左的移动。 题目提供了一个初始的性能极差的实现，通过逐位移动 $ k $ 次来实现 $ k $ 位循环旋转，复杂度为 $ O(n^{2}) $。根据这个原始实现很容易想到一个初步的优化方案： 问题的核心是把数组 [A|B] 变成 [B|A] ，一个经典的算法是三步翻转法：如果我们把翻转操作记为 ' ，A' 表示数组 A 前后反转，那么可以发现原问题的操作实际上等价于三次翻转操作：[A'|B']' = [B|A] ，复杂度为 $ O(n) $ ，代码如下： ...