1 条题解

  • 0
    @ 2026-9-29 20:33:54

    对于果农 22,最优的操作是在剩余字符串还有 00 的时候,选 0101,否则选 1111。所以当两个果农刚好能一人选一次到游戏结束时,子串中一定满足 num0=3⋅num1num_0 = 3 \cdot num_1。

    • 当 num0≥3⋅num1+2num_0 \ge 3 \cdot num_1 + 2 时,果农 11 能在两人一人选一次后多选一次,玩家一获胜。
    • 当 num0<3⋅num1+2num_0 < 3 \cdot num_1 + 2 时,
      • 当 num0=3⋅num1−1num_0 = 3 \cdot num_1 - 1 时,在倒数第二轮选完之后,刚好只剩下两个 00、一个 11。果农 11 获胜。
      • 剩余其他情况下,带倒数第二轮选完之后会剩下两个 00 和若干个 11,果农 22 获胜。

    果农 11 获胜的数量就是所有满足的 num0−3⋅num1≥2num_0 - 3 \cdot num_1 \ge 2 或 num0−3⋅num1=−1num_0 - 3 \cdot num_1 = -1 的子串数量。

    设 cnticnt_i 表示前 ii 位的 num0−3⋅num1num_0 - 3 \cdot num_1 的数量,所有以第 ii 位结尾的子串中,果农 11 获胜的数量为满足 1≤j<i1 \le j < i 且 cntj≤cnti−2cnt_j \le cnt_i - 2 或 cntj=cnti+1cnt_j = cnt_i + 1 的 jj 的数量(满足 cnti−cntj≥2cnt_i - cnt_j \ge 2 或 cnti−cntj=−1cnt_i - cnt_j = -1,其中 cnti−cntjcnt_i - cnt_j 表示的是 (j,i](j, i] 的子串中的 num0−3⋅num1num_0 - 3 \cdot num_1 数量。

    最后只需要统计出满足 1≤j<i1 \le j < i 且 cntj≤cnti−2cnt_j \le cnt_i - 2 或 cntj=cnti+1cnt_j = cnt_i + 1 的 jj 的数量即可。

    时间复杂度: O(n)O(n)。

    • 1

    信息

    ID
    8292
    时间
    2000ms
    内存
    512MiB
    难度
    10
    标签
    递交数
    9
    已通过
    3
    上传者