2 条题解

  • 2
    @ 2024-10-22 19:48:08

    题意

    给你两串由 '0''1' 构成的字符串 ab,你可以对 a 串进行操作,在一次操作之中,你可以选择 01 串前缀中01数量相等的前缀,使其字母颠倒(0 变成 1 , 1 变成 0)。

    现在你可以进行任意次操作,问你能否让 ab 两个字符串相等。

    思路

    因为可以进行任意次操作,所以只要选择的前缀01数量相同无论如何都可以转回来,所以重点就在01的数量是否相同。

    所以可以在从前都后进行遍历的时候计算前缀中01的数量,当遍历时遇到:

    (1)a[i]==b[i]&&a[i+1]!=b[i+1] (2)a[i]!=b[i]&&a[i+1]==b[i+1]

    上述两种情况就代表此时字符串 1~i 的前缀必须要进行一次翻转,则此时判断 a 串 1~i 的前缀中01个数是否相同,若不相同则代表不能翻转,则中止遍历,输出 NO,若相同就代表此时可以翻转,继续向后遍历,直到遍历结束输出 YES 或在遇到上述输出 NO 的条件的情况下中止遍历输出 NO

    信息

    ID
    1026
    时间
    1000ms
    内存
    256MiB
    难度
    8
    标签
    递交数
    85
    已通过
    11
    上传者