蓝桥杯赛前总结: 记录一些经典算法(二)
目录
* dfs/bfs
* 动态规划
* 位运算
* 日期枚举
* 最后一点: C/C++的对拍小技巧
dfs/bfs
dfs/bfs为最常用的搜索算法, 需要找好解空间的状态和终止条件。
例题: 小朋友崇拜圈
班里 N 个小朋友，每个人都有自己最崇拜的一个小朋友（也可以是自己）。
在一个游戏中，需要小朋友坐一个圈，每个小朋友都有自己最崇拜的小朋友在他的右手边。
求满足条件的圈最大多少人？
小朋友编号为 1,2,3，⋯N。
思路: 我们使用 dfs 从每一个小朋友 i 开始搜索, 看看从 i 出发最大的圈为多少, 全局定义一个变量然后更新最大的圈长。
这题有意思的是dfs边界条件，当我们记录的圈长 > N时说明从 i 出发得不到一个圈, 因为极端条件下最大得圈只能是 N。
例题2.分考场
n 个人参加某项特殊考试。
为了公平，要求任何两个认识的人不能分在同一个考场。
求最少需要分几个考场才能满足条件。
分考场有两种状态, 一种是新开一个考场，另一种是往之前得考场里面安排座位, 接着通过 dfs搜索回溯即可:
例题3.气候变暖
dfs版本:
bfs版本:
动态规划
1. 0-1背包问题
根据闫式DP分析法, 我们设状态f[i][j]表示的子集为在前 i 个物品中选取不超过重量 j 的最大价值。
我们考虑最后一组情况 f[i][j], 对于第 i 件物品, 我们只有选和不选两种情况，于是我们的状态转移方程为:
f[i][j] = max(f[i-1][j], f[i-1][j-w[i]+v[i])
2. 完全背包问题
状态表示与 01背包问题是一样的，我们对第 i 件物品有 k 种选取情况(可以选 0, 1, ... , k件), 那么状态转移方程为:
f[i][j] = max(, f[i - 1][j - k * w[i]] + v[i], ...)
来个枚举可能的 k 值的朴素写法, 时间复杂度: O(n^3):
f[i][j] = max(, f[i - 1][j - k * w[i]] + v[i], ...)
递归地根据定义:
f[i][j - w[i]] = max(f[i - 1][j - w[i]], f[i - 1][j - 2w[i]] + v[i], ...)
那么我们就可以把状态转移方程化简为:
f[i][j] = max(f[i - 1][j], f[i][j - w[i]] + v[i])
于是我们可以将时间复杂度降低到 O(n^2):
1.例题:砝码称重
先来个 dfs 版本:
dp解法, 我们设状态dp[i][j] 为在前 i 个砝码中是否能称出重量 j, 那么在第 i 个状态中有放左边，不选，放右边 3 种情况, 那么状态转移方程为:
f[i][j] = max(f[i - 1][j], f[i - 1][abs(j - a[i])], f[i - 1][j + a[i]])
3. 线性dp问题
这个没有固定的模型, 只能依靠数学关系现场推导.不过状态的设置也是个技术活，而且需要靠大量的经验(希望可以灵光一现吧。。。）
位运算
大写转小写, 小写转大写:
二进制的状态压缩:
我们要优化空间复杂度时, 我们可以一个二进制整数来表示集合中的状态(前提是集合中每个元素只有0和1两种情况)
取出 n 在二进制表示下的第k位 (n >> k) & 1
把整数n在二进制表现下的第k位取反 n xor (1 << k)
把整数n在二进制表现下的第k位赋值1 n | (1 << k)
把整数n在二进制表现下的第k位赋值0 n & (~(1 << k))
日期枚举
最不容易错的方法是一天一天地枚举，同时注意日期合法性。
C/C++的对拍小技巧
当你想到个优化方法来优化暴力法时, 就要确定好这个方法得出来的结果是和暴力法一样的。下面就来介绍一个对拍的方法来检验你的程序。
对拍其实很简单，改改源程序然后用 dos 命令就可以了, 下面介绍在 windows 下如何实现对拍:
./a1.exe > A.txt 指的是运行 a.exe，把结果输出（>）到 A.txt 中
./a2.exe > B.txt
A.exe < in.txt > C.txt 指的是运行 A.exe，从 in.txt 中读入（<）数据，把结果输出（>）到 C.txt
然后使用 fc 命令就可以显示出两个文件的差异了:
fc A.txt B.txt
不过我们要改写一下源程序(最后备份一下), 改成像 codeforces 那样 改成批量循环就可以了, 然后构造一个 in.txt 文件, 或者随机生成输入值放入in.txt里面。
当然, 前提是自信--你的暴力代码是正确的。。。
最后, 没思路可以去去洗手间(不是去作弊哦)，是因为可以走动一下, 毕竟比赛过程长达个4小时的久坐。
