1 条题解

  • 0
    @ 2026-11-15 15:17:20

    题目分析

    考点:贪心、分类讨论。

    要求构造出满足「每一位数字出现次数固定」「相邻两位不同」「无前导零」的最小正整数。

    爆搜部分分:直接搜索全排列即可。

    特殊性质(只有两个数字非零):设这两个数字为 xx 和 yy。此时最终的美丽数只可能是 xyxy⋯xyxy\cdots 或 yxyx⋯yxyx\cdots 两种形式之一,分类讨论一下即可。

    特殊性质(三个数字非零):设这三个数字为 x,y,zx,y,z。贪心策略是从数位高位到低位依次放置:优先放当前最小的数字,如果与上一位相同则放下一个。但需要判断「剩下的数字还能不能构成美丽数」。

    能构成的充要条件是:设剩余数字中出现次数最多的那个数字出现 mxmx 次、其余数字总数为 restrest,则必须满足 mx≤rest+1mx \le rest + 1。只有这样才能保证相同数字不相邻。

    关于不能有前导零:可以假设前一位放置的是数字 00,这样处理自然就排除了前导零。

    正解:沿用上面的思路,从高位到低位依次尝试放置 0∼90 \sim 9,判断「放在这一位之后,剩余数字还能否构成美丽数」——同样使用上面那条 mx≤rest+1mx \le rest + 1 的充要条件。由于数字种类只有 10 种,暴力判断的复杂度很小。

    若所有数字都无法放置(即任何情况下都无法避免相邻重复),则输出 −1-1。

    • 1

    信息

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