bzoj题解汇总(1052~1061)

时间:2021-10-28 15:21:57

bzoj1052:

贪心

bzoj1053:

DFS

bzoj1054:

加深迭代搜索

bzoj1055:区间判定性dp

bzoj1056:

Treap

bzoj1057:

二分,单调队列 / ST表。

普通dp。

bzoj1058:

非旋Treap优化模拟。

bzoj1059:

二分图匹配。

bzoj1060:

树形dp,弄出记录子树内叶子节点的个数,以及最大的距离。

再贪心地DFS一遍。

bzoj1061 :

对偶原理

裸单纯形。

【小结】问题解决的一般性思路

(1)特性分析:分析题目的特性,挖掘更深层的东西

(2)转化:根据题目特性,转化问题的性质(如二分),或者代数方法,或者几何方法进行转化

(3)逐步满足:思考当前问题的一个子问题,将子问题与当前问题建立联系

(4)阶段性解法:即动态规划或者贪心,将问题分阶段解决

(5)离线处理:离线算法用空间换时间,可以用在线的所有算法,还有特殊算法。

回代,分治,确定左端点移动右端点,DFS,莫队,Two Pointer,定期重建,区间赋予状态,etc

(6)平衡规划:分块。将几种复杂度基质不同的算法有机地结合起来,得到一种更优的方法。

恩这次应该找到了一些精髓所在。