代码练习

Posted on Edited on In Views:
排序、枚举、搜索（DFS）、动态规划（DP）、Floyd 最短路、表达式求和、倍增法求最近公共祖先

题目

单词排序

  • 代码
  • 简单的排序题，同时可以学习下 STL 中的如下函数
    • iterator unique(iterator it_1,iterator it_2);
      • 返回去重后的最后一个元素的下一个元素
      • 调用前需要先排序

垃圾炸弹

  • 代码
  • 暴力枚举所有点即可

放苹果

  • 代码
  • 简单递归
  • 记忆化搜索
    • 分类：有盘子不放，所有盘子都放
1
apple(m, k) = apple(m - k, k) + apple(m, k - 1);

Red and Black

  • 代码
  • 深搜
  • 找到起始点相邻的所有黑色格子
  • 输入输出格式比较麻烦

复杂的整数划分问题

  • 代码
  • 动态规划
    • 逐个尝试，状态转移的时候添加一维，表示当前拆分最小的数为 min_val
  • 注意一些细节，详情见代码
  • 输入有多组，注意复用
  • 记忆化

兔子与樱花

表达式·表达式树·表达式求值

  • 代码
  • 输出格式比较麻烦
    • 计算
  • 中缀转后缀
    • 准备一个栈
    • 遇到操作数，直接输出
    • 遇到左括号，将左括号压栈
    • 遇到右括号，弹栈输出，直到遇到左括号停止
      • 遇不到左括号则输入序列有问题
    • 遇到操作符，重复如下操作，直至条件不成立，最后将当前操作符压栈
      • 同时满足：栈非空、栈顶不为左括号、栈顶操作符优先级小于等于当前操作符
    • 最后弹空栈输出

Distance Queries

  • Floyd 算法 \(O(N^3)\)，TLE
  • 代码
  • 一些条件
    • 无向无环图
      • No two roads cross, and precisely one path.
    • 连通图
      • precisely one path (sequence of roads) links every pair of farms.
  • 构建一棵树
    • dist[x] 记录 x 结点到根的距离
    • 如果两个结点 \(a,b\) 的存在最近公共祖先 \(c\)
      • 结果为 \(\mathrm{dist[a]+dist[b]-2\times dist[c]}\)
    • 利用并查集优化判断是否在同一棵树中，或者增加一个虚拟结点
  • 基本思路
    • 深度大的点先找他的父结点，直到两个结点的深度一样
    • 然后一起向上找父结点，直到找到相同的父结点
  • lca：Least Common Ancestors

倍增法

  • 倍增法求最近公共祖先
  • 第一步，先让 x，y 跳到相同深度（不妨假设 x 深度更大）
    • x 与 y 的深度差可以表示为若干 2 的幂次的和，每次跳跃 \(2^i\) 个点，复杂度 \(\log(x-y)=O(\log N)\)
    • 这个差可以显式获取到
  • 第二步，要么是同一个点，要么一起往上跳
    • 同样的思路，lca(x, y) 与现在的深度差可以也可以可以表示为若干 2 的幂次的和，复杂度 \(O(\log N)\)
    • 这个差不能显示获取到，但是可以通过深度比较试出来
  • 具体实现见代码