Better late than never

在 520B Two Buttons 中，每次操作的代价都是 1，BFS 按层扩展就等于按距离扩展。如果一条边代价 2、另一条边代价 10，“经过的边更少”就不再等于“总代价更小”。 Codeforces 20C 把问题推进了一步：边权为正，既要算最短距离，还要输出一条真正达到该距离的路径。本文会把距离计算、贪心正确性与路径还原分开讲清楚。 1. 先读约束，再选择算法20C · Dijkstra? 官方题目 的难度为 1900，官方标签为 graphs 和 shortest paths，于 2026-09-08 核对。题目给出无向带权图：2≤n≤100000、0≤m≤100000、边权 1≤w≤1000000，允许自环和重边，需要输出顶点 1 到顶点 n 的任意一条最短路径；不可达时输出 -1。 约束信息 直接影响 十万个点、十万条边 O(n²) 的朴素选点不可接受 边权均为正 可以使用 Dijkstra 图较稀疏 邻接表比邻接矩阵更合适 要输出顶点序列 松弛时还要记录父节点 路径和可能超过 32 位 距离必须使用 long long 最坏情况下，一 ...

如果一道题没有给出顶点和边，能不能用图算法？可以：把“当前局面”当作顶点，把“一次合法操作”当作有向边，最少操作次数就变成了最短路。 这篇用一道题走两遍：先用 BFS 建立可靠的通用解法，再利用操作的特殊结构，把搜索压缩成逆向贪心。重点不是背两份代码，而是分清哪个结论来自图模型，哪个结论必须另行证明。 1. 先确定状态与边520B · Two Buttons 官方题目 的难度为 1400；官方标签包括 graphs、shortest paths、greedy、math、implementation、dfs and similar，于 2026-09-07 核对。下面是原创推导，不复述题目故事。 起点为正整数 n，目标为正整数 m。每步可以把当前数乘 2，或减 1；过程中不能变成 0 或负数。官方输入满足 1≤n,m≤10000 且二者不同；本文实现也自然支持相等时返回 0。 图中的概念 本题对应 顶点 x 当前显示的正整数 有向边 x → 2x；当 x>1 时还有 x → x-1 边的代价 一次操作，均为 1 目标 从 n 到 m 的最短路径长度 ...

读到“某种太阳能电池效率又提高了”，容易把进展想成找到了更会吸光的材料。但一个光生电子能不能最终流过外电路，还取决于晶体缺陷、相邻材料的能级，以及界面处是否发生了不希望出现的复合。 钙钛矿太阳能电池把这些问题集中在一起：组成可以调整，薄膜很有吸光潜力，但高效率、长期稳定与大面积制造必须同时推进。本文先解释材料和器件，再用一篇 2025 年原始论文观察界面化学怎样改变性能。 1. 先把“钙钛矿”与具体成分分开钙钛矿在这类研究中指一族具有相关晶体结构的材料，并不意味着太阳能电池里必须含有钙和钛。光伏中常讨论的是金属卤化物钙钛矿；例如 MAPbI₃ 中的 MA 指甲基铵，另外两个组成部分是铅和碘。美国能源部的材料入门 对光伏用卤化物与其他应用中的氧化物作了区分。 这个区别值得保留：文章标题里的结构名称，不足以告诉我们样品的全部化学组成。阅读论文时，应继续查配方、是否混合阳离子或卤素，以及研究的是哪一层材料。 本文关注金属卤化物光伏器件。不同配方的性能和降解路径不能默认完全相同。 2. 从吸光到输出电流，中间有好几道关钙钛矿薄膜在器件中承担吸光层的角色。吸收合适能量的光后产生可参与输运的载 ...

在 动态规划两题 中，我们保存的是“最多能得到多少”。如果目标改成“合法方案一共有多少种”，状态依然可以按长度排列，但合并候选的方式就从取最大值变成了求和。 Codeforces 474D 很适合把这一步与 前缀和 连起来：先算每种长度有多少方案，再快速回答一段长度范围内的方案总数。 1. 先把问题分成两层474D · Flowers 官方题目 的难度为 1700，官方标签为 dp，于 2026-09-07 核对。下面使用原创解释与自拟推演，不整段翻译题面。 把红花记为 R、白花记为 W。红花可以逐朵出现，白花按长度为 k 的块出现；相邻的白花块可以连在一起，因此连续白花段的长度可以是 k、2k、3k…。 每次查询给出 [a,b]，需要统计总长度在这个范围内的合法序列数量，结果对 1000000007 取模。t、k 和查询端点均不超过十万，其中 t 是查询数。 这里有两个任务： 层次 问题 工具 单点 长度恰好为 i 的方案有多少 计数 DP 区间 长度从 a 到 b 的方案加起来有多少 前缀和 如果每次查询都重新运行 DP，会重复计算相同长度。所有查询共享同一 ...

同一道题，让模型立即给出答案，或者允许它生成多个候选、运行检查、修正后再提交，得到的结果可能不同。这个差别把注意力从“模型有多大”扩展到另一个问题：处理这一次请求时，怎样花额外的计算预算？ 这篇文章解释推理时计算（test-time compute）的几种典型方式，并给出一个可以照着设计评测的例子。它是一篇研究方向入门，不是模型排行榜，也不把更长输出直接当作更强推理。 1. 先分清训练预算与推理预算 阶段 发生了什么 影响范围 预训练 从大量数据中学习语言与知识模式，更新参数 后续大量请求 后训练 用示范、偏好或奖励改进模型行为，更新参数 后续大量请求 推理时计算 对当前问题增加生成、搜索、验证或修订 当前请求及其候选结果 本文讨论的是固定权重下的推理策略。也有研究在测试阶段调整模型，这属于更广义的测试时适应，不能与这里的“多生成、多检查”直接画等号。 在 推理计算分配研究 中，Snell 等人讨论了验证器引导的搜索和响应分布的自适应改进。一个关键观察是：方法收益随题目难度变化，因此固定给所有题相同的额外预算未必划算。论文中的效率比较依赖具体模型、任务和计算口 ...

写动态规划时，最容易卡住的地方往往不是循环，而是这句话：dp[i] 究竟表示什么？如果状态只写成“到 i 的最优解”，那么“恰好到达”和“不超过 i”就可能混在一起，初始化也会跟着出错。 本文用两道题练习两个不同的状态轴：一题按已使用的长度递推，另一题按数值大小递推。建议先独立画出状态表，再看代码。 1. 两道题，两个关键问题 题目 官方难度 官方标签 本文训练重点 189A · Cut Ribbon 1300 brute force、dp 恰好填满与不可达状态 455A · Boredom 1500 dp 按值聚合与相邻冲突 名称、难度和标签于 2026-09-05 通过 Codeforces 官方 API 核对。下文是原创建模与解法说明，不是题面翻译；所有推演表均使用自拟例子。 读过 贪心三题 后，可以把这篇当作下一步：当一个局部选择无法保证未来仍然最优时，保留不同状态的最优结果，之后再比较。 2. Cut Ribbon：为什么不能一直选最短的一段给定总长度 n，每段只能取 a、b、c 三种正整数长度，目标是在不剩余材料的前提下，让段数最多。题目保证有解，四个 ...

Q-learning 先估计每个动作的价值，再选价值最大的动作；策略梯度则直接调整策略参数，让带来较高回报的动作以后更可能发生，让结果较差的动作概率下降。 这条路线特别适合随机策略和连续动作，但代价是梯度估计噪声很大、数据通常只能使用一次，而且更新过猛时容易破坏已有策略。本文从最小的随机策略开始，逐步解释 REINFORCE、基线、优势函数与 Actor-Critic 的关系。 1. 从动作价值转向参数化策略设策略为 πθ(a|s)，参数 θ 可以是一个表格，也可以是神经网络权重。它接收状态，并输出动作的概率分布。我们的目标是最大化策略产生轨迹的期望回报： 1J(θ) = Eτ~πθ [R(τ)] 一条轨迹包含状态、动作和奖励。策略改变动作分布，动作又改变之后访问到的状态，因此无法像监督学习那样直接为每个动作准备“正确标签”。 策略梯度定理提供了一个可以从采样轨迹估计的方向： 1∇θ J(θ) = E[Σt ∇θ log πθ(at|st) × A(st, at)] 可以把它读成：动作的对数概率梯度，乘以该动作比基准好多少。 2. 为什么出现 log π概率分布的期望中含有 π ...

旋律可以哼出来，和声能制造离开与回归，节奏则决定声音怎样占据时间。很多人看到 3/4、6/8 就开始数分数，却忘了拍号首先描述的是重音层级：哪些脉搏属于同一组，哪一拍像落脚，哪一拍推动下一步。 本文不要求读谱，从拍手、走路和呼吸的经验开始，区分脉搏、速度、节奏与节拍，再进入弱起、切分、复拍子和弹性速度。 1. 四个容易混用的概念 概念 它回答的问题 聆听动作 脉搏 Pulse 哪些时刻可以稳定地拍手？ 找到等距的时间点 速度 Tempo 脉搏走得多快？ 比较单位时间内拍点数量 节奏 Rhythm 声音以怎样的长短与停顿出现？ 模仿具体音型 节拍 Meter 脉搏怎样形成强弱层级和分组？ 找到周期性“第一拍” 同一速度下可以写出完全不同的节奏；同一段节奏也可以用不同速度演奏。节拍则不是节拍器的点击本身，而是我们在连续脉搏中感到的组织方式。 flowchart LR A[等距脉搏] --> B[形成强弱层级] B --> C[二拍、三拍或四拍分组] C --> D[旋律在强弱位置间移动] D --> ...

普通二分查找在有序数组里找位置；二分答案则不直接构造最优方案，而是反复询问：“答案至少达到 x，能做到吗？”只要可行性随 x 单调变化，就能在答案空间里找到最后一个可行值。 本文选择三道 Codeforces 题，分别练习中位数提升、共享资源分配和配方生产。它们的题面不同，但代码骨架几乎一致：定义 can(x)、找到可靠上界、维护一个可行点和一个不可行点。 1. 二分答案的核心不是 while 循环假设要最大化一个整数答案，并且： 1can(x) = true 表示答案至少可以达到 x 如果 can(x) 为真能推出所有更小值也为真，那么答案轴具有如下结构： 123true true true ... true | false false ... false ↑ 最大可行值 flowchart LR A[猜测答案 x] --> B[计算达到 x 的最低成本] B --> C{成本是否不超过预算} C -->|是| D[x 可行，向右找] ...

智能体总选当前回报最高的动作，可能永远错过真正更好的选择；如果一直尝试未知动作，又会浪费已经学到的信息。探索与利用的矛盾，就是在“获取信息”和“使用信息”之间分配有限交互次数。 多臂老虎机去掉了完整强化学习中的状态转移和延迟回报，保留这组矛盾的最小形式。它很适合用来理解探索策略，因为每种方法为什么有效、又会在哪里失效，都能被直接观察。 1. 多臂老虎机模型设有 k 个动作。每次选择动作 a，环境从该动作未知的奖励分布中给出奖励。动作的真实期望奖励记为 q*(a)，智能体只能维护估计值 Q_t(a)。 若动作 a 已被选择 N_t(a) 次，新奖励为 R_t，样本均值可以增量更新： 1Q_{t+1}(a) = Q_t(a) + 1 / N_t(a) × [R_t - Q_t(a)] 括号中的差叫估计误差。这个公式不必保存全部历史奖励，每一步只需维护次数和当前均值。 除了平均奖励，还可以考察累积遗憾：每一步没有选择真实最优动作时，损失了多少期望奖励。 1Regret(T) = Σ(q*(a*) - q*(A_t)), t = 1 ... T 真实任务里通常不知 ...