每日练习与编程练习

强候选人的思路会先把任务拆成“数值下溢”和“模型本身偏好近邻”两类，不能把所有远距离低权重都当 bug。对每个 query/head，softmax 实际计算的是 `exp(z_j - M)`，其中 `M=max_j z_j`。若某个 block 的最大 logit `a_b=max_{j in block} z_j` 满足 `a_b - M < τ_dtype`，则该 block 内 token 在当前 kernel/dtype 下可能全部被 flush 为 0；`τ_dtype` 需要按实际 kernel 标定，例如 fp16、bf16、fp32 exp、是否 flush-to-zero 都不同。 在线检测可以嵌入 FlashAttention 的 tile 计算。每个 key block 维护两个元信息：`a_b=max z_j` 和 `L_b=logsumexp_{j in block}(z_j)`，全局维护 `M=max_b a_b` 和 `L=logsumexp_b L_b`。不保存完整 `QK^T`，只保存每个 query/head 对 key-block 的少量标量。风险分数可定义为：`R = sum_{b: a_b-M<τ+margin} exp(L_b-L)`，表示理论高精度下本应来自被下溢 block 的注意力质量。若 `R > ε`，或被检索器/引用定位标记为关键证据的 block 被判定下溢，则触发慢路径。 缓解策略分三级。第一层是低成本数值修复：ALiBi bias、logit、block logsumexp 全部用 fp32 计算，禁止把概率中间结果落 fp16；对高风险 head 使用更保守的 softmax kernel。第二层是精确慢路径：对触发的 query/head 做分块 log-domain attention。先在每个 block 内用局部最大值算 block 内归一化输出 `o_b` 和 `L_b`，再用 `w_b=exp(L_b-L)` 聚合 `o=sum_b w_b o_b`。这样避免远距离 block 内所有 token 因相对全局最大值过小而被直接清零。可以两遍扫描 KV，避免存储所有 token 级注意力。第三层是语义层兜底：若高精度下远处质量仍接近 0，说明 ALiBi 偏置本身压制远证据，可使用距离偏置 cap、长距离 slope annealing、摘要/landmark memory、query-aware retrieval 近端重排等方法，但这些会改变模型行为，需要离线评估。 复杂度上，正常路径仍是 FlashAttention 的 `O(HLd)` 解码计算，额外只做 block 级 max/logsumexp 归约，元信息为 `O(H * L/B)` 标量，通常低于 3% 显存；慢路径只对少量高风险 query/head 二次扫描，最坏 `O(HLd)` 额外，但线上要限流，例如每步最多修复 top-k head 或 top-r 风险 block，保证 P99 开销。工程上还要处理 causal mask、全 mask 行、NaN/Inf logit、KV 量化 scale、不同 GPU 的 flush-to-zero 行为、多 query attention head 共享 KV、prefill 与 decode 两种路径一致性。 验证方案包括：构造远距离 needle-in-haystack、长文引用、多跳检索样例；用 fp64 或高精度 log-domain attention 作为 golden，对比 block mass loss、输出 hidden 差异、答案召回率和延迟；线上灰度监控 `R` 分布、触发率、P99 延迟、显存、远证据命中率，并设置回滚开关。关键取舍是：尽量用检测驱动的局部慢路径修复数值任务，不把模型设计缺陷伪装成数值优化。

参考解法：枚举最终要复制的“模板值” `x`。

如果先把初始的 `1` 增加到 `x`，需要 `x - 1` 次操作。之后每复制一次 `x`，数组总和增加 `x`。为了让总和至少为 `k`，最终至少需要 `ceil(k / x)` 个值为 `x` 的元素，因此复制次数是：

`ceil(k / x) - 1`

总操作次数为：

`(x - 1) + (ceil(k / x) - 1)`

等价写法：

`(x - 1) + (k - 1) // x`

由于值 `x` 和元素个数本质上形成一个乘积，最优值一定出现在 `sqrt(k)` 附近，因此枚举到 `sqrt(k) + 1` 即可。

python
from math import isqrt


class Solution:
    def minOperations(self, k: int) -> int:
        # 边界：初始 nums = [1]，和已经 >= 1
        if k == 1:
            return 0

        ans = k - 1  # 只执行加一操作，把 1 加到 k

        # 枚举最终被复制的模板值 x。
        # 由于 x 和最终元素个数可以互换理解，最优解只需要检查 sqrt(k) 附近及之前。
        for x in range(1, isqrt(k) + 2):
            # 先将 1 增加到 x，需要 x - 1 次
            increase_ops = x - 1

            # 当前已有一个 x，还需要复制若干个 x
            # 需要的最终元素个数为 ceil(k / x)
            # 复制次数 = ceil(k / x) - 1 = (k - 1) // x
            copy_ops = (k - 1) // x

            ans = min(ans, increase_ops + copy_ops)

        return ans


if __name__ == "__main__":
    sol = Solution()

    assert sol.minOperations(11) == 5
    assert sol.minOperations(1) == 0
    assert sol.minOperations(2) == 1
    assert sol.minOperations(5) == 3

    print("OK")