刷题笔记合集🔗

出错的或电路

问题描述

小兰是一名电路工程师，她发现某一批次的或门电路不稳定，具体现象为计算两个二进制数的或操作时，第一个二进制数中某两个比特位会出现交换，交换的比特位置是随机的，但只交换这两个位，其他位不变。

很明显，这个交换可能会影响最终的或结果，也可能不会有影响。

为了评估影响和定位出错的根因，小兰需要研究在各种交换的可能下，最终的或结果发生改变的情况有多少种。

输入格式

第一行有一个正整数 ，其中 。

第二行有一个长为 的二进制数，表示与电路的第一个输入数，即会发生比特交换的输入数。

第三行有一个长为 的二进制数，表示与电路的第二个输入数。注意第二个输入数不会发生比特交换。

输出格式

输出只有一个整数，表示会影响或结果的交换方案个数。

样例输入

3
010
110

6
011011
110110

样例输出

1

4

数据范围

• 
• 输入的两个二进制数长度均为

题解

这道题目要求我们计算在第一个二进制数的两个位交换后，会改变或运算结果的交换方案数量。

首先需要理解，二进制的或运算有个特点：只要两个输入中的任意一位是1，结果就是1；只有当两个输入的对应位都是0时，结果才是0。

基于这个特性，可以分析什么情况下交换会影响结果：

1. 如果第二个数的某一位是1，那么无论第一个数对应位是什么，或运算结果都是1，所以交换不会影响这一位的结果。
2. 只有当第二个数的某一位是0时，交换才可能影响结果：
   • 如果第一个数对应位是0，交换后变为1会改变结果
   • 如果第一个数对应位是1，交换后变为0会改变结果

因此，我们只需要关注第二个数中为0的位置，并计算合法的交换方案。

具体算法步骤：

1. 统计第一个数中1和0的总数量
2. 统计第二个数为0的位中，第一个数对应位为0的数量(x)和为1的数量(y)
3. 计算可能改变结果的交换方案数：
   • 对于第二个数中值为0、第一个数中值为0的位，需要与第一个数中值为1的位交换才能改变结果，所以有x*a种可能（其中a是第一个数中1的总数）
   • 对于第二个数中值为0、第一个数中值为1的位，需要与第一个数中值为0的位交换才能改变结果，所以有y*b种可能（其中b是第一个数中0的总数）
   • 需要减去重复计算的情况：x*y

最终结果为：x * a + y * b - x * y

时间复杂度：O(N)，其中N是二进制数的长度，需要遍历一遍两个二进制数。 空间复杂度：O(1)，只需要几个变量来存储计数结果。

参考代码

• Python

import sys
input = lambda: sys.stdin.readline().strip()

# 读取输入
n = int(input())
bin1 = input()  # 第一个二进制数（可能发生交换）
bin2 =