📑Plan

• 动态规划

  • 背包问题

    POJ-1837

    POJ-1276

    POJ-1014

  • 动态规划

    POJ 1018

    POJ 3267

    POJ 1260

    POJ 1015

    POJ 3176

    POJ 1080

    POJ 1159

    POJ 2533

    POJ 1836

    Leetcode 70

    Leetcode 309

• 搜索

  • DFS

    POJ 2488

    POJ 3083

    POJ 3009

    POJ 1321

  • BFS

    POJ 3278

    POJ 1426

    POJ 3126

    POJ 3414

    POJ 2251

  • 简单搜索技巧和剪枝

    POJ 1010 ⭐

    POJ 2362

    POJ 1011（搜索+剪枝）

    POJ 1416

    POJ 2676

    POJ 1129❔

• 数据结构

  • 串

    POJ 1016

    POJ 1035

    POJ 3080

    POJ 1936

  • 排序（快排）

    POJ 1007

    POJ 2388

    POJ 1804

    POJ 2299

  • 高效查找

    POJ 1002

    POJ 3349

    POJ 3274

    POJ 1840

    POJ 2002

    POJ 3432

    POJ 2503

    Leetcode 33

  • 哈夫曼树、优先队列

    POJ 3253

  • trie树

    POJ 2513

  • 双指针

    Leetcode 15

  • 二叉树

    Leetcode 94

    Leetcode 102

    Leetcode 124（dfs）

  • 哈希

    Leetcode 454

  • 栈

    Leetcode 227

• 字符串

  • KMP算法:ghost:(不够熟练)

    POJ 3461

• 图算法

  • 图遍历（前序、中序、后序）

    POJ 2255

  • 最短路（Bellman-Ford/SPFA/Dijkstra）

    POJ 1860

    POJ 3259

    POJ 1062

    POJ 2253

    POJ 1125

    POJ 2240

  • 最小生成树(Prime)

    POJ 1789

    POJ 2485

    POJ 1258

    POJ 3026

  • 拓扑排序(Kahn)

    POJ 1094

  • 二分图的最大匹配​👻(不够熟练)

    POJ 3041

    POJ 3020

  • 最大流

    POJ 1459

    POJ 3436

• 基本算法

  • 枚举

    POJ 1753

    POJ 2965

  • 贪心

    POJ 1328

    POJ 2586

  • 构造法

    POJ 3295

    POJ 3239

  • 分治法

    Leetcode 395

  • 模拟法

    POJ 1008

    POJ 1068

    POJ 2632

    POJ 1573

    POJ 2993

    POJ 2996

    POJ 3087

  • 高精度算法

    POJ 1001

    POJ 1503

    POJ 2109

    POJ 2389

    POJ 2602

    POJ 3982

    Leetcode 2

• 北大叉院2019

  POJ 1064

  POJ 1321

  百练 3421

  百练 4128

  POJ 1185

⭐READ

• Manacher’s Algorithm

  *O(n)*时间复杂度寻找字符串中的最长回文子串

• POJ试题分类

🚏TODO

• KMP
• 背包问题及其变种
  • 多重背包
    • 二进制拆分
    • O(Vn)解法
• DP 🛩️ 🛩️ 🛩️ 🛩️ 🛩️ 🛩️
  • 最大子段和
  • 最长递增子序列(LIS)
  • 最长公共子序列(LCS)
• 最短路 🛩️
  • Floyd
  • Dijkstra
  • Bellman-Ford(检查出的是包含源点的负环还是所有负环？)
  • SPFA
• 并查集 🛩️
• BFS 🛩️ 🛩️
• DFS 🛩️
• 贪心 🛩️
• 二叉树遍历 🛩️
• 输入输出整理
  • long long ("%lld")
  • double("%lf")

🛰️Knowledge

• 闰年：能被4整除且不能被100整数；能被400整除

• 使用BIT时需要特别注意，当idx为0时update会陷入死循环

• 滚动数组

• 有整数求和操作时注意是否需要使用long long !!! 有double时一定要小心不要将其赋给整形变量

• 欧拉图（一笔画问题）

  • 联通无向图存在欧拉路径的充要条件：度数为奇数的结点的数目等于0或2
  • 联通无向图存在欧拉回路的充要条件：每个结点的度数均为偶数
  • 联通有向图可以表示为一条从u到v的欧拉路径的充要条件：u的出度比入度多1，v的出度比入度少1，其他结点的出度和入度相等

• 拓扑排序

  • Kahn算法（前驱结点法）

• 二分图

  • 判定
    • 黑白染色
  • 最大匹配
    • 匈牙利算法
  • 最小点覆盖
    • 求出一个最小的点集，使得图中任意一条边至少有一个端点属于点集
    • 最小点覆盖包含的点数=最大匹配包含的边数
  • 最大独立集
    • 任意两点之间都没有边相连的点集
    • 二分图最大独立集包含的点数=二分图的总点数-二分图的最大匹配数
  • 最小边覆盖
    • 选出尽量少的边，使得每个点至少是一条选出的边的端点
    • 最小边覆盖的边数=二分图总点数-二分图的最大匹配数

• 快速排序优化

  • 随机选取基准
  • 三数取中
  • 小数组使用插入排序

• C++ 稳定排序 stable_sort

⛏️Skill

• 化归策略

  • POJ 1014 判断sum是否平分，转换为是否可以将物品放到sum/2的背包中

• 位运算技巧

  • n&(n-1) 将n的最后一个1变为0

❔Problem

• 图着色问题与最大团是否等价？（仿佛有个反例）

  A-B B-C C-D D-E E-A

😙Key

• POJ 1018
• POJ 1260
• POJ 1837
• POJ 3274
• POJ 2513

🌟Star

• https://github.com/flyhero99/BaoYanJiShi
• Leetcode题解
• Leetcode题解
• 二分查找的总结