今日复习计划：做题
例题1：笨笨的机器人
问题描述：
肖恩有一个机器人，他能根据输入的指令移动相应的距离。但是这个机器人很笨，他永远分不清往左边还是往右边移动。肖恩也知道这一点，所以他设定这个机器人不管向哪边只要走出7步就会自动回到原点（如果不这样设定机器人就有可能跑到肖恩找不到的地方）。请你计算肖恩给机器人一串指令后，机器人能回到肖恩面前的概率（机器人初始时在肖恩面前）。
输入描述：
第一行输入一个n，表示肖恩一次输入n条指令；
第二行输入n个整数，a[i]表示肖恩输入的第i条指令。
数据保证：1 <= n <= 15,0 <= a[i] <= 1000
输出描述：
输出一个浮点数表示机器人回到肖恩面前的概率。浮点数四舍五入后保留小数点后4位小数。
参考答案：
def get():
cnt = 0
for i in range(1<<n):
ans = 0
for j in range(n):
if (i >> j & 1 == 1):
ans += li[j]
else:
ans -= li[j]
if ans % 7 == 0:
cnt += 1
return 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,-1
for i in range(len(A)):
if tmp < ((V|A[i]) - V):
tmp = ((V|A[i]) - V)
ind = i
if ind == -1:
break
B.append(A[ind])
V|=A[ind]
A.remove(A[ind])
print(*A,*B)运行结果：
以下是我对此题的理解：
一行一行写太麻烦了，我用注释的形式表示出来：
n = int(input()) # 输入数字序列 A 的长度
A = list(map(int,input().split())) # 输入数字序列 A
B = [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 和 ind
if tmp < add_value:
tmp = add_value
ind = i
# 如果找不到能够增加字典序的数字，则结束循环
if ind == -1:
break
# 将找到的数字添加到 B 中，并更新 V
B.append(A[ind])
V |= A[ind]
A.remove(A[ind]) # 从 A 中移除已经添加到 B 中的数字
# 输出新序列，保持原数组输入顺序
print(*A, *B)
好了，以上的注释就是我的思路。
OK,今天状态不好，这篇就这样了，下一篇继续！
