1 条题解

  • 0
    @ 2026-11-15 13:29:03

    题目分析

    30 分

    暴力搜索划分方案即可。

    60 分

    写一个简单 dp 就行,设 dpi,jdp_{i,j} 表示划分到了 ii,当前 gcd⁡=j\gcd=j 是否可行,转移是简单的,时间复杂度 O(n3V)\mathcal{O}(n^3V),其中 VV 是值域。

    80 分

    手玩可以发现答案一定是 n2\frac{n}{2}。

    正解

    注意到一个关键性质:gcd⁡(a+b,c)≥gcd⁡(a,b,c)\gcd(a+b,c)\ge \gcd(a,b,c)。

    证明是容易的,设 d=gcd⁡(a,b,c)d=\gcd(a,b,c),那么 d∣(a+b)d|(a+b),于是 gcd⁡(a+b,c)≥d\gcd(a+b,c)\ge d 肯定成立。

    这个性质说明最优划分一定只会划分为两段,否则将相邻的两段合并起来一定更优。

    于是滚一个前缀和,暴力枚举分割点即可,时间复杂度 O(nlog⁡V)\mathcal{O}(n\log V)。

    • 1

    信息

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