盘点NOIP解题技巧大全

本文包含了我自己的经验以及各dalao的思路，有新点子的可以到本讨论区发帖。

1.常数优化

如位运算、循环变量前加register、函数前加inline等，大家自己百度去。

有一个地方要讲一下：

（其中$n_b$为b的二进制数位数，$b_{2k}$为b的二进制数的第k位）也就是说，2个正整数相乘，把第二个数转为二进制，并按二进制数的进位法则逐位转成右移运算。注：本方法不可用于除法。这个很少有网站讲到。

还有一个地方很重要：特判优化。对于循环/递归/递推寻找恰好符合条件的值，有公式用公式，用不了公式用特判：跳着区间遍历，循环计数器每次增加很多数，然后刚刚超出答案范围时，用一大串ifelse语句倒回去特判，寻找答案的具体位置。还有快速幂，可以用$\log_3n$甚至$\log_6n$的算法（每次乘3、6次方），然后加特判（注意用记忆化，不然每次都计算n次方，常数很大）。注意前面那个区间搜索，能用二分尽量用二分，二分更快！（我也构想过三分，但是发现常数更大。。。）

2.打表

很多时候，我们的算法会超时。有时数据只有很少的输入，数据跨度较小，甚至没有输入（当然这种题）这时可以另建CPP文件，模拟暴力遍历所有的输入可能，用慢算法算出结果，对目标程序写入答案数组或ifelse语句，强行打标出答案。至于没有输入的就更好办了，我不信我的程序慢到几个小时都算不完（NOIP有3小时考试时间）。

另：如果时间不允许，可以选择跳着数据打标，虽然不能保满分，但是基本的得分还是可能的。

也可以算出自己的算法最多能容纳多大的数据，加if语句：如果数据低于这个值直接计算，否则按照打表的结果计算。当然只打超时数据的表！也可以两种混着用（跳数据+选择性打表）。

如果对于不同的输入，输出依然有一定联系，可以分块打表。例如阶乘/n次方/数列求和等问题取模，可以把数据范围分成若干个小块，对于输入，划定范围，以范围下限的打表结果开始，逐步推至上限。

注：如果有两道题超时，可以同时用两个CPP文件打表（Linux也可以同时运行程序，省时间）。如果还是打不完表———到此为止，应该也能通过个别数据。手动补上剩下的程序（如main的return 0和下大括号等）。

3.答案搜索

有时要搜索一个区间以寻找答案，如果符合单调性用二分，否则用随机性较好的遍历方式来查找答案，这样刚好遍历到答案点的几率和速度就会提升。

4.骗分 直接输出答案肯定0分，对于多组数据访问，用随机数（可能真的有奇效）。

5.作弊（本方法纯属活跃气氛，请勿滥用）

把英语学好，这样不管其他考生用的什么语言，你都能理解他程序的大致意思（Python除外，太强）。我没学过Pas、Java等，但却成功吧Pas、Java、Go等语言的程序翻译成了C++。对于高级语言转低级语言要困难写，甚至几乎不可能，比如C++转Pas就要把STL库全部手写，Algorithm库也几乎要全部手写。瞄一眼其他考生的程序，想一想。

带个U盘，把算法模板提前考进去。比赛结束前删除。

6.桌面上建个try.cpp是个好习惯（用于打表、改程序。存数据等）。提前把要用到的代码打好也是个好习惯。