本系列为《挑战程序设计竞赛》读书笔记,分为初级篇、中级篇、高级篇
初级篇目录:
- 穷竭搜索
- 贪心
- 动态规划
- 数据结构
- 图论
- 数论
1.穷竭搜索
a.核心思想:
- DFS :从某个状态开始,不断转移,直至无法转移,回退到前一步,再继续转移到其他状态,直到找到最终解;一般使用递归或者栈实现
- BFS 从初始状态开始,总是先搜索至距离初始状态近的状态。每个状态都只经过一次,因此复杂度为O(状态数*转移方式数);一般使用队列实现
b.优化细节:
- 剪枝:明确知道从当前状态无论如何转移都不会存在解的情况下,不再继续搜索而是直接跳过
- 特殊状态枚举:可行解空间多数可采用DFS,但当其比较特殊时,可简短地实现:
- 全排列使用STL中的next_permutation
- 组合或子集使用位运算
- 栈内存与堆内存:(所以一般算法竞赛中都使用全局数组,开的最大)
main函数中的局部变量存储在栈内存中,统一分配后不再扩大,影响栈深度,与机器设置有关。通常,C++中执行上万次递归是可行的。
new或malloc的分配的是堆内存,全局变量存储在堆内存中,使用全局变量代替局部变量可减少栈溢出的风险。
c.题解
- POJ 3009: Curling 2.0 :
/* * POJ 3009: Curling 2.0 * 题意:m*n矩阵中,给出起点、终点、空格、障碍,从每个点可向4方前进,直到遇到障碍,打碎并停在障碍格的前面。求到达终点的最少前进次数。 * 类型:DFS+记忆化搜索 * 算法:从某点出发,向4个方向投掷,遇到障碍格,标记其为空格状态,继续递归障碍前一点,回退恢复障碍状态。每次递归直至到达终点或全部出界失败。 */
- AOJ 0558: Cheese
/* * AOJ 0558: Cheese * 题意:m*n矩阵内,给出起点、1~N表示N个工厂、障碍、空格。求按顺序遍1~N的最短路。 * 类型:BFS+Queue(/Dijkstra) * 算法:从S顺序通过1~N的最短路,可以用BFS求N次相邻序号间最短路的和。 */
/**
* 要求顺序遍1~N的最短路径,可以每次用bfs求出相邻两点的最短路,然后加起来
* 因为bfs每次都是直接遍历所有周围的点,所以搜到终点时,d[x][y]表示的一定是直接走最短的路;
*/
- POJ2718 : Smallest Difference (穷竭搜索+全排列)
/* * POJ 2718: Smallest Difference * 题意:给出不重复升序单数字,将其分为两组打乱顺序后组成整数,求两个整数的最小差值。 * 类型:穷竭搜索+全排列 * 算法:将序列全排列,按长度均分成两组,计算每个排列下的差值。 */ #include <cstdio> #include <iostream> #include <sstream> #include <algorithm> using namespace std; /** * 题意:0-9数字分成两部分,随意组合,求能使得这两个数绝对值差最小的情况的差 * 算法:肯定是将数组对半分,然后求所有的全排列的差的最小值 * c++中全排列用到:next_permutation */ int n, res; int nums[10]; int d[2]; const int INF = 10000000; int array2num(int s, int t) { int num = 0; if (nums[s] == 0 && s + 1 < t) return -1; for (int i = s; i < t; i++) { num = num * 10 + nums[i]; } return num; } void helper(int index) { int x = array2num(0, index); int y = array2num(index, n); if (x != -1 && y != -1) { res = min(res, abs(x - y)); } } void solve() { int x, y; do { //n可能为偶数也可能为奇数,需要分开考虑 if (n % 2 == 0) { helper(n / 2); } else { //n为奇数,则分给左边多和右边多的结果不一样,要分开考虑 int s1 = n / 2; int s2 = (n + 1) / 2; helper(s1); helper(s2); } } while (next_permutation(nums, nums + n)); } int main() { int case_n; cin >> case_n; cin.get(); while (case_n--) { n = 0; res = INF; string str; getline(cin, str); stringstream ss(str); while (ss >> nums[n]) n++; solve(); cout << res << endl; } }
2.贪心
a.贪心思想:
贪心就是遵循某种规律,不断贪心选取当前最优策略
b.贪心证明:
- 与其它选择方案相比,该算法并不会得到更差的解(归纳法)
- 不存在其他的解决方案(反证法)
3.动态规划
a.核心思想
- 动态规划(DP):通过定义某种最优子状态,进行状态间转移达到最终解。
- 记忆化搜索:将重复状态通过标记降低复杂度。
- 多种形式的DP:搜索的记忆化或利用递推关系的DP,或从状态转移考虑的DP。状态定义和循环顺序都会影响复杂度。
b.优化细节
- 使用memset初始化
- 重复循环数组
- dp仅bool是一种浪费
- 根据规模改变DP对象
c.经典模型
- 背包问题(01背包,完全背包)
- 最长子序列(LCS,LIS)
- 划分数类型:就是n的m划分(第二类Stirling数,Bell数):
面试题中的比例:
- Matrix DP (10%) :
- Sequence DP(40%) 最长回文子序列,单词拆分,分割回文串;dp不仅对于求解最优问题有效,对各种排列组合的个数、概率或者期望之类的计算同样有用;
- Two Sequences DP (40%)
- Backpack (10%)