问题 给出一个若干个圆，将他们放到矩形框中，与矩形框的下底面相切，圆与圆之间不可以相交，求一个圆的排列方式使得所有圆中最左侧的点到最右侧的点距离水平距离最小 解析 计算两圆左右两侧距离 如图所示，对于现切的两个圆，他们两个圆心之间的距离可以通过勾股定理计算，设距离为则，而对于如图所示的两圆最远端的水平距离为 如图所示， 此时两圆的最远距离为 互换同理，计算新加入的圆时需要同时记录最右侧和最左侧的位置其中右侧的距离为的圆心位置 如图所示，后加入的圆可能不与相邻的圆现切，而是与前面的圆现切新加入一个圆后的计算方式 依次计算新加入的圆与已经加入的圆的现切形成的圆心位置，容易得出新圆的圆心位置...

问题 给出一个个点的连通图,用至多种颜色对图上每个点进行染色，要求任意两个有边直接相连的点不可以同色，染色方案数有多少种，输出方案数，若不存在这样的染色方案输出 解析 本题可以使用分支限界的方法来计算，尝试对每个点进行染***r>剪枝的情况： 1.如果当前尝试染色的点已经有颜色，则不需要继续枚举 2.如果当前尝试染色的点周围已经有相同的颜色，则不需要继续枚举 采用深度优先搜索+回溯的方法来 设计 未染色点个数=n dfs（当前点，尝试染的颜色）： 遍历所有与当前点相连的点 如果存在同色的点，则直接退出 给当前点染色，未染色点个数-1 如果未染色点个数=0 染色方案+...

问题 给出一些字符和这些字符的出现频率，对这些字符用二进制进行编码，使得任意一个编码不是另一个编码的前缀，且编码的加权长度和最小。 解析 显然对于出现频率高的字符用更短的二进制进行编码，对出现频率低的字符用更长的二进制进行编码会得到编码加权长度和最小的结果。这个问题可以用哈夫曼编码树来解决。哈夫曼编码1.取出所有数字中出现频率最低的两个，作为二叉树上的两棵子树，两者频率之和作为这两颗子树的根2.将根作为新的节点投入序列中3.重复1，2操作直到序列中只剩一个点4.以最后一个点为根，遍历整颗二叉树，以经过的路径作为字符的编码，向左子树移动记为1，向右子树移动记为0 设计 priority_queu...

问题 给出若干个节目在同一个舞台演出，每个节目需要占用一段时间的舞台，用起始时间和结束时间表示。不同的节目占用舞台的时间不可以有重叠，如何安排可以被安排上的节目数量最多。 解析 对所有节目按照结束时间升序排列，按顺序排列不冲突的节目，最终得到的就是不冲突节目数量最多的安排证明： 定理1：设时间区间的最优解为,,其中一定是区间的最优解 证明： 若不是区间的最优解，则存在,显然,这与是最优解相悖，所以一定是区间的最优解 定理2：设是区间中最早结束的事件，则在区间的其中一个最优解中 证明： 设区间的一个最优解为,若事件是中最先发生的一个事件，事件为区间内最早结束的事件，结束时间为记作，则 若，...

卡特兰数 卡特兰数的基本公式 通项公式变形公式递推公式 基本形式 给出个元素，其中个元素，个元素，要求对于由两种元素按顺序排列组成的序列中，任意一个前缀的数量不少于,有多少种组合方式 个节点的二叉树共有多少个 可以将一棵二叉树分为根，左子树，右子树三部分，枚举左子树节点个数，则共有种不同的二叉树

问题 给出两个序列,求出一个序列使得同时是和的子序列，且的长度最大 解析 给出一个动态规划的做法令表示序列的前项和序列的前项的最长公共子序列那么就有 最优子问题证明 已知是序列的前项和序列的前项的最长公共子序列 当时，假设存在,则即存在与已知不符，假设不成立 当时，假设存在,则与已知不符，假设不成立，情况同理可证设计 const int maxn = 1010; int dp[maxn][maxn]; int s[maxn], t[maxn]; int ds[maxn][maxn], dt[maxn][maxn]; int main() { int n, m; scanf("%d%...

miller_rabin素性测试 给出一个非常大的数，判断它是不是素数对于较小的数，可以枚举内每一个数试除，若能整除则非素数，这么做的复杂度为对于较大的整数，如级别的数，不够用了所以去学了一下miller_rabin测试法miller_rabin测试法是一个随机算法，虽然不能保证完全正确，但是判断64位整数范围内的数够了(大概 费马小定理 若是素数且，则我们可以随机的枚举范围内的数，若不符合上述定理，则显然是合数但是这个定理只是必要条件，并不是充分条件存在一类叫做卡迈克尔数的数，也满足上述条件，但是他们是合数，比如 二次探测定理 若是奇素数，则的解要么是,要么是证明 因为，所以 所以 所以 ...

问题 给出一个长度为的序列表示个矩阵其中分别表示第个矩阵的行和列将个矩阵按顺序相乘，最少需要做多少次乘法 解析 对于行列分别为和的两个矩阵相乘，共需要次乘法同时对于矩阵乘法，满足结合律但不满***换律，即例如：对于序列表示矩阵 按照原顺序，总运算次数为 先对后两项做乘法，总运算次数为 显然不同的结合顺序会使总运算次数产生很大区别做法：我们考虑用动态规划的方法来解决这个问题令表示第到各矩阵按一定顺序相乘的最小乘法次数则 证明满足最优化法则 已知是当前子问题的最优答案 假设不是最优的子问题答案，即存在 那么 也就是存在更优的，这与之前的假设相矛盾，得证 设计 for (int i =...

问题 给出个投资项目，每个项目有种投资方式第个项目第种投资方式需要花的钱，最后会得到的钱现在你有共有总量为的钱，合理分配，最终最多能赚多少钱 解析 令表示前个项目共花费元能够得到的最大价值则选择第个第种投资方式能得到的最大价值应该是证明:的任意一个确定状态的子决策都是此状态下的最优决策 已知是前个项目共花费元能够得到的最大价值 假设子决策不是这种状态下能得到的最大价值 那么一定存在另一个子决策 用这个子决策替换原来的子决策，必然可以得到一个更大的,这与之前的假设想冲突，因此不存在这个一个 得证 设计 for (int i = 1; i <= n; ++i) { ...

问题 给出序列求出其中第小的元素 解析 这里给出分治算法的做法 按个一组对整个序列分组排序，选出每组中的中间项 对所有的中项进行排序，选出中位数 用中位数进行划分 所有比中位数小的放到中位数前面，比中位数大的放到中位数后面 若前面的数少于个，则在后半部分寻找第个，其中表示前半部分的元素个 若前面的数等于个，则当前所选取的中位数就是答案 若前面的数多于个，则在前半部分寻找第小设计 // #pragma GCC optimize(3,"Ofast","inline") #include <cstdio> #include <cma...

问题 给出平面上若干个点，两点之间的距离为两点之间的曼哈顿距离，求这些点的最小生成树例题传送门两点的曼哈顿距离： 定理 对于图上任意一个环，环上边权最大的边一定不在最小生成树上证明： 环上至少有一条边不在最小生成树上，若环上所有边都在最小生成树上，那不满足树的性质 在树上任意断开一条边，最小生成树必然分成两棵子树 假设环上边权最大的边在最小生成树上，在最小生成树上断开这条最大的边，新产生的两棵子树显然可以通过连接原先环上的边重新形成一棵树，而这条边的权值显然小于已经断开的边，所以总权值变小了，与原先的树是最小生成树相矛盾 做法 分析 根据上述定理，显然图中的蓝色边是不需要连接的...

问题 给出平面上一系列点，求任意两点之间欧几里得距离的最小值 解析 记作两点之间的欧几里得距离 暴力做法 很容易想到对这个问题暴力求解的方法，对于每一个点,计算它与其余所有点之间的距离，取最小值即可 时间复杂度为 分治策略 首先按照分治策略的基本套路，一般都是将问题分解为若干个子问题，然后将子问题的结果合并为大问题的结果 首先考虑分治的终点 显然当所求的点只有两个的时候，最近距离就是两点间距离 当所求的点有一个的时候，可以取最近距离为无穷大(一个答案肯定无法取到的极大值) 考虑如何合并子问题 对于整体的答案，可以分为两类，一类为子问题的最近距离(所有点都取子问题内的)，一类为子问题之间的...

问题 二分归并排序：对个不同的数构成的数组进行排序，其中 解析 归并 将任意的两个升序序列和合并为一个升序序列主要步骤比较序列中的首元素和序列中的首元素若则将加到序列末尾，否则将加到序列末尾重复以上操作直到序列或序列为空将非空序列直接加到序列末尾正确性证明对于升序序列和，将两个序列的首元素分别记为和因为和是升序序列，所以有若则,此时就是两个序列中最小的，将放入序列末尾中即可 此时序列中最小的数变为了同理，当只需将放入末尾即可因为每次放入序列末尾的元素总小于中其他元素，也就是也就说也是一个升序序列复杂度每个元素会被放入序列一次，若序列长度分别为，则总操作次数为,归并操作的复杂度为 归并排序 我们...

问题 一般问题的形式为给出一个条件，问一段区间内符合要求的数的个数 举例 HUD-2089 不要62 题意 给出一个区间，求区间内没有连续"62"且没有"4"的数的个数 思路 暴力直接暴力枚举区间内每一个数来统计搜索用深搜的思想实现，比如求0~234之间符合条件的数的个数，可以先枚举第一位，再枚举第二位，再枚举第三位，需要注意的是，当第一位枚举为1时，第二位的范围只能是0~2，同理当前两位为“12”时，第三位只能是0~3记忆化观察可以发现，在枚举第一位为1的时候，后两位的枚举其实和第一位为0时一样，都是00~99，所以可以记忆化，节约下大量时间我们可以设...