算法竞赛（ACM、NOI）中有哪些奇技淫巧？
好久不搞了，强调一下：过不去的题花里胡哨基本也过不去。如果利用这些技巧过了，纯属走运。 可以改写成： 这个操作减少了循环中 i < 100 的判断次数以及 goto 的次数 2. 优化求值顺序，比如： 可以改写成： 看似都是3个加法，但是后者可以利用指令级并行加速。 1 2 综合运用的例子： 3. 优化高维数组寻址 例： 可以改写为： 4. 优化嵌套数组寻址 例： 可以改写为： 理论基础：用好 cache，连续的内存会自动被读入 cache。多次嵌套的数组寻址会让 cache 命中率变低。 实战例子：在后缀数组的 20 行模板中： 这里 “for (i = 0; i < n; i++) ws[wv[i] = x[y[i]]]++;”顺手实现了 wv[i] = x[y[i]]，然后下两行 “for (i = n - 1; i >= 0; i--) sa[--ws[wv[i]]] = y[i];”实际上实现了一个稳定的计数排序，这里使用了 wv[i]，没有直接使用 x[y[i]]，就是优化了数组寻址。 ================= Update：连续被点赞，增加几条 ============== 5. Java 黑科技 我们那个时代，ACM里 C++11都不开。但是 JDK 可是全功能的…… 因此可以使用 Java 的黑科技包括但不限于： 5.1 自定义栈大小，Java thread 有： 再也不用担心在退化成链表的图里面DFS爆栈了 5.2 多线程 由于 Thread 是内置功能，Java 又有比 C++ 更长的时限，而 Java 单纯计算的效率没比 C++ 慢出太多。所以可以使用多线程计算…… 具体实现可以是起若干个线程，然后用一个 CyclicBarrier 等待所有线程跑完，输出结果 5.3 作图 是的，JDK 自带 JavaFx，可以做一个 GUI，把数据可视化。 ================= Update：岛娘亲自点赞了，再更几条！ ============== 6. 打表找规律 6.1 加速篇：结合 5.2，你可以写出比别人更猛的打表程序。如果测试机有 C++ 版线程库更佳 6.2 找递推公式 通项公式是多项式的数列，都可以靠解方程解出来通项公式 比如说一个数列，1 4 9 16 25…… 你也不知道他是啥（这怎么可能看不出是啥），但是盲猜他的通项公式是多项式，假设最高项是三次方，那么 f(x) = ax^3 + bx^2 + cx^1 + d，问题就变成了个解方程问题： 比如说又打表得出一个数列 1 1 2 3 5 8 13 21...，你也不知道他是啥，但是如果你猜他的递推公式是 f[i] = a * f[i-1] + b * f[i-2] + c * f[i-3] + d 这样的，那么问题就变成了个解方程问题： 嗯，可以解得 a = 1 b = 1 c = 0 d = 0，于是递推公式就暴力解方程解出来了。 6.3 暴力DFS，枚举思路贪心对拍 常见于盲猜是个贪心，但是不知道怎么贪。可以先写个暴力解法，然后编若干测试数据，然后枚举思路：贪 xx 大的优先，xx 小的优先 等。某条思路和暴力解法解一样就 Bingo 了 7. 这里不推荐内嵌汇编。因为每个平台对内嵌汇编的支持都不一样，没法训练。而且2202年了，手撸的汇编还真不一定打得过编译器。。。 8. 调整分支语句的逻辑顺序 比如： 如果 cond1，cond2，cond3 不相关，且绝大多数情况下都是 cond2，可以改写成： 9. Struct > N个数组 常见的例子是： vs 前者的效率会更高，因为随机访问 intervals[i] 的时候，所在的一个内存页都会从主内存放到 cache，而访问 interval[i] 就很可能顺手访问 interval[i+1], interval[i+2]，写成 struct 缓存命中率就会高。而拆成三个数组的话，访问 interval_right[i] 的时候，可能就会把 interval_left[i] 的缓存顶掉。下次访问 interval_left[i+1] 的时候就又要从主内存寻址了 其实写完回头看看，这里提到的绝大多数优化性能的操作都是正道…… 可以参考《深入理解计算机系统》第五章，有详细介绍。在测试数据不够强的情况下，用一个略低效的算法，但低空卡时间飞过是有可能的。