aurora5090

摘要： [CERC2014] The Imp 恶魔有 \(n\) 个物品，每个物品价值为 \(v_i\)，购买需要 \(c_i\) 元。 恶魔至多可以使用 \(k\) 次魔法，你和恶魔轮流操作： 你购买一个物品 恶魔要么释放一次魔法销毁这个物品（继续游戏），要么让你拿走这个物品（然后强制结束游戏） 你和恶魔 阅读全文

摘要： 退役了，平时没事干就做点题吧 233 [NWRRC 2025] Keys and Grates 在数轴上，有 \(n\) 个不同的障碍，每个障碍唯一对应了一把钥匙，散落在不同位置。 你要从 \(S\) 走到 \(T\)，求最短路径，或者报告无解。 \(n \le 2 \cdot 10^5\) 手玩一 阅读全文

摘要： 学长 rinne 也从 ICPC 退役了，根据惯例，他也要写一篇小作文（点头） 2019 年，吴作同在集训队论文《公园》命题报告中正式引入了这个结构。在这种特殊图上，存在一组收缩操作，存在一类 DP 方法。具体的正确性证明可以在集训队论文里找到，这里暂略。我们非常 naïve 地介绍一下这个特殊图， 阅读全文

摘要： 学长 Mikakoko 在 ICPC 比赛中退役了，根据惯例，他要写一篇小作文（手动滑稽）。 最短路相关的问题太多啦，这篇小作文只能简单介绍其中的一部分。 在连通的无向正权图上，给定源点 \(S\)，我们能计算得到所有 \(\text{dis}(S, x)\)。 如果一条边 \((u \xright 阅读全文

摘要： 今天退役了，根据惯例要写一篇小作文，如果你能能读完这篇小作文，我会很高兴。 这篇小作文会介绍一下我在打 ICPC 期间学过的 LCS 相关的算法，希望能提高大家的理解。 \(\text{LCS}\) 问题：字符集为 \(\Sigma\)，你需要求两个字符串 \(A, B\) 的最长公共子序列。 经典 阅读全文

摘要： 建立坐标系，\(x\) 作为输入，\(y\) 作为输出 假如这种系统形如：一段水平线 + 一段 \(k = 1\) 的直线 + 一段水平线 那么这种结构在级联以后是可以快速合并的（E.g. 一个连续的序列，将前一个的输出作为后一个的输入） 具体来说，这个系统可以直接用两个拐点的信息来表示 struc 阅读全文

摘要： 快速幂 一个简单的技术，可以认为是一种小 trick 。 不叫 ksm，可以叫 fastPow，或者叫 binaryPow。 后者的名字为我们解释了这个 trick 的本质的一部分。 这个算法 / 技术 / trick 主要利用了二进制分解。 二进制 可以用二进制表达任意一个十进制整数 \(1_{1 阅读全文

摘要： Tarjan 求强联通分量 SCC 强联通分量（Strongly Connected Component，SCC）是一个 有向图 中的点集 这个点集内的任意两个点，都可以相互抵达 比如说，一个环，它是一个 SCC 比如说，一条链，虽然链头可以抵达任何点，但是其他点都无法抵达链头 在链的情况下，每个点 阅读全文