1 条题解

  • 0
    @ 2024-7-14 3:49:40

    题目大意

    每次可以选择任意区间 [L,R][L,R],如果 hLhRh_L \sim h_R 有超过一半是相同的数字,那么整个区间都会被同化为这个数字。这样的操作可以进行无数次,问能不能将整个序列都同化为同一个数字,如果可以,从小到大列出所有可能。

    解题思路

    手动列举一些情况会发现,只要想办法让相邻的两个数相等,那么一定能通过若干次操作将所有奶牛同化。(因为可以先选三头牛,其中两头数字相等,那三头牛都变成相同数字;接着在这三头牛的基础上再加入一头相邻的牛,继续重复操作即可)

    那问题就变成了如何构造出连续且相等的两个数字。由于每次操作,相同的数字必须超过一半才能同化奶牛(刚好一半是不行的),因此对长度为 22 的区间进行操作是无效的,考虑对长度为 33 的区间进行操作,只要区间内有两个相同的数字,那区间就能同化为 33 个连续且相同的数,这样就成功构造出来了。

    因此,可以三个数一组进行枚举,只要发现三个数中出现任意两个相等的数字,那么这个数字一定是答案之一。

    最后对所有答案排序再输出即可。

    • 1

    信息

    ID
    10
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    (无)
    递交数
    1
    已通过
    1
    上传者