编程奇淫技巧，应试专用

算法竞赛（ACM、NOI）中有哪些奇技淫巧？ - bstiat的回答 - 知乎 https://www.zhihu.com/question/288096930/answer/2968006378

卡时

比如时限是 1s ，然后你有一个退火或者什么爆搜做法，就记一下程序用时，如果快来不及了，就直接输出当前找到的最优解。

在退火里面，你先要大概算一下你退火一次要用多久。

while((double)clock()/CLOCKS_PER_SEC<=0.97) SA();

或者在搜索里面

if((double)clock()/CLOCKS_PER_SEC>0.97) return;

还有就是，这个查时间也是有一个常数的，不要运行一次就查一次，那样比较慢。

大概就是，有的题目，你可以想到一个看起来很对的 DP ，但这个 DP 其实是错的。

如果你这个 DP 的值，依赖于序列的顺序，或者其他什么东西，那么你可以把整个序列或其他什么东西，rand 一下，然后多跑几遍，然后就能拿到巨大多分，甚至可能过题。

当然，你要保证你这个 DP 出来的值一定能取到，只是不一定最优。

同理，还有随机化贪心，也是一样的想一个看起来很对的贪心，然后多乱搞几次。

具体分析还要看题目。不同题目差挺多的。

题目可能是推一些奇怪的式子，然后你不会推，你如果大胆猜想，感性思考答案是一个次数比较低的多项式，你可以先手玩或者爆搜一下前几个答案，然后直接插值，再看看下一个爆算出来的答案和插出来的一不一样，如果一样大概率就对了。比如 THUPC2019鸽鸽的分割 就可以这么做。

事实上，在大部分网络流题中，反向边用的都不多，所以如果你的网络流因为时空常数效果很差，你可以随机去掉一些反向边，可以拿到好多好多分。

众所周知，DP 其实就是在一个状态 DAG 上递推，但有的时候，你弄出来的状态转移并不是一个 DAG，这可能是因为你状态设计的错误，也有可能是因为正解不是 DP。

然后因为有环就没法 DP 了，但是我们考虑可以上一个 SPFA 乱搞，本来是按拓扑序在 DAG 上转移，现在我们按 SPFA 的顺序转移，如果转移后的值更优，就按最短路的方式更新，也可以拿到好多好多分。

有的题可以打表，但是表不能全部存下来，因为代码长度限制，这时你可以分块打表，取一个刚好能全部存下来的块的数量，然后算块长，回答询问的时候就只需要计算边角块就好了，平衡一下时空复杂度。

大家应该都会计算空间。

但是可能新开了几个数组，或者删了几个，计算空间比较麻烦，有一个小技巧，在所有变量定义之前加一行：

bool Be;

在所有变量定义之后加一行：

bool Ed;

然后输出：

cout<<((&Be-&Ed)>>20);

就是使用的变量的总空间，单位是 MB ，比较方便，但是栈空间啥的不会计算在内，你还需要额外算一下。