今日復習計劃：做題
例題1：笨笨的機器人
問題描述：
肖恩有一個機器人，他能根據輸入的指令移動相應的距離。但是這個機器人很笨，他永遠分不清往左邊還是往右邊移動。肖恩也知道這一點，所以他設定這個機器人不管向哪邊只要走出7步就會自動回到原點（如果不這樣設定機器人就有可能跑到肖恩找不到的地方）。請你計算肖恩給機器人一串指令后，機器人能回到肖恩面前的概率（機器人初始時在肖恩面前）。
輸入描述：
第一行輸入一個n，表示肖恩一次輸入n條指令；
第二行輸入n個整數，a[i]表示肖恩輸入的第i條指令。
數據保證：1 <= n <= 15,0 <= a[i] <= 1000
輸出描述：
輸出一個浮點數表示機器人回到肖恩面前的概率。浮點數四舍五入后保留小數點后4位小數。
參考答案：
def get():cnt = 0for i in range(1<<n):ans = 0for j in range(n):if (i >> j & 1 == 1):ans += li[j]else:ans -= li[j]if ans % 7 == 0:cnt += 1return cnt
n = int(input())
tot = 2**n
li = list(map(int,input().split()))
cnt = get()
print('{:.4f}'.format(cnt / tot + 0.0000001))運行結果：
以下是我對此題的理解：
這道題目可以通過暴力枚舉的方式來解決。我們可以枚舉所有可能的指令組合，并計算每個組合下機器人能否回到原點。然后，統計滿足條件的組合數量，并計算其概率。
思路解析：
1.枚舉所有可能的指令組合
使用位運算可以方便地枚舉所有可能的指令組合。假設肖恩輸入了n條指令，那么一共有2^n種指令組合，即1 << n；
2.計算每個組合下機器人是否能夠回到原點
遍歷每個指令組合，根據指令的正負確定機器人的移動方向，并累加移動的距離。然后判斷移動的距離能否整除7，如果能，則表示機器人可以回到原點。
3.統計滿足條件的組合數量
統計滿足條件的組合數量，即機器人能夠回到原點的組合數量。
4.計算概率
將滿足條件的組合數量除以總的指令組合數量，得到機器人回到原點的概率。
接下來是我的代碼解釋：
def get():定義了一個函數get，用來統計滿足條件的組合數
cnt = 0：初始化滿足條件的組合數量為0
for i in range(1<<n)：通過位運算枚舉所有可能出現的組合
ans = 0：初始化移動的距離為0
for j in range(n)：遍歷每個指令
if(i >> j & 1 == 1)：檢查當前指令是否在指令組合中
如果是，則將指令對應的距離加到ans中，否則，就減去。
if ans % 7 == 0：檢查ans是否為7的倍數
如果是，則說明機器人能回到原點，將滿足條件的組合數加一
return cnt：返回滿足條件的組合數量
n = int(input())：輸入肖恩一次輸入的指令數量
tot = 2 ** n：計算總的組合數量
li = list(map(int,input().split()))：輸入肖恩所輸入的指令列表
cnt = get()：調用get函數統計滿足條件的組合數量
print('{:.4f}'.format(cnt / tot + 0.0000001))：計算最后答案。加上0.0000001是為了避免除法運算時可能出現的精度損失導致的錯誤舍入。
例題2：迷失之數
問題描述：
肖恩是一名冒險家，他聽說在一座神秘的迷宮中隱藏著巨大的寶藏，迷宮中有一個特殊的房間，房間里有一行數字序列A，被稱之為”迷失之數“，傳說有著神秘的力量。
據傳言，只有將這些數字重新排列，才能找到通往寶藏的路徑。肖恩發現，通過重排這個數字序列，使得重排后的序列的前綴或和數組B的字典序最大，就能夠觸發隱藏在迷宮深處的傳送門，進入寶藏所在的禁地。
肖恩希望能夠成功解開這個謎題，以獲得寶藏的榮譽和財富。他需要利用自己的智慧和洞察力，找到最佳的數字排列方式。現在，你能幫助肖恩找到正確的序列，找到通往寶藏的序列嗎？
前綴或和：B[i] = a[1] or a[2] or a[3] or... or a[i - 1] or a[i]稱B[i]為A的前綴1到i的前綴或和。
輸入描述：
第一行輸入一個n，表示數字序列A的長度；
第二行輸入n個數字，第i個數字A[i]表示序列的第i個數字。
數據保證：1 <= n <= 10^6,1 <= A[i] <= 10^9。
輸出描述：
輸出n個數字，表示前綴或和字典序最大的序列。
若字典序相同時，保持原數組輸入順序不變，即若ai和aj(i < j)在某一位置能得到相同字典序的序列時，保持ai在aj之前。
參考答案：
n = int(input())
A = list(map(int,input().split()))
B = [max(A)]
V = max(A)
A.remove(max(A))
for _ in range(30):tmp,ind = -1,-1for i in range(len(A)):if tmp < ((V|A[i]) - V):tmp = ((V|A[i]) - V)ind = iif ind == -1:breakB.append(A[ind])V|=A[ind]A.remove(A[ind])
print(*A,*B)運行結果：
以下是我對此題的理解：
一行一行寫太麻煩了，我用注釋的形式表示出來：
n = int(input()) # 輸入數字序列 A 的長度
A = list(map(int,input().split())) # 輸入數字序列 AB = [max(A)] # 初始化一個數組 B，初始值為 A 中的最大值，表示序列的第一個數字
V = max(A) # 使用變量 V 來記錄當前已經形成的前綴或和A.remove(max(A)) # 從 A 中移除最大值，因為最大值已經添加到 B 中# 循環 30 次，這里選擇 30 次是因為題目中限定了數字范圍為 1 到 10^9，而 2^30 = 1073741824 大于 10^9
for _ in range(30):tmp, ind = -1, -1 # 初始化臨時變量 tmp 和索引 ind，用于記錄最大增加值和對應的索引# 遍歷 A 中的數字，找到能夠使得字典序最大的數字for i in range(len(A)):# 計算當前數字與 V 進行按位或操作后的增加值add_value = (V | A[i]) - V# 比較增加值是否大于臨時變量 tmp，如果是則更新 tmp 和 indif tmp < add_value:tmp = add_valueind = i# 如果找不到能夠增加字典序的數字，則結束循環if ind == -1:break# 將找到的數字添加到 B 中，并更新 VB.append(A[ind])V |= A[ind]A.remove(A[ind]) # 從 A 中移除已經添加到 B 中的數字# 輸出新序列，保持原數組輸入順序
print(*A, *B)
好了，以上的注釋就是我的思路。
OK,今天狀態不好，這篇就這樣了，下一篇繼續！
