在需要频繁地求数组中区间的和的情景下，前缀和数组十分有用。花费 $O(n)$ 的时间生成前缀和，之后只需要 $O(1)$ 的时间计算区间和。 定义一个数组a = [1, 2, 3, 4, 5]，它的前缀和数组： prefix[0] = 1 prefix[1] = 1 + 2 = 3 prefix[2] = 1 + 2 + 3 = 6 prefix[3] = 1 + 2 + 3 + 4 = 10 prefix[4] = 1 + 2 + 3 + 4 + 5 = 15 要计算 $[i,j]$ 区间的和，可以用 prefix[j] - prefix[i-1] 算出，其中 i = 0 下溢时直接取 prefix[j]。 vector<int> prefix(n); int sum = 0; for(int i = 0; i < n; i++) { sum += i; prefix[i] = sum; } C++的numeric库提供了一个方便的函数partial_sum可以快速计算前缀和。 ...
这次省赛，实际上我并无准备，因为我一如既往地对算法没有什么兴趣。 竞赛一共八道题，A和B题是填空题，后六道题都是程序设计。前五题都做了，第六题暴力应该只拿了部分分，后两题就没时间写了。 在赛场上当时看到C++编译器是2014年发布的gcc 4.7.4，用的是C++98标准。但蓝桥杯的云端是可以运行C++11以上的标准的代码的。 本地做题环境的编译器低版本，导致许多C++函数用不了。比如 to_string()函数用不了。前两题最快速的做饭需要将数转到字符串类型，但是我只知道c++中有一个方便的 to_string() 函数，还好当时我看到赛场机子中有Pycharm，所以我就用python计算了前两道填空题。 这个向下兼容的过程，消耗了我大量时间。 最致命的是，有一道题我需要声明一个迭代器，但是我不知道迭代器的类型名，一般来说都是用auto自动推导的，但auto只在C++11标准以上才有，导致这道题的代码我在本地环境无法测试。明明代码是正确的，但本地的低版本编译器却认为我的代码是错误的。这种割裂感很少有。 而现在看来这道题也依旧做对了。 // C++98 std::vector<int> vec; std::vector<int>::iterator it = vec.begin(); // C++ 11 auto it = vec.begin(); // 自动推导为 std::vector<int>::iterator 与当时赛场的老师沟通，得知组委会只要求提供5.11版本的dev c++，而他们似乎只更新了代码编辑器版本，但一般来说dev c++是捆绑了一个编译器的，但不知为何内置的编译器却十分古典，感觉有点意思。 比赛完后，我查找了在 C++98 的字符串类型转换方法： // for C++98/03 standard string old_int_to_string(int v) { ostringstream oss; oss << v; return oss.str(); } string old_double_to_string(double v) { ostringstream oss; oss << fixed << setprecision(6) << v; return oss.str(); } string old_c_style_to_string(int v) { char buffer[32]; // make sure buffer is suffcient sprintf(buffer, "%d", v); return string(buffer); } 事实上，生活在草台班子里的我们不必认真太多。 ...
本文介绍了一种快速计算平方根倒数的算法，该算法源于上世纪90年代。文章首先解释了浮点数在计算机中的存储方式，特别是float32格式的结构，包括符号位、指数位和尾数位。接着，介绍了牛顿迭代法的基本原理及其在求解平方根倒数中的应用。通过对浮点数的对数变换，推导出与平方根倒数相关的公式，并解释了代码中使用的神秘常数 0x5f3759df 的来源，最后提到切比雪夫最佳逼近的概念，以优化计算结果。