从题面来判断算法

· · 算法·理论 

我们经常会有这样的时候:
    辛辛苦苦学了几年OI，等上了考场的时候却发现所有的题目根本看不出来有什么逻辑性，甚至觉得毫无算法性可言，但是等到考试结束看题解又会发现确实是要用到某些算法，还用的挺规整，经典!
    于是乎你又在爆零的WA声中痛哭一夜......

所以，这篇文章就来教你根据题面来猜算法!

希望大家不要重蹈热狗贩子的覆辙......

注意：本文中讨论的都是普及组和提高组算法，很简单，因为省选及以上的作者没学过(悲)，但他们至少可以管饱你的CSP-J和CSP-S。

1 出现关于取模的语句

当题目中出现诸如 “将答案对998244353取模” 时的类似语句时，一般不可能是暴力，因为这种答案一般要你输出诸如方案数的答案。

例如洛谷P1077，是让你输出可以一共有多少种摆花的方案。由于已知答案要取模，所以答案取模之前一定数值较大，所以不可能是对所有的摆花方案一一枚举。 而实际上，这一题是个DP。

当然有的时候不一定有取模就是DP，这题也可能是数论。因为 有的时候一些答案不考虑特殊情况，是可以用数学公式算出来的。 ABC 262-E就是一个经典的例子，这里面的红点可以放在哪些地方是可以推导出来的，不需要DP，只需要公式。

这道题当时完全蒙骗了我 ，我居然还傻傻的在告诉别人这道题DP的正确性。

2 最大值最小，最小值最大或出现单调性

二分。

它是裸的!

比如?这题!

注意这题的措辞:

最短跳跃距离尽可能长?

这题二分!二分跳跃距离!

还有一种不那么裸的题型，大致是这个样子：

输入m,求 x^2+x+1=m 的正数解，数据保证有解

然后还贴心地给了你 y=x^2+x+1 的图像:

这题看似是个数学题，其实也可以用二分，因为我们看到，函数 y=x^2+x+1 在区间 \left( 0,\infty \right) （即正数区间） 中成单调递增。因此 这还是二分!

(当然:如果你数学学得好，还可以用这种方法同时解出这个方程的另一个解!)

\color{Red}\colorbox{White}{不一定二分的就是常数值。前缀和，位运算结果甚至gcd都可以尝试二分!}

3出现区间统一查询

这样的题面一般也是针对暴力来下套的，毒瘤一点的每一次操作针对全体元素，于是乎你喜提TLE，那么，接下来的指南会对你有所帮助。

数据完全静态，没有修改

那么此时，你需要前缀和或后缀和，当然，ST表也是一个不错的选择。尤其是当出现 n<= 10^7 这种及其毒瘤的数据范围时，这些算法就可以完杀线段树等。

数据为动态，有修改

一般情况下，有三种算法可供考虑：线段树，树状数组和根号分治。

线段树和树状数组的时间复杂度都是 O(logn)，而根号分治的复杂度是 O(\sqrt{n})。

至于线段树和树状数组的选择。线段树在区间修改的题目中优势更大，并且原理 个人 认为较为简单易懂；而树状数组的优势在于其占据的空间更小，并且 涉及每一次的单点修改时，线段树的复杂度是严格的O(logn) ，而树状数组的复杂度其实应为O(pop count(n))，这意味着线段树还可以卡常。

4 数据范围很小，但是暴力又会unaccepted

例题:洛谷P1433

乍一眼一看，这一题 n \leqslant 15 ，似乎可以用深搜剪枝来过去，复杂度是 O(n!) 。

但我告诉你: 15!=1,307,674,368,000 ，这一定是会超时的。

此时, 状压就成为了首选!

\color{Red}\colorbox{White}{请注意，状压是以二进制为基础的，因此当题目中所有数据都大于27时，不建议使用状压。}

当然，还有的时候，如果数据是很小，小到只是二位数，但是数据达到不适用状压的条件时，那么你也可以尝试折半查找。

5 数据的答案具有单一性或规律性

此时不要犹豫，AC就在打表里等着你!

什么叫单一性?举个简单的例子，考虑如下的问题:

 输入k,输出第k小的质数。

这种问题输出的永远是同一种类型的答案，没有变化。因此，可以直接自行本机打表，做出包含所有质数的向量，到时直接输出即可。

\color{Red}\colorbox{White}{如果本机打表的时间复杂度是诸如 O(n!) 的这种复杂度最好不要打表，这很耗时间。}

还有一种打表，是根据数据的变化而变化的，我们更多称之为 预处理。像是ABC 258-E，我们在接收到数据后预处理每一袋土豆会有多少个，由于这题数据是有规律的，所以我们不需要无限的打表，只要找出规律再进行取余查找即可。

6 出现操作对象之间的两两关系时

例题:ABC 190-E

这一题乍一眼一看，似乎是关于如何生成一个合法的序列的，但是你这么想。

把宝石看成节点，可相邻关系转化成边，那么这就是一个图上找路径的问题!

因此，我们得出结论，这种题目 一般都是图论!

\color{Red}\colorbox{White}{不一定只有空间上具有相邻关系的可以使用图论!逻辑关系也可以！}

7 有些题目看似可以贪心，但是会被会被Hack掉

这种题目基本都是DP或者反悔贪心

8 呈现出指数级的规律

举个例子,找规律输出正方形。

当n=1时,输出:

+-+
| |
+-+

当n=2时，输出:

+-+-+-+
| | | |
+-+ +-+
|     |
+-+ +-+
| | | |
+-+-+-+

当n=3时，输出:

+-+-+-+-+-+-+-+
| | | | | | | |
+-+ +-+ +-+ +-+
|     | |     |
+-+ +-+ +-+ +-+
| | | | | | | |
+-+-+-+ +-+-+-+
|             |
+-+-+-+ +-+-+-+
| | | | | | | |
+-+ +-+ +-+ +-+
|     | |     |
+-+ +-+ +-+ +-+
| | | | | | | |
+-+-+-+-+-+-+-+

很显然，第 n 号的正方形在四个角上各有一个第 n-1 号的正方形的， 因此我们需要使用递归!

\color{Red}\colorbox{White}{使用递归时注意剪枝!不要爆栈导致RE！}

9 查询关于连通分量的数据

并查集!你需要它!

不记得是CF上的哪一题了，大意是有一个长度为 n 的全排列 b 然后有一个长度为 n 的数组 d ，当 |i-j| \in \left\{ d_i,d_j \right\} 时，b_i 和 b_j 的值可以互换，问有没有可能以此将 b 转化成诸如 \left[ 1,2,3...n-1,n \right] 的全排列。

注意题面，我们可以将它理解为 \forall i \in \left[ 1,n \right] ,第 i 位要被移动到第 b_i 位。并且我们已经知道，从第 i 位可以移动到i+d_i 或 i-d_i 位(当然下标不能越界)。此时题目就转化成了 i 号点和 i+d_i 号点， i-d_i 号点连了边，求 \forall i \in \left[ 1,n \right] , i 号点和 b_i 号点是否连通。

\color{Red}\colorbox{White}{使用并查集不一定只用到father数组，你也可以使用诸如size这种数组统计当前连通分量的大小} \color{Red}\colorbox{White}{同时，并查集不支持删除操作，如果出现删边的操作，请尝试将它倒过来做，转化为加边问题}

10 序列中元素的数值较小

大多数时候，序列中的数值一般都是 小于等于 10^{9}的，所以当你发现题目中声明或是解题时发现某些数组中的数值很小 \left( \le2 \times 10^{5} \right) 时，必定考虑 开桶!

\color{Red}\colorbox{White}{当元素的值域较大时，也不排除用map来桶排序的可能}

总结

有的时候，某些题目标算并没有那么遥不可及，只不过是题面吓吓你罢了。在写题的时候要记住，编程算法的本质就是一种优化手段，因此，在遇见复杂度过大的步骤时，便可以考虑算法优化。

\color{Red}\colorbox{White}{区区CSP，不足为惧，你可以的！}