学做各种糕点的网站,自己网站做搜索引擎优化,pc网站 手机网站 微信公众平台,网站设计超链接怎么做【五级编程题1】
【试题名称】#xff1a;小杨的幸运数
【问题描述】
小杨认为#xff0c;所有大于等于a的完全平方数都是他的超级幸运数。
小杨还认为#xff0c;所有超级幸运数的倍数都是他的幸运数。自然地#xff0c;小杨的所有超级幸运数也都是幸运数。
对于一个…【五级编程题1】
【试题名称】小杨的幸运数
【问题描述】
小杨认为所有大于等于a的完全平方数都是他的超级幸运数。
小杨还认为所有超级幸运数的倍数都是他的幸运数。自然地小杨的所有超级幸运数也都是幸运数。
对于一个非幸运数小杨规定可以将它一直1直到它变成一个幸运数。我们把这个过程叫做幸运化。例如如果a4那么4是最小的幸运数而1不是但我们可以连续对1做3次1操作使其变为4所以我们可以说1幸运化后的结果是4。
现在小样给出N个数请你首先判断它们是不是幸运数接着对于非幸运数请你将它们幸运化。
【输入描述】
第一行2个正整数a, N。
接下来 行每行一个正整数 表示需要判断幸运化的数。
【输出描述】
输出N行对于每个给定的x如果它是幸运数请输出“lucky”否则请输出将其幸运化后的结果。
【数据规模】
对于30%的测试点保证a,x≤100N≤100。
对于60%的测试点保证a,x≤10⁶。
对于所有测试点保证a≤1,000,001保证N≤2×10⁵保证1≤x≤1,000,001。
【分析】
方法一
如xa判是否是完全平方数或完全平方数的倍数输出“lukey”。如 int(x⁰·⁵) x⁰·⁵ 则为完全平方数在Python中x**0.5//1比int(x**0.5)快3倍左右x不是完全平方数则完全平方数的倍数个数不超过x⁰·⁵如是整数倍数则求商是否是完全平方数
对小于a或不是完全平方数或倍数的则需要加1至大于等于a直到是完全平方数或完全平方数的倍数输出该数。
搜索2个完全平方数的次数不超过2001(2001*2001-2000*2000)找完全平方数倍数不超过x⁰·⁵
时间复杂度O(n(x⁰·⁵2001))约2×10⁵×(10012001)≤6.1×10⁸应该不会超时。
【完整代码】
a, n [int(i) for i in input().split()] # 输入a和n
def p_square(n): # 判完全平方数或其倍数if n**0.5 n**0.5//1:return Trueelse:for i in range(2,int(x**0.5)1): # 倍数不超过int(x**0.5)if x // i x / i and (x//i)**0.5 (x//i)**0.5//1:return Trueelse:return False
for i in range(n): # 循环输入并处理n个数x int(input()) # 输入xtf Falseif x a:if p_square(x): # 如果是完全平方数或其倍数print(lucky) # 输出lucky tf Trueif not tf: # 如果是则需要加1while True:x 1if x a:if p_square(x): # 直到是完全平方数或其倍数print(x) # 输出该数break
【运行结果】 方法二
先建完全平方数和其倍数表(简称lucky表)将可能的数值范围内的完全平方数和其倍数纳入表中如直接从表的x位置(索引)中找到的数x则输出“lucky”否则输出该数。
因为题目给出a≤1,000,001N≤2×10⁵x≤1,000,001所以最大的完全平方数不超过1001*1001故先生成1001*10011元素为0的列表在1~1001的平方大于等于a的位置填上平方数(lucky数)并在其倍数位置填上相应倍数值(lucky数)。对于0值用后面与其最接近的lucky数填充。输了直接用x作为索引查询如x作为索引的值是x则a是lucky数输出“lucky”否则输出x作为索引的值。
时间复杂度小于O(4x)主要用于建表1001×10011001×20012×10⁵3.3×10⁶。
【完整代码】
a, n [int(i) for i in input().split()] # 输入a和n
max_ly 1001 * 1001 # 最大的lucky数不超过此数x≤1000001
nr_ly [0 for i in range(max_ly 1)] # 生成max_ly1个元素为0的列表
for i in range(1, int(max_ly**0.5)1):if i*i a: # 大于等于a的完全平方数元素位置填入此数nr_ly[i*i] i*ifor j in range(i*i i*i, max_ly, i*i): # 其倍数元素位置也填入其倍数nr_ly[j] j
for i in range(max_ly, 0, -1): # 两个lucky数之间最近的lucky数是后面的数if not nr_ly[i]: # 如i是lucky数则有值否则为0nr_ly[i] nr_ly[i 1] # 0值则填入其后面的数(最接近的lucky数)
for i in range(n): # 输入n个xx int(input()) # 输入xif nr_ly[x] x: # 如果x是lucky数输出“lucky”print(lucky)else:print(nr_ly[x]) # 否则输出最接近的lucky数(即x1至lucky数)
【运行结果】 【五级编程题2】
【试题名称】烹饪问题
【问题描述】
有N种食材编号从0至N-1其中第i种食材的美味度为ai。
不同食材之间的组合可能产生奇妙的化学反应。具体来说如果两种食材的美味度分别为x和y那么它们的契合度为x and y。
其中and运算为按位与运算需要先将两个运算数转换为二进制然后在高位补足 再逐位进行与运算。例如12与6的二进制表示分别为1100和0110将它们逐位进行与运算得到0100转换为十进制得到4因此12 and 6 4。在 C 或 Python 中可以直接使用 运算符表示与运算。
现在请你找到契合度最高的两种食材并输出它们的契合度。
【输入描述】
第一行一个整数N表示食材的种数。
接下来一行N个用空格隔开的整数依次为a0,…, aN-1表示各种食材的美味度。
【输出描述】
输出一行一个整数表示最高的契合度。
【数据规模】
对40%的测试点保证N≤1,000。
对所有测试点保证N≤10⁶0≤ai≤2,147,483,647(2³¹-1)。
【分析】
方法一
由于0≤ai≤2,147,483,647所以(ai aj)i≠j≥0因此结果最大值的初值可定义为0。因为ai aj aj ai先取第1个与其它N-1个数进行按位与运算如大于结果就赋给结果(求两数按位与的最大值)再取第2个与其后N-2个数进行按位与运算如大于结果就赋给结果(求两数按位与的最大值)以此类推直到所有数据都计算并比较大小。此解法时间复杂度为O(N²)可以解决40%多的数据当N≥10⁴就可能超时。
【完整代码】
n int(input()) # 输入n
a [int(i) for i in input().split()] # 输入n个食材的美味度
ans 0 # 初值为0
for i in range(n-1): # 0≤in-1for j in range(i1,n): # i1≤jnif a[i] a[j] ans: # a的下标为1~n-1ans a[i] a[j] # ans为两种食材的美味度的最大值
print(ans) # 输出结果
【运行结果】 方法二
因为ai≤2,147,483,647(2³¹-1)最多31位二进制从最高位开始枚举时间复杂度O(31N)可以解决所有数据不超时。
【完整代码】
n int(input()) # 输入n
a [int(i) for i in input().split()] # 输入n个食材的美味度
ans 0
for i in range(30,-1,-1): # 从最高位开始枚举ans 2**i # 加上当前二进制位为1cnt 0 # 统计数量for j in range(n): # 遍历所有数if (ans a[j] ans):cnt 1if cnt 2: # 两个以下ans - 2**i # 这一位为0(原加1现减去1)
print(ans) # 输出结果
【运行结果】
