Cedeat的摸鱼中心
  文章分类
算法入门 24 算法进阶 5
质数 质数
质数质数的判定-试除法质数的因子一定是成对出现的，因此不必枚举所有的因子，只要枚举其中较小的因子，也就是一半的因子即可。而较小因子的上限是sqrt(n)，所以只需到sqrt即可。 #include <bits/stdc++.h>
2022-02-04 算法入门
算法 数论
记忆化搜索 记忆化搜索
记忆化搜索记忆化搜索有点像搜索+初始化判断，通过保存过去的结果，可以避免重复的搜索，以此达到更快的时间。 f[a] [b]表示走到a，b这一点的最大距离，因此f[a] [b]如果不为初始化的值，则一定是最大值，我们不必再重复搜索 #incl
2022-01-05 算法入门
算法 动态规划
状态压缩DP 状态压缩DP
状态压缩DP状态压缩本质上就是用一个二进制数来表示出所有的状态，从而方便用位运算节省速度。 蒙德里安的梦想要找到所有的方案数，我们需要找到所有横放1x2方格的合法方案数，当横放数量确定后，竖放的方格只需插入即可。 状态表示：用f[i] [j
2022-01-05 算法入门
算法 动态规划
树形DP 树形DP
树形DP状态表示： 树形DP的状态集合有两个f[u, 0]和f[u, 1]，分别表示所有从以u为根的子树中选择，且不选u这个点的方案，和选这个点的方案。 首先对于f[u, 0]，因为它没有选择u这个点，因此子节点自由选择，可以由f[j ,
2022-01-05 算法入门
算法 动态规划
计数DP 计数DP
计数类DP整数划分可看作是完全背包问题的改版，将1~n的数看作体积，每个物品使用无限次，恰好能装满背包体积n的总方案数。 注意初始化时，我们要求的与完全背包不同，完全背包要求最大的价值，该题要求最大的方案数，因此我们至少有一种方案，应该全部
2022-01-04 算法入门
算法 动态规划
背包问题 背包问题
背包问题背包问题是一类很大的问题，很多问题都能转化成背包问题。 01背包01背包问题的特点是所有物品仅能用一次 状态转移方程 f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]); 二维版
2022-01-04 算法入门
算法 动态规划
数位DP 数位DP
数位DP感觉是一种出现很多次的题然而我一次都不会（（ 数位DP的核心是分情况讨论，找到一个第j位，表示第j位上数字i出现了多少次，最后将每个位数上数字i的出现次数相加即是总和。 对于一个数abcdefg，假定第j位是d，那么有如下可能： （
2022-01-04 算法入门
算法 动态规划
区间DP 区间DP
区间DP区间DP的核心是每次都将左边一堆与右边连续的一堆合并 状态表示：f[i] [j]表示将i到j合并为一堆的方案的集合的最小值。 状态计算： f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] +
2022-01-03 算法入门
算法 动态规划
拓扑排序 拓扑排序
拓扑排序什么是拓扑排序？若一个由图中所有点构成的序列A没满足：对于图中的每条边(x,y)，x在A中都出现在y之前，则称A是该图中的一个拓扑排序。只适用于有向无环图（AOV网）。 入度想要找到拓扑排序，我们要了解入度的概念：指有向图中某点作为
2021-12-24 算法入门
算法 图论/搜索
深度优先搜索 深度优先搜索
DFS（深度优先搜索）DFS使用栈的数据结构，指对所有可能的分支进行一次搜索，优先向下走，直到不能搜索为止，当搜索到头没有路时进行回溯，或在不满足条件时剪枝，然后再次找到别的路径深入。它所找到的不一定是最短路。 全排列问题#include
2021-12-16 算法入门
算法 图论/搜索
宽度优先搜索 宽度优先搜索
BFS（宽度优先搜索）宽度优先搜索最大的优势是可以搜索到最短路，然而在空间上要比DFS上大一些。BFS是一层一层向外搜索，先搜索所有距离为1的点，再搜索所有距离为2的点，以此类推，所以搜到的点是逐渐离我们越来越远的，找到的第一个即为最小，前
2021-12-16 算法入门
算法 图论/搜索
并查集 并查集
并查集并查集的作用1.进行集合合并。 2.查询两个元素是否处于同一集合。 并查集的原理用树的形式维护所有的集合 每个集合用一颗树来标志。树的编号就是整个集合的编号。每个节点储存的是他的父节点，p[x]表示x的父节点。 例： 对于一个元素3，
2021-12-14 算法入门
算法 数据结构
2 / 2