python 基礎知識點（藍橋杯python科目個人復習計劃56）

今日復習內容：做題

例題1：最小的或運算

問題描述：給定整數a,b，求最小的整數x，滿足a|x = b|x，其中|表示或運算。

輸入格式：

第一行包括兩個正整數a，b；

輸出格式：

輸出共1行，包含一個整數，表示最終答案。

參考答案：

a,b = map(int,input().split())
print(a^b)

運行結果：?

以下是我對此題的理解：

1.因為題目要求找到一個最小的整數x，使得a|x = b|x，其中|x表示a和b的二進制形式對應位進行或運算；

2.從最高位開始比較，如果a和b在該位上的值相同（即都為0或都為1），那么x在該位上可以取任意值，不影響最終結果。因此，我們可以直接將該位的添加到結果x中。

3.如果在某一位上a和b的值不同（即一個為1，一個為0），那么為了使得a|x = b|x，我們需要將x在該位上的值設為1，因為1與任何數進行或運算都得到1。

4.最終，得到的x就是滿足條件的最小整數

這種做法基于按位異或運算（^）的定義如下：

如果兩個對應的二進制位相同，則結果為0；

如果兩個對應的二進制位不同，則結果為1。

根據這個定義，當a和b的某一位不同時，按位異或的結果為1，這意味著在結果x的對應位上必須為1，否則無法滿足條件。而當a，b的某一位相同時，按位異或的結果為0，這意味著在結果x的對應位上可以時0或1，都不影響最終結果。

因此用這個方法，可以得出答案。

例題2：簡單的異或難題

問題描述：

最近藍橋A夢喜歡上了或運算，特別是沉迷于異或運算。

異或運算的特殊之處在于，進行異或運算的兩個數a和b，，對于它們在二進制下的同一位，只有兩邊數不相同，運算的結果才為1，如果相同，則為0。比如1和3進行運算，它們轉化成二進制后，分別為01和11，那么它們的異或運算結果就是10，轉換成十進制后就是2。

異或運算實在是太有趣了，他這些天一直在進行異或運算，藍橋美怕他走火入魔了，打算給藍橋A夢出個難題打擊一下他的興趣。

藍橋美給了藍橋A夢n個正整數ai，然后進行m次詢問，每次詢問在第l個數到第r個數之間，所有出現次數為奇數的數的異或和是多少。

對于3個數a，b，c，它們的異或和就是：

這種難題怎么會難倒藍橋A夢呢？他并不想回答這么簡單的問題，所以他把問題扔給了你，你能解決嗎？

輸入格式：

第一行包括兩個正整數n和m(1 <= n,m <= 1 * 10^5)，表示數組的長度和詢問的次數。

第二行包含n個正整數ai(1 <= ai <= 10^5)，ai表示第i個位置上的數字是ai。

接下來m行，每行包含兩個正整數l和r(1<= l,r <= n)，表示當前詢問的區間。

輸出格式：

對于每一行詢問，輸出一個整數，為當前詢問區間[l,r]的出現次數為奇數的數的異或和。

參考答案：

n,m = map(int,input().split())
a = list(map(int,input().split()))
pre = [0]
for i in range(n):pre.append(pre[-1]^a[i])
for i in range(m):l,r = map(int,input().split())print(pre[r]^pre[l - 1])

運行結果：

以下是我對此題的理解：

n,m = map(int,input().split())

a = list(map(int,input().split()))

首先，讀取輸入，包括正整數的個數n，查詢次數m以及正整數序列a；

pre = [0]

for i in range(n):

pre.append(pre[-1] ^ a[i])

使用一個數組pre來存儲前綴異或和，其中pre[i]表示前i個數的異或和，這里pre的作用是為了方便計算任意區間的異或和。

在這個循環中，計算每個位置的前綴異或和，pre[-1]表示前i個數的異或和，然后再異或上當前數a[i]，得到前i + 1個數的異或和，依次類推。

接下來就是讀取查詢區間[l,r]。

例題3：出列

問題描述：

上體育課時，n個同學按順序站成一排，初始時第i個位置的同學，編號為i（從1開始）。

老師下令：“單數同學出列！”然后序號為單數的同學出列，剩下的同學重新按位置開始排列，編號不變。

老師又下令：“單數同學出列！”新的單數位置的同學出列，剩下的同學繼續重新按位置排列。

如此下去，最后只剩下一個人，他的編號是多少？

輸入格式：

輸入僅一行，包含一個整數n。

輸出格式：

輸出僅一行，包含一個整數，表示最后剩下的人的編號。

參考答案：

n = int(input())
bin_n = bin(n)[2:]
print(1 << (len(bin_n) - 1))

運行結果：

以下是我對此題的理解：

我剛開始想到的是數學歸納法：

首先觀察一下題目，每次出列后，剩下的同學的編號會重新排列，但總是保持著奇數編號的同學被淘汰。當剩下的同學數量為奇數時，淘汰后剩下的同學編號從2開始重新編號。由此可以得出結論：之后剩下的同學編號一定是2的冪次方，因此，我們只需要找到，因此我們只需要找到小于等于n的最大的2的冪次方，就得到了答案。

首先，將輸入的n轉化為二進制字符字符串并去掉開頭的‘0b’；

然后，通過len(bin_n) - 1計算二進制表示的n的位數；

最后，通過1 << (len(bin_n) - 1)得到最后的同學的編號，即為小于等于n的最大的2的冪次方；

bin(n)[2:]

將輸入的n轉化為二進制字符字符串并去掉開頭的‘0b’

len(bin_n) - 1：計算二進制字符串的長度，即二進制的位數

1 << (len(bin_n) - 1)：左移<<表示將1左移若干位，相當于乘以2的若干次方，這里左移的位數為二進制的位數減一，就是最后的那個學生的編號

然后，我就想到了另外一種方法：

n = int(input())# 尋找小于等于n的最大的2的冪次方
last_student = 1
while last_student <= n:last_student *= 2# 最后剩下的同學的編號即為小于等于n的最大的2的冪次方的一半
last_student //= 2print(last_student)

?例題4：位移

問題描述：

在一個神奇的玩具世界中，有兩個小朋友，小明和小紅，他們喜歡玩數字游戲。一天，他們發現了一種神奇的數字變換能力，只需使用位移運算（<<和>>）就能將一個數字變成另一個數字。

小明和小紅決定進行一場數字變換的挑戰。他們選定了兩個數字a和b，并嘗試通過位移運算講數字a變成數字b。他們非常興奮，想知道是否存在一系列的位移操作可以實現這個目標。

他們開始思考，并設計了各種位移操作的組合，希望能夠將數字a變成數字b。如果他們成功找到一種位移操作組合，則輸出Yes，否則輸出No。

現在，讓我們來幫小明和小紅來完成這個數字變換的挑戰，看看他們能否成功通過數字變換講數字a變成數字b。

右移和左移的運算規則為：邏輯左移，高位丟棄，低位補0；邏輯右移，低位丟棄，高位補0。如0000100，邏輯左移一位為0001000，邏輯右移一位為0000010。（需著重注意左移高位的變化）

輸入描述：

第一行輸入一個整數t，表示有t組測試數據；

接下來又t行輸入，每行包含兩個數字a和b，a和b意義如題目所述。

數據保證1 <= t <= 10^6,0 <= a,b <= 10^9

輸出描述：

對于每一組測試數據，輸出Yes或No。

參考答案：

import sys
t = int(input())
for i in range(t):a,b = map(int,sys.stdin.readline().strip('\n').split())bin_b = bin(b)[2:].strip('0')bin_a = bin(a)[2:]if bin_b in bin_a:print('Yes')else:print('No')

運行結果：