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 //= 2
 
print(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')

运行结果：

 

以下是我对此题的理解：

这道题可以检查数字b的二进制表示是否是数字a的二进制表示的字符串的子串来解决。如果是，则说明存在一系列位移操作可以将数字a转换为数字b，否则不能。

以下是我的思路：

1.二进制表示的子串

当一个二进制数字b是另一个二进制数字a的子串时，意味着可以通过在数字a的二进制表示中通过位移操作来得到b，因为位移操作不会改变数字1和0的位置，只会改变它们的相对位置。

2.代码解析

首先输入测试用例的数量t；

然后通过一个循环处理每个测试用例，输入数字a和b；

接着，将a和b转化为二进制字符串；

然后检查数字b的二进制表示是否是数字a的二进制表示的字符串的字串；

如果是字串，则输出"Yes"，说明存在一系列位移操作可以将a转换为b；

否则输出"No"，说明不能通过位移操作将a转换为b。

---

OK，这篇就到这里，下一篇继续！