确定是否可以使用特定操作从位串A到达位串B

Question

问题是，给定两个位串 A 和 B，使用以下操作确定是否可以从 A 到达 B：

选择两个索引i,j，使得两个索引处的值相同，并且i和j之间的1和0的数量分别大于区间外的1和0的数量。然后，翻转两个索引处的位。

操作示例： 0001010001

0001010001 之间的零个数：3 > 外部零个数 = 2

之间的个数：2 > 外面的个数 = 1

因此， 0101010101 是有效的更改。

我尝试通过跟踪每侧的 1 和 0 的数量来从右到左迭代，如果右侧的 1 和 0 的数量小于左侧，我执行一个操作来尝试移动所有1 在右侧（我试图将每个位串转换为其字典顺序的最小简化版本，然后比较以查看它们是否相同），但这会导致隐藏的测试用例失败。 （或者是我实现错误，不确定算法思想是否正确）。

不发布代码，因为它不相关。我只需要算法帮助，而不是编码帮助。

这是一个私人 codeforces 健身房问题，所以我无法发送链接。

Answer 1

这是一个很好的问题。你能检查一下我的Python代码是否通过了测试吗？如果确实如此，如果您愿意，我可以提供一些数学背景。

from itertools import accumulate, chain

def main():
    read_input_and_solve()


def read_input_and_solve():
    n = int(input())
    p = input()
    q = input()
    
    all_transfers_possible = solve(n, p, q)
    if all_transfers_possible:
        print('yes')
    else:
        print('no')


def solve(n, p, q):
    prefix_sum_players_stay_in_team_A = prefix_sum(n, lambda i: p[i] == 'A' and q[i] == 'A')
    prefix_sum_players_stay_in_team_B = prefix_sum(n, lambda i: p[i] == 'B' and q[i] == 'B')

    try:
        transfers_from_A_to_B = generate_transfers(n, lambda i: p[i] == 'A' and q[i] == 'B')
        transfers_from_B_to_A = generate_transfers(n, lambda i: p[i] == 'B' and q[i] == 'A')
        transfers = chain(transfers_from_A_to_B, transfers_from_B_to_A)
        check_transfers(prefix_sum_players_stay_in_team_A, prefix_sum_players_stay_in_team_B, transfers)
    except Exception:
        return False

    return True


def prefix_sum(n, condition):
    players_stay_in_team = (1 if condition(i) else 0 for i in range(n))
    return list(accumulate(players_stay_in_team))


def generate_transfers(n, transfer_indentifier):
    players_switch = [i for i in range(n) if transfer_indentifier(i)]
    if len(players_switch) % 2 != 0:
        raise Exception('not solvable')
    half = len(players_switch) // 2
    return zip(players_switch[:half], players_switch[half:])   


def check_transfers(prefix_sum_players_stay_in_team_A, prefix_sum_players_stay_in_team_B, transfers):
    for i, j in transfers:
        execute_vote(prefix_sum_players_stay_in_team_A, i, j)
        execute_vote(prefix_sum_players_stay_in_team_B, i, j)


def execute_vote(prefix_sum_players_stay_in_team, i, j):
    votes_no = prefix_sum_players_stay_in_team[-1] - prefix_sum_players_stay_in_team[j] + prefix_sum_players_stay_in_team[i]
    votes_yes = prefix_sum_players_stay_in_team[j] - prefix_sum_players_stay_in_team[i]
    if votes_yes <= votes_no:
        raise Exception(f'transfer rejected')    
   

if __name__ == '__main__': main()