Kruskal4668

摘要： Codeforces 232B Table。 蒟蒻模拟赛上场切的一道蓝，非常难以置信我竟然能做蓝题。 这题的数据范围初看还是比较坑的，\(10^{18}\) 的值域很容易让人往矩阵加速那方面想。实际上在列出转移方程式后，我们发现状态是二维的，无法使用矩阵加速（或者说这样做很麻烦）。 思路 首先观察到 阅读全文

摘要： 概率基本知识 套路 dp 常用正推的方式，从起始状态到目标状态。 实际要根据是起始和目标状态哪个好确定、哪个好想来决定，这个没有限制，大部分题两种顺序都可以。 常用公式 贝叶斯公式：\(P(A|B)=\frac{P(B|A)P(A)}{P(B)}\)。 几何概型。构造几何模型之后求面积即可。 几何分 阅读全文

摘要： 双倍经验：Luogu P5089 元素周期表 ，CF1012B Chemical table：模拟赛搬的好题，有点厉害。赛时10min码的假贪心拿了五十多分，赢。 并查集思路 1 对于此类棋盘整行整列覆盖问题，有一个通用思路：把每一行和每一列看作一个点，那么原本棋盘上的格子就可以看作是连接这些点的边 阅读全文

摘要： 线性结合状压的 dp。 阅读全文

摘要： Piggy and Trees：把路径拆成边的思维题。 思路 一看到这题的路径，就想到了 Luogu P3177 树上染色 这题化路径为边的贡献，分别计算的思维。 那么对于此题，先来观察题目里式子的意思：对于树上的每个无序点对，求出树上每个点 到这些点对之间的最短路径的 距离之和。枚举点对对应的就是 阅读全文

摘要： 国际象棋：模板棋盘状压。 摆上马：需要点思维的棋盘状压，相比上一道题加了“蹩马脚”的设定。 Easy_version ：国际象棋 概述一下此类棋盘问题的思路： 用二进制数表示出棋盘上某一行的状态。 用位运算预处理出合法的单行状态，以及需要用到的一些东西。 用位运算判断前一行或者前几行能否转移过来。 阅读全文

摘要： 状压细节题。 阅读全文

摘要： 构造：结论题，gcy数竞大佬tql%%%orz。 结论 先放结论：如果 \(x \bmod 4=2\) ，那么 \(x\) 无法被表示为 \(a^2-b^2\) 的形式；除此之外的其他数都可以。 证明 对 \(a^2-b^2\) 因式分解，得 \(x=(a+b)(a-b)\) 。 当 \(x \bm 阅读全文

摘要： 能量消耗：一个前缀和优化 dp 的大典题，要是数据水一点 \(O(n^3)\) 都能硬草过去。 思路 显然，定义 \(dp[i]\) 为考虑前 \(i\) 个塔，并且将第 \(i\) 个塔开启，将前面的精灵全部收集的最小代价。 于是转移： \[dp[i]=min(dp[i],dp[j]+w(j,i) 阅读全文

摘要： 跑路：绝佳倍增好题，思路是化 \(2^k\) 为 \(1\) ，倍增起预处理作用。 最近不知道是撞了什么运，前一脚看的是绿题，写完之后交一发，发现直接被 lxl 升蓝了，血赚。 思路：Floyd 首先观察到每次走 \(2^k\) 的代价为 \(1\) ，我们可以预处理出每次走 \(2^i\) 能到哪 阅读全文

摘要： 思路不难想，细节比较多。 思路 观察到 \(n \le 19\) ，首先想到状压 dp 。 于是自然地定义 \(dp[j][i]\) 为：抵达点的状态为 \(i\) ，且此时在点 \(j\) 时，简单路径的条数。注意这里是简单路径的条数，而不是环的个数，因为环的个数要在 dp 过程中统计。这里的 d 阅读全文

摘要： 拓扑排序好题。 阅读全文

摘要： 绝世树形 dp 好题。一般看到有关树上“路径”的题，就要把路径拆成一个个独立的单边，对每个单边独立计算贡献。同时还有易错的树形背包上下界优化，用链构造卡掉。 阅读全文

摘要： 状态设计 基本上每一种 dp 都有一种标准的 dp 定义方式，树形 dp 也是如此： 定义 \(f[u]\) 表示以 \(u\) 为根节点的子树里最优的决策。 从分析子树入手，转移便是找到某一子树中，根节点与各子树、边权间的递推关系。 最优解常常是关于根节点的函数。 它的子结构是一颗子树。 实现方式 阅读全文

摘要： 二分答案有一个很显著的特征：一定存在一个临界值，单调性只是临界值的一种，而不是全部。 临界值，就是寻找第一个/最后一个满足要求的值，这又分别对应着两个完全不同的二分模板，这里做题时推荐使用“第一个满足要求的值”，即对应着 STL 中的 upper_bound ，手写板对应着 这篇文章 里讲的模板。 阅读全文

摘要： 依据值域的 \(O(n^2)\) 做法 这种做法只适用于这种值域小的题，下一种做法才是求等差数列的通解。 我们定义 \(f[i][j]\) 表示以 \(h_i\) 为最后一个数，公差为 \(j\) 的等差数列（长度 \(\ge 2\) ） 的个数。 接下来我们找每一个数前面的数，确定公差后转移即可。 阅读全文

摘要： 题目：绝世好题。 暴力 dp 显然 \(O(n^2)\) 转移即可。 单调队列优化 观察到只有某二进制位两个数都为 \(1\) 时才能转移，因此我们把每个二进制位开一个单调队列，然后对于一个数 \(a\) ，找到它是 \(1\) 的二进制位并选其单调队列的队头进行转移，在这之后把这个数加入符合要求的 阅读全文

摘要： 题目：编辑距离 。 思路 显然，定义 \(f[i][j]\) 表示字符串 \(a\) 中前 \(i\) 个字符到 字符串 \(b\) 中前 \(j\) 个字符的编辑距离。 那么对于 \(a_i=b_j\) 时，我们对当前位无需进行任何编辑操作，则 \(f[i][j]=f[i-1][j-1]\) 。 阅读全文

摘要： 朴素算法 不必多说，\(O(n^2)\) 的暴力 dp 转移。 优化算法 时间为 \(O(n \log n)\) ，本质是贪心，不是 dp 。 思路是维护一个单调栈（手写版），使这个栈单调不降。 当该元素 \(\ge\) 栈顶元素时，把这个元素压入栈中。 否则，在单调栈中找到第一个大于该元素的项，把 阅读全文

摘要： 二分最佳模板 阅读全文