算法竞赛进阶指南 0x00 基本算法

放在原来这个地方不太方便,影响阅读体验。为了读者能更好的刷题,另起一篇随笔。

0x00 基本算法

0x01 位运算

[题目][64位整数乘法] 知识点:快速幂思想的灵活运用

[题目][最短Hamilton路径] 知识点: 状压DP。我的题解总是写得不好,大家还是看书吧qwq

P2114 [NOI2014]起床困难综合症 知识点:状态压缩

0x02 递推与递归

[题目][费解的开关] 知识点:搜索?递推?模拟? +状压

[题目] 4座塔的Hanoi 知识点:递推

[题目][约数和问题] 知识点:数学+分治

0x03 前缀和和差分

[HNOI2003]激光炸弹 知识点: 二维前缀和模板

[题目] [IncDec Sequence] 知识点: 对差分的理解

P2879 Tallest Cow 知识点: 差分

0x04 二分

[题目] [Best Cow Fences] 知识点: 二分+前缀和做最大子段和

给你一个正整数序列 (a[]) 求一个平均数最大、长度不小于 (L) 的连续子段

0x05 排序

[题目][货仓选址] 经典问题,洛谷期中考试部分分考过,选中位数。

[题目][七夕祭] 一道好题。看起来很复杂,其实可以抽象成两次“环形均分纸牌”问题,再经过思考分析,可以再转化成“均分纸牌”+“货仓选址”两个基本问题。

这也启发到我们(引用书上原话):这个问题的每一步都仅用到基本算法的性质,最后转化成了简单而经典的问题。我们应该时刻把各种模型之间的简化,扩展和联系作为算法学习的设计脉络,以点成线,触类旁通,才能产生数量到质量的飞跃。

[关于动态维护中位数] 有一种叫做“对顶堆”的做法。 开一个大根堆一个小根堆,把 (1)(frac{m}{2}) 的数储存在大根堆里,把 (frac{m}{2}+1)(m) 的数储存在小根堆里,这样两个堆的堆顶都在中心位置,就可动态维护中位数了,很好理解。

0x06 倍增 和 0x07 贪心

今天把0x06倍增 和 0x07贪心 都看完了,书上实在是讲得太好了。题外话:后天就要开学考试了!

0x08 总结与练习

[题目+Code][The Pilots Brothers' refrigerator]

[题目(模拟)] [占卜DIY]

P2862 [USACO06JAN]把牛Corral the Cows 乍一看是一个二维前缀和,考虑要离散化。突破口在判定这里,考虑二分。大佬们用扫描线+二分,我这个蒟蒻在这里就不多bb了。

原文地址:https://www.cnblogs.com/BaseAI/p/11448592.html