2020-09-05

BFS

初始化：与初始点相关的状态放入队列中
while (队列非空) {
  取队列最前面的状态
  将该状态弄出队列
  将该状态的状态标记为visited
  然后判断状态是否满足要求，进行操作
  对状态进行“展开”，即对状态可以到达的点进行循环
  对上述选出的状态进行过滤，过程如下：
    1.看有没有visited
    2.看该状态是否越界
  将过滤完的状态放入队列尾部
//  将过滤完的状态标记为visited
}

队列的使用：queue<类型> q,

• q.push(k)(将状态k放入队列尾部),
• q.empty()（检查队列是否为空）,
• q.pop()（将队列最前面的状态弄出队列）,
• t = q.front()（得出队列最前面状态t）
  对于BFS在楼梯一题中的应用：
  每次可向上或向下走楼梯的长度（但不能越界），也可以向左或向右走一格（同样也不能越界）
  对于BFS在跳马问题中的应用与其在楼梯问题中的应用相似

快速幂

快速幂的存在可以将a^b除以一个数的余数可以较快算出来，比如可以由的平方推出来。快速幂通过计算低次幂的，累计相乘得到高次幂的余数，其复杂度由O(n)变为了O(logn)

DP记录路径的方法

记录方法是用二进制的角度看待这样一个问题，比如longlong有64位，每一位的1表示选中，每一位的0表示未选中，假如现在的状态是n这样一个数，而对于第m个物体，如果我们要将它选上，则应进行操作n|1<<m, 若要将它不选上，则要进行操作n异或1<<m这样就可以将第m位不选上，如果想要判断第m位上有没有选上，那么就可以使用n&1<<m检查这个值是否为n即可，但是更多位下的（如超过64位的）还没有解决的思路。