自二叉树开始吧
P2334 dfs 一遍字符串就行了
P2330 设字符串长度为 S,那么用暴力跑复杂度是 $ O(S^2T) $。但是有个 9 倍常数,理论上会挂。但是实际上根本跑不到那么多,所以可以过
P2011 因为是满二叉树,所以可以用数组模拟一遍树的操作,跑一遍就行了
P2274 NOIP2018PJT4,直接暴力 dfs,$ O(nlogn) $ 很稳
P2029 堆模板题,$ O(nlogn) $ 套模板就星
P2027 同滑动窗口,但是是用堆做的,用大根堆套上 pair 跑一遍,$ O(nlogn) $
P2020 这道题用堆做最低的复杂度是 $ O(nlogn) $,但是我没想出来,在暴力的基础上加上了一个特判,复杂度也从暴力的 $ O(n^2logn) $ 降到了 $ O(nlog^2n) $,意外的是跑的还挺快的,有开了 O2 和常数较小的原因吧
P2028 合并果子,每次 get 堆中最小的两个值,然后再将两数之和 put 到堆里面去,$ O(nlogn) $,在 COJ 上要开 LL,见祖宗 $ \times 1 $
P1419 杨辉三角递推 $ O(n^2) $
P2147 名字 tm 就叫最大子段和,用什么算法应该都知道了吧 跑一遍最大子段和,取一个最大值,没了 $ O(n) $
P2336 名字 tm 就叫最长上升子序列,用什么算法应该都知道了吧 跑一遍最长上升子序列 LIS,没了 暴力 DP $ O(n^2) $,通过二分优化后复杂度可以降至 $ O(nlogn) $
P2337 只要想到了 01 背包这题应该就做出来了,设 $ dp[i] $ 为在总和不超过 i 的情况下的最大值,那么 $ dp[j] = max(dp[j],dp[j-a[i]]+a[i]) $
P2338 又双叒叕是杨辉三角,比上面那题还简单些,几乎一模一样,不说了
P2340 这题题面必须给个好评,名字 tm 叫咸鱼翻身,希望我也有那么一天吧 废话不说多,开始讲题 这题首先要预处理一下,把翻过身的咸鱼(1)翻回去,变成 -1(千万要变成 -1!不能变成 0),然后再把没有翻身的咸鱼(0)翻身,变成 1,然后跑一遍最大子段和,将最大子段和加上初始状态下翻身的咸鱼数量,输出即可 这题是个多测,设共有 T 组数据,则复杂度为 $ O(TN) $,常数也并没有想象中的那么大
P2148 导弹拦截,LIS 跑一遍,不说了