CSP2025倒计时打卡

qq群号:868765105
HSqq号:774269903
V:hs774269903
hs手机号:17698083099

https://www.luogu.com.cn/article/dpcjimcj

Oh~ That's good~

新手噩梦

所以说hs是谁

诗人我吃

11111

每天上线先贡献1000次访问

DFS或者Dijkstra，上下左右任意走可以看成环，dp做不到

既然超过 \(S \cdot T\) 的空地不会改变青蛙的“记忆模式”，我们就可以把任意长的空地**缩短成 \(S \cdot T\)**，而不影响最终答案。
例如，若石子在 100 和 10000 处，中间 9900 格全是空的，我们只需保留 90 格（因 \(S,T \leq 10\)，取 \(10 \times 9 = 90\)）。压缩后，DP 状态空间大小从 \(L\)（可能 10⁹）降到约 \(100 \times 90 = 9000\)，计算可行。**这个 \(S \cdot T\) 就是保证状态“线性无关组已完备”的临界长度**。

假设两块石子之间全是空地，距离为 \(d\)。青蛙能跳 \(S, S+1, \dots, T\) 格。数学上可以证明：只要 \(d > S \cdot T\)，青蛙就能通过不同跳法，**落到这段空地之后的任意“相对位置”**（比如刚好对齐某个余数）。
这是因为步长集合能“生成”所有足够大的数（因 \(\gcd=1\)），而 \(S \cdot T\) 是最坏情况下需要的最小长度（来自 Frobenius 问题）。此时，状态向量 \(\mathbf{v}_x\) 已经遍历了所有可能的组合，**新增的空地不会带来新信息**——就像背完乘法表后，再背也是重复。

青蛙跳到位置 \(x\) 时，最少踩多少石子，只和它**前 \(T\) 步**的情况有关（因为最多跳 \(T\) 格）。我们可以把这 \(T\) 个值写成一个“状态向量”：
\[
\mathbf{v}_x = \begin{bmatrix} f(x-T+1) \\ f(x-T+2) \\ \vdots \\ f(x) \end{bmatrix}
\]
这个向量就像青蛙的“记忆”，长度固定为 \(T\)。所以，不管桥多长，所有可能的“记忆”最多只有 \(T\) 个独立方向——这叫**状态空间维度不超过 \(T\)**。一旦走过一段很长的空地，这些“记忆”就会开始重复。

以下内容是根据陈老师讲的后增加的自我总结的内容

回复 @hsl_beat :
[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [(bg

水题

双倍经验：
http://218.28.19.228:8081/cogs/problem/problem.php?pid=vNxXmkqqa
1440. [NOIP 2013]积木大赛

回复 @ムラサメ :
文明 @回归运动