时间不会倒流，时间轴上靠后发生的不会影响前面的事，具有无后效性，因此很多时候结合时间来设状态，并用刷表法进行转移，是一种很好的做法。 例题 CF1840F Railguns 题解博客 这题将某人在第 $k$ 秒能否 停留在点 $(i,j)$ 上设为状态 dp[i][j][k] 进行转移，一个人在某个时间要么停留，要么往右/往下走，于是可以列出更新公式（转移方程）。 P2583 地铁...

一些情况下，图不是事先给定，从输入中直接给出的，而是根据实际情况在程序中动态生成的，称为“隐式图”。 路径寻找问题主要是求从某个初状态到某个终状态的最优路径（关键是存在状态间的相互转移，所以可以把状态看作是图上的节点），一般可以转化为隐式图，然后利用图的遍历或者求图的最短路来求解。 例题 隐式图中最短路 CF1846G（把当前的患病状态作为图上的节点，结合每种药的药效用位运算来连边）...

这是一篇关于区间问题的算法学习文章。文章介绍了五类最常见的区间问题，并提供了相应的解决思路。 简介 区间问题大多都是用贪心来做的。 一般都是先按照区间排序，可能按照左端点或右端点从大到小或从小到大排序，然后使用贪心。 根据问题的不同，具体贪心的思路也各不相同。 这篇文章汇总了最常见的5类区间问题，并直接给出思路方便理解和记忆。 区间合并问题 选择不相交区间问题 区间...

这篇博客主要讲述了一个算法问题，题目是给定 $n$ 条线段，每对线段由两个相交的线段组成。要求删除最少的线段，使得剩余的线段可以分成若干对，且每对线段互不相交。文章通过贪心算法解决这个问题，具体实现代码也给出了。 题目大意 有 $n$ 条线段，一对线段由两个相交线段组成。 称某 $k$ 条线段为漂亮的线段组，如果 $k$ 条线段满足: $k$ 是偶数 可以分成 $k/2$ 对线...

并查集是一种常用的数据结构，可以高效地处理动态连通性问题。在例题中，通过拓展并查集的应用，我们可以解决一些特殊的问题，如带权并查集和种类并查集。 P1196 [NOI2002] 银河英雄传说 题目链接 思路很简单，用并查集维护连通性的同时维护每个舰队到列首的距离即可。 由于并查集的修改操作只对集合的最早祖先进行修改（维护集合中元素总数可以完成这项操作），我们在对非最早祖先元素操作时，需...

Codeforces Round 882 (Div. 2) A 题目大意 一段数列的总贡献是所有相邻两项差的绝对值的总和。现有一段长度为 $n$ 的数列，可以把它分为 $k$ 段，求这k段的贡献之和的最小值。 思路 将一段数列分成两段，本质上是将其中一个相邻两项的贡献不计入其中。贪心，计算出所有相邻两项差的绝对值，排序后不计入前 $k$ 大的值即可。 代码 int n, k, a[1010...

这是一个关于质数判断和质因数分解的算法示例。其中使用了 Miller Rabin 算法进行质数判断，时间复杂度为 $O(k*log^3n)$，以及 Pollard’s Rho 算法进行质因数分解，时间复杂度为 $O(n^{1/4})$。 质数判断：Miller Rabin 时间复杂度为 $O(k \log^3n)$。 ll qmul(ll a,ll b,ll mod)//快速乘 { ...

Educational Codeforces Round 151 [Rated for Div. 2] A 题目大意 输入 $n,k,x$，有 $1$ 到 $k$ 中除了 $x$ 的所有数，每个数可以取任意次，任意给出一种取法，让取出来的所有的数和为 $n$。 思路 如果 $k=1$，则 $x=1$，显然不存在。 如果 $k>1$ 且 $x \neq 1$，则用 $1$ 可以得到 $...

这篇博客介绍了使用动态规划算法解决一个机器人在网格中避开激光炮到达终点的最短路径问题。 题意 Tema在 $n×m$ 的网格内要从 $(0,0)$ 走到 $(n,m)$。第0秒Tema位于 $(0,0)$。 假设第 $t$ 秒Tema位于 $(i,j)$，则第 $t+1$秒Tema可以在 $(i,j)$， $(i+1,j)$ 或 $(i,j+1)$. 机器人会发射 $r$ 次激光炮阻挠他的...

该博客的主要内容是关于解决一个图论问题，使用Dijkstra算法计算出聚会的最大总时间，并给出相应的聚会方案。 题目大意 Tenzing有 $n$ 个朋友，编号为 $1$ 至 $n$ ，每次举办聚会可以邀请其中的一些朋友参加，且朋友 $1$ 必须参加，朋友 $n$ 必须不参加。另有 $m$ 条限制，每条限制包含 $u,v,w$ ，表示朋友 $u$ 和朋友 $v$ 中只有一个在聚会中的总时间...