題目描述與示例

題目描述

某生產門電路的廠商發現某一批次的或門電路不穩定，具體現象為計算兩個二進制數的或操作時，第一個二進制數中某兩個比特位會出現交換，交換的比特位置是隨機的，但只交換這兩個位，其他位不變。

很明顯，這個交換可能會影響最終的或結果，也可能不會有影響。

為了評估影響和定位出錯的根因，工程師需要研究在各種交換的可能下，最終的或結果發生改變的情況有多少種。

輸入描述

第一行有一個正整數 N；其中 1 ≤ N ≤ 1000000。

第二行有一個長為 N 的二進制數，表示與電路的第一個輸入數，即會發生比特交換的輸入數。

第三行有一個長為 N 的二進制數，表示與電路的第二個輸入數。注意第二個輸入數不會發生比特交換。

輸出描述

輸出只有一個整數，表示會影響或結果的交換方案個數。

示例一

輸入

3
010
110

輸出

1

說明

原本 010 和 110 的或結果是 110，但第一個輸入數可能會發生如下三種交換：

1. 交換第 1 個比特和第 2 個比特，第一個輸入數變為 100，計算結果為 110，計算結果不變
2. 交換第 1 個比特和第 3 個比特，第一個輸入數變為 010，計算結果為 110，計算結果不變
3. 交換第 2 個比特和第 3 個比特，第一個輸入數變為 001，計算結果為 111，計算結果改變

故只有一種交換會改變計算結果。

示例二

輸入

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，計算結果變為 111110

其他的交換都不會影響計算結果，故輸出 4。

解題思路

第一個二進制數我們記為num1，第二個二進制數我們記為num2，或運算的結果記為num_or。對num1所選取的兩個位置記為i和j。

如果num1[i]和num1[j]交換之后或運算的結果和之前的不一致，說明交換的兩個位置必定滿足以下條件：

1. num1[i] != num1[j]，即交換的兩個數必須是一個0一個1，不能均為0或者均為1。因為如果num1[i] == num1[j]，說明交換前后的num1是一致的，與num2進行位運算得到的結果的num_or自然也是一致的。
2. num2[i]和num2[j]不能均為1，即num2的對應位置，至少有存在1個0。因為如果存在num2[i] == num2[j] == 1，那么無論num1[i]和num1[j]是什么內容，或運算的結果一定存在num_or[i] == num_or[j] == 1，不會因為num1[i]和num1[j]的交換而改變。

簡單來說：

1. num1的兩個位置必須是一個0和一個1。
2. num2的兩個位置必須至少有一個0。

因此，如果num_or在交換前后出現改變，那么只可能是以下三種情況。

num1的情況	num2的情況	num_or交換前	num_or交換后
num1[i] = 1``num1[j] = 0	num2[i] = 0``num2[j] = 0	num1[i] = 1``num1[j] = 0	num1[i] = 0``num1[j] = 1
num1[i] = 1``num1[j] = 0	num2[i] = 1``num2[j] = 0	num1[i] = 1``num1[j] = 0	num1[i] = 1``num1[j] = 1
num1[i] = 1``num1[j] = 0	num2[i] = 0``num2[j] = 1	num1[i] = 1``num1[j] = 1	num1[i] = 0``num1[j] = 1

由于i和j兩者的地位是等價的，因此我們只需要求出以下四種情況下的索引i的個數

1. num1[i] == 1，num2[i] == 1的i的個數，記為cnt11。
2. num1[i] == 0，num2[i] == 0的i的個數，記為cnt00。
3. num1[i] == 1，num2[i] == 0的i的個數，記為cnt10。
4. num1[i] == 0，num2[i] == 1的i的個數，記為cnt01。

上述表格中的三種情況的個數，根據乘法原理，分別對應

• cnt10 * cnt00
• cnt11 * cnt00
• cnt10 * cnt01

再將上述三者的結果相加，即為答案。

代碼

Python

# 題目：2023B-出錯的或電路
# 分值：200
# 作者：閉著眼睛學數理化
# 算法：數學/乘法原理
# 代碼看不懂的地方，請直接在群上提問n = int(input())
num1 = input()
num2 = input()# 初始化四個變量，分別統計四種情況
cnt11, cnt00, cnt10, cnt01 = 0, 0, 0, 0
for i in range(n):# 分別根據num1[i]和num2[i]的情況# 統計對應變量的個數if num1[i] == "1" and num2[i] == "1":cnt11 += 1elif num1[i] == "0" and num2[i] == "0":cnt00 += 1elif num1[i] == "1" and num2[i] == "0":cnt10 += 1elif num1[i] == "0" and num2[i] == "1":cnt01 += 1# 根據乘法原理，進行計算
ans = cnt10 * cnt00 + cnt11 * cnt00 + cnt10 * cnt01
print(ans)

Java

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();String num1 = scanner.next();String num2 = scanner.next();int cnt11 = 0, cnt00 = 0, cnt10 = 0, cnt01 = 0;for (int i = 0; i < n; i++) {if (num1.charAt(i) == '1' && num2.charAt(i) == '1') {cnt11++;} else if (num1.charAt(i) == '0' && num2.charAt(i) == '0') {cnt00++;} else if (num1.charAt(i) == '1' && num2.charAt(i) == '0') {cnt10++;} else if (num1.charAt(i) == '0' && num2.charAt(i) == '1') {cnt01++;}}int ans = cnt10 * cnt00 + cnt11 * cnt00 + cnt10 * cnt01;System.out.println(ans);}
}

C++

#include <iostream>
using namespace std;int main() {int n;cin >> n;string num1, num2;cin >> num1 >> num2;int cnt11 = 0, cnt00 = 0, cnt10 = 0, cnt01 = 0;for (int i = 0; i < n; i++) {if (num1[i] == '1' && num2[i] == '1') {cnt11++;} else if (num1[i] == '0' && num2[i] == '0') {cnt00++;} else if (num1[i] == '1' && num2[i] == '0') {cnt10++;} else if (num1[i] == '0' && num2[i] == '1') {cnt01++;}}int ans = cnt10 * cnt00 + cnt11 * cnt00 + cnt10 * cnt01;cout << ans << endl;return 0;
}

時空復雜度

時間復雜度：O(N)。一次遍歷求出四個變量的情況。

空間復雜度：O(1)。僅需若干常數變量

---

華為OD算法/大廠面試高頻題算法練習沖刺訓練

• 華為OD算法/大廠面試高頻題算法沖刺訓練目前開始常態化報名！目前已服務100+同學成功上岸！

• 課程講師為全網50w+粉絲編程博主@吳師兄學算法 以及小紅書頭部編程博主@閉著眼睛學數理化

• 每期人數維持在20人內，保證能夠最大限度地滿足到每一個同學的需求，達到和1v1同樣的學習效果！

• 60+天陪伴式學習，40+直播課時，300+動畫圖解視頻，300+LeetCode經典題，200+華為OD真題/大廠真題，還有簡歷修改、模擬面試、專屬HR對接將為你解鎖

• 可上全網獨家的歐弟OJ系統練習華子OD、大廠真題

• 可查看鏈接 大廠真題匯總 & OD真題匯總(持續更新)

• 綠色聊天軟件戳 od1336了解更多