1 条题解

  • 0
    @ 2026-11-15 14:07:01

    题目分析

    60 pts

    爆搜

    100 pts

    先来考虑固定 kk 时怎么做。设 bi=∑j=1iajb_i=\sum_{j=1}^i a_j, 发现

    ∀1≤i≤n,k∣ai\forall 1 \leq i \leq n, k | a_i

    可以转化为

    ∀1≤i≤n,k∣bi\forall 1 \leq i \leq n, k | b_i

    同时可以发现:

    1. 将 aia_i 取出 1 并放入 ai+1a_{i+1} 这个操作等价于 bi←bi−1b_i \leftarrow b_i-1 。
    2. 将 ai+1a_{i+1} 取出 1 放入 aia_i 等价于 bi←bi+1b_i \leftarrow b_i+1 。

    那么当固定 kk 时, 答案:

    $$a n s=\sum_{i=1}^n \min \left(b_i \bmod k, k-b_i \bmod k\right)$$

    因此,我们只需 O(bn)O(\sqrt{b_n}) 地枚举 kk,取 min⁡\min 即可

    • 1

    信息

    ID
    84
    时间
    1000ms
    内存
    256MiB
    难度
    4
    标签
    递交数
    1
    已通过
    1
    上传者