CSP常见问题常见分析技巧

1.第$ k $大:二分答案,转化为判定(多半为求出答案后比大小)问题 2.序列最优化:dp/贪心,也有可能结合,如果直接dp不好转移,贪心又没有明显的正确结论,可以先尝试证明最优决策性质然后dp 3.计数:多半dp,如果不能dp的话计数原理 4.求总贡献:直接求太慢或不好做的话,转化成单个贡献累加 5.$ n $很小:多半状压dp,如果是数学题还要考虑容斥原理 6.疑似NPC问题但数据范围大:很可能要转化到特殊模型上获得正确算法 例:最大团问题,一旦发现数据范围不能支撑一般图最大团搜索的复杂度就要考虑用补图转化到二分图上用最大独立集求解 7.数据结构中出现删除操作:多半离线+时光倒流转成插入操作 8.棋盘上一次走一步且方向没有特殊限制:多半二分图 9.排列计数:dp,状态可以按权值正序或倒序,也可按位置正序或倒序 10.序列上的划分:多半dp,而且是一维状态,如有必要,还可能要加个区间dp预处理 11.$ n $超级大而且可以用dp暴力:一般是矩阵快速幂,少数情况下是结论题,找规律 12.$ n $不大($ O(n^3) $可以搞定的范围),转移步数$ k $超级大而且转移有固定的限制条件:可行的转移作为边,邻接矩阵快速幂 13.数据明显提示$ 2^n $:分治或倍增或二进制拆分 14.树上两条链(不相交),最优化或问题与长度有关:双直径 15.直接转移有后效性,但是影响范围很小:一般状压dp 16.多次查询的dp问题:一般数据结构维护,重复计算很多的话可以倍增优化 17.答案有单调性/最大值最小/最小值最大:二分答案转化为判定问题 18.图上随便走,直接dp有严重后效性:一般邻接矩阵问题 19.背包类模型 20.需要把每个点都走一遍:转化成旅行商问题 21.需要把每个边都走一遍(或每种二元组都用上):转化成欧拉路问题 22.一些奇怪的最短路问题:图的建模与转化 23.涉及与素因子有关的数论题:唯一分解定理或枚举 24.选取某一个区间达到最优化目标:枚举某一端点,用数据结构维护或单调性找寻最优的另一端点并更新答案 25.有特殊操作的最短路题(特殊操作数很少):分层图 26.一些对某一条边进行操作的图论题:枚举操作的边,然后考虑快速求出对边操作之后的结果,更新答案 27.图上两点之间最大边最小/最小边最大:瓶颈路问题,先求最小/最大生成树,变成树上问题 28.$ O(n^2) $优化的常见方法:数据结构(包括单调队列之类),前缀和,倍增...这几种方法在dp里尤为常见 29.需要在树上向上跳时常可考虑倍增 30.当最优化目标不止一个时:把多个目标量组合成一个量进行求解(比如自定义结构体或把两个数组合成一个大数之类的) 31.当$ n $不是很大,暴力不能解决,但是暴力可以解决$ \frac{n}{2} $(或类似)时,可以考虑折半