刷题笔记合集🔗

问题描述

某生产门电路的厂商发现某一批次的或门电路不稳定,具体现象为计算两个二进制数的或操作时,第一个二进制数中某两个比特位会出现交换,交换的比特位置是随机的,但只交换这两个位,其他位不变。

这个交换可能会影响最终的或结果,也可能不会有影响。为了评估影响和定位出错的根因,工程师需要研究在各种交换的可能下,最终的或结果发生改变的情况有多少种。

输入格式

第一行输入一个正整数N(1≤N≤1000000)。

第二行输入一个长度为N的二进制数,表示会发生比特交换的第一个输入数。

第三行输入一个长度为N的二进制数,表示不会发生比特交换的第二个输入数。

输出格式

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

样例1

输入:

3
010
110

输出:

1

说明:

• 原本010和110的或结果是110
• 第一个输入数可能发生三种交换:
  1. 交换第1、2位:100,结果110,不变
  2. 交换第1、3位:010,结果110,不变
  3. 交换第2、3位:001,结果111,改变
• 只有一种交换会改变计算结果

样例2

输入:

6
011011
110110

输出:

4

说明:

• 原本011011和110110的或结果是111111
• 以下交换会影响结果:
  1. 交换第1、3位:110011,结果110111
  2. 交换第1、6位:111010,结果111110
  3. 交换第3、4位:010111,结果110111
  4. 交换第4、6位:011110,结果111100
• 其他交换不会影响结果,共4种

题解

本题可以使用统计法解决:

1. 对于bin2中值为1的位,不管bin1对应位如何交换,结果都为1,可以忽略
2. 只需关注bin2中值为0的位:
   • 若bin1对应位为0,需要和bin1中值为1的位交换才能改变结果
   • 若bin1对应位为1,需要和bin1中值为0的位交换才能改变结果
3. 统计:
   • x:bin2为0且bin1为0的位数
   • y:bin2为0且bin1为1的位数
   • a:bin1中1的总数
   • b:bin1中0的总数
4. 结果为:xa + yb - x*y

时间复杂度:O(n),其中n为二进制串长度。

参考代码

# 读取输入
n = int(input())
bin1 = input()
bin2 = input()

def getResult(n, bin1, bin2):
    # 统计各种情况的数量
    x = 0  # bin2为0且bin1为0的位数
    y = 0  # bin2为0且bin1为1的位数
    a = 0  # bin1中1的总数
    b = 0  # bin1中0的总数
    
    for i in range(n):
        if bin1[i] == '0':
            b += 1
            if b