今日复习内容:做题
例题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,这篇就到这里,下一篇继续!