思想思路集萃
继承、状态等量关系、递推
当需要同时求解多个同类的信息,但是这些信息逐个暴力计算会超时的时候,可以尝试发现这些值之间的关联性、建立方程进行递推或者转移。
如果这种递推是从一个更小的范围得来的,那么这就是一种 DP 的求解思路,如果这种递推是在相同或者说等价的范围进行的,这就是一种快速处理多个值的方法。
划归
先得到一种特殊的情况的解法,再尝试将一般情况转化为特殊的一种或者几种情况,进行求解。
答案集合、求解转判定
如果直接求解是困难的,可以考虑对一个可能的答案进行判定,不断缩小答案集合,最后的道正确的答案。
这里的直接求解是指,对于已有的信息,进行不断地计算,最后给出的答案是一个正确的答案。而判定的答案不一定是正确的。判定是在不断获取信息,减少可能性。
当答案具有单调性的时候,可以二分的缩小答案集合,当答案不具有单调性的时候,可以通过枚举等方式,检查答案集合。如果有别的性质做到快速缩小答案集合,这自然也可以。
- 题目:2024.6.12T4
贪心、可行性、最优性
一种决策一定是最优的,一种状态一定是可行的,这种决策不一定严格优于其他决策,只要不劣于其他决策即可。
相同信息、等价状态
反复调用相同的信息,可以考虑先将其计存下来,减少计算时间,或是将相同的信息放在一起,使得调用更加连续,这样将其当作常熟,优化处理。对于等价的状态,只需要算出其中一个状态的答案就行了。
划分、分组
将一个事物划分为多个部分,或者将一些状态划分为多组,分别计算出每个部分的答案,最后合起来就是最终的答案。
划分的难点在于如何划分,可以利用划分后状态之间的相关性、无关性进行求解。
相关性可以简化多余计算,比如继承、状态等量关系、递推关系,达到快速计算的效果。
无关性可以使得状态分别处理,特别是当原式相关限制比较复杂的时候,这往往可以从乘法的时间变为加法的时间。
有时我们也可以对数据范围进行划分,在不同的范围下计算使用不同的算法,合并得到答案,比如“根号分治”算法。
- 题目:2024.6.8T2、2024.6.8T3、
平衡
让两个操作的代价平衡,而不是偏向一边。
根号操作分治,根号平衡、许多数据结构都是利用这个想法,但是各种数据结构都是对于单次操作经行平衡的,然而在题目中,会出现一个本身就偏袒的现象,此时便应该向另一边篇,以达到平衡。
- 题目:
归纳
当初始合法,当一个状态合法下一个就合法,那么所有都合法。
数学归纳法,多用于证明结论
递归也用到了这个思想。
标签:状态,题目,思想,2024.6,求解,集萃,答案,思路,递推 From: https://www.cnblogs.com/lupengheyyds/p/18303049