【五級(jí)編程題1】

【試題名稱】：小楊的幸運(yùn)數(shù)

【問題描述】

小楊認(rèn)為，所有大于等于a的完全平方數(shù)都是他的超級(jí)幸運(yùn)數(shù)。

小楊還認(rèn)為，所有超級(jí)幸運(yùn)數(shù)的倍數(shù)都是他的幸運(yùn)數(shù)。自然地，小楊的所有超級(jí)幸運(yùn)數(shù)也都是幸運(yùn)數(shù)。

對(duì)于一個(gè)非幸運(yùn)數(shù)，小楊規(guī)定，可以將它一直+1，直到它變成一個(gè)幸運(yùn)數(shù)。我們把這個(gè)過程叫做幸運(yùn)化。例如，如果a=4，那么4是最小的幸運(yùn)數(shù)，而1不是，但我們可以連續(xù)對(duì)1做3次+1操作，使其變?yōu)?/span>4，所以我們可以說，1幸運(yùn)化后的結(jié)果是4。

現(xiàn)在，小樣給出N個(gè)數(shù)，請(qǐng)你首先判斷它們是不是幸運(yùn)數(shù)；接著，對(duì)于非幸運(yùn)數(shù)，請(qǐng)你將它們幸運(yùn)化。

【輸入描述】

第一行2個(gè)正整數(shù)a, N。

接下來 行，每行一個(gè)正整數(shù) ，表示需要判斷（幸運(yùn)化）的數(shù)。

【輸出描述】

輸出N行，對(duì)于每個(gè)給定的x，如果它是幸運(yùn)數(shù)，請(qǐng)輸出“l(fā)ucky”，否則請(qǐng)輸出將其幸運(yùn)化后的結(jié)果。

【數(shù)據(jù)規(guī)?！?/span>

對(duì)于30%的測試點(diǎn)，保證a,x≤100，N≤100。

對(duì)于60%的測試點(diǎn)，保證a,x≤10?。

對(duì)于所有測試點(diǎn)，保證a≤1,000,001；保證N≤2×10?；保證1≤x≤1,000,001。

【分析】

方法一

如x>=a，判是否是完全平方數(shù)或完全平方數(shù)的倍數(shù)，輸出“l(fā)ukey”。如 int(x?·?)= x?·? 則為完全平方數(shù)，在Python中x**0.5//1比int(x**0.5)快3倍左右；x不是完全平方數(shù)，則完全平方數(shù)的倍數(shù)個(gè)數(shù)不超過x?·?，如是整數(shù)倍數(shù)，則求商是否是完全平方數(shù)？

對(duì)小于a或不是完全平方數(shù)或倍數(shù)的，則需要加1至大于等于a，直到是完全平方數(shù)或完全平方數(shù)的倍數(shù)，輸出該數(shù)。

搜索2個(gè)完全平方數(shù)的次數(shù)不超過2001(2001*2001-2000*2000)，找完全平方數(shù)倍數(shù)不超過x?·?

時(shí)間復(fù)雜度：O(n(x?·?+2001))，約2×10?×(1001+2001)≤6.1×10?，應(yīng)該不會(huì)超時(shí)。

【完整代碼】

a, n = [int(i) for i in input().split()]???????????????# 輸入a和n
def p_square(n):???????????????????????????????????????# 判完全平方數(shù)或其倍數(shù)if n**0.5 == n**0.5//1:return Trueelse:for i in range(2,int(x**0.5)+1):?????????????? # 倍數(shù)不超過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):?????????????????????????????????????# 循環(huán)輸入并處理n個(gè)數(shù)x = int(input())???????????????????????????????????# 輸入xtf = Falseif x >= a:if p_square(x):????????????????????????????????# 如果是完全平方數(shù)或其倍數(shù)print('lucky')?????????????????????????????# 輸出lucky tf = Trueif not tf: ????????????????????????????????????????# 如果是則需要加1while True:x += 1if x >= a:if p_square(x):????????????????????????# 直到是完全平方數(shù)或其倍數(shù)print(x)???????????????????????????# 輸出該數(shù)break

【運(yùn)行結(jié)果】

方法二

先建完全平方數(shù)和其倍數(shù)表(簡稱lucky表)，將可能的數(shù)值范圍內(nèi)的完全平方數(shù)和其倍數(shù)納入表中，如直接從表的x位置(索引)中找到的數(shù)=x，則輸出“lucky”，否則輸出該數(shù)。

因?yàn)轭}目給出a≤1,000,001，N≤2×10?，x≤1,000,001，所以最大的完全平方數(shù)不超過1001*1001，故先生成1001*1001+1元素為0的列表，在1~1001的平方大于等于a的位置填上平方數(shù)(lucky數(shù))，并在其倍數(shù)位置填上相應(yīng)倍數(shù)值(lucky數(shù))。對(duì)于0值用后面與其最接近的lucky數(shù)填充。輸了直接用x作為索引查詢，如x作為索引的值是x，則a是lucky數(shù)，輸出“lucky”，否則輸出x作為索引的值。

時(shí)間復(fù)雜度：小于O(4x)，主要用于建表，1001×1001+1001×2001+2×10?<3.3×10?。

【完整代碼】

a, n = [int(i) for i in input().split()]?? ??????# 輸入a和n
max_ly = 1001 * 1001?????????????????????????????# 最大的lucky數(shù)不超過此數(shù)，x≤1000001
nr_ly = [0 for i in range(max_ly + 1)]???????????# 生成max_ly+1個(gè)元素為0的列表
for i in range(1, int(max_ly**0.5)+1):if i*i >= a:???????????????????????????? ????# 大于等于a的完全平方數(shù)元素位置填入此數(shù)nr_ly[i*i] = i*ifor j in range(i*i + i*i, max_ly, i*i):? # 其倍數(shù)元素位置也填入其倍數(shù)nr_ly[j] = j
for i in range(max_ly, 0, -1):???????????????????# 兩個(gè)lucky數(shù)之間最近的lucky數(shù)是后面的數(shù)if not nr_ly[i]:?????????????????????????????# 如i是lucky數(shù)則有值，否則為0nr_ly[i] = nr_ly[i + 1]??????????????????# 0值則填入其后面的數(shù)(最接近的lucky數(shù))
for i in range(n):???????????????????????????????# 輸入n個(gè)xx = int(input())???????????????????????????? # 輸入xif nr_ly[x] == x:????????????????????????????# 如果x是lucky數(shù)輸出“l(fā)ucky”print("lucky")else:print(nr_ly[x])??????????????????????????# 否則輸出最接近的lucky數(shù)(即x+1至lucky數(shù))

【運(yùn)行結(jié)果】

【五級(jí)編程題2】

【試題名稱】：烹飪問題

【問題描述】

有N種食材，編號(hào)從0至N-1，其中第i種食材的美味度為ai。

不同食材之間的組合可能產(chǎn)生奇妙的化學(xué)反應(yīng)。具體來說，如果兩種食材的美味度分別為x和y，那么它們的契合度為x and y。

其中，and運(yùn)算為按位與運(yùn)算，需要先將兩個(gè)運(yùn)算數(shù)轉(zhuǎn)換為二進(jìn)制，然后在高位補(bǔ)足 ，再逐位進(jìn)行與運(yùn)算。例如，12與6的二進(jìn)制表示分別為1100和0110，將它們逐位進(jìn)行與運(yùn)算，得到0100，轉(zhuǎn)換為十進(jìn)制得到4，因此12 and 6 = 4。在 C++ 或 Python 中，可以直接使用 & 運(yùn)算符表示與運(yùn)算。

現(xiàn)在，請(qǐng)你找到契合度最高的兩種食材，并輸出它們的契合度。

【輸入描述】

第一行一個(gè)整數(shù)N，表示食材的種數(shù)。

接下來一行N個(gè)用空格隔開的整數(shù)，依次為a0,…, aN-1，表示各種食材的美味度。

【輸出描述】

輸出一行一個(gè)整數(shù)，表示最高的契合度。

【數(shù)據(jù)規(guī)?！?/span>

對(duì)40%的測試點(diǎn)保證N≤1,000。

對(duì)所有測試點(diǎn)保證N≤10?，0≤ai≤2,147,483,647(231-1)。

【分析】

方法一

由于0≤ai≤2,147,483,647，所以(ai & aj)i≠j≥0，因此結(jié)果最大值的初值可定義為0。因?yàn)?/span>ai & aj = aj & ai，先取第1個(gè)與其它N-1個(gè)數(shù)進(jìn)行按位與運(yùn)算，如大于結(jié)果就賦給結(jié)果(求兩數(shù)按位與的最大值)，再取第2個(gè)與其后N-2個(gè)數(shù)進(jìn)行按位與運(yùn)算，如大于結(jié)果就賦給結(jié)果(求兩數(shù)按位與的最大值)，以此類推，直到所有數(shù)據(jù)都計(jì)算并比較大小。此解法時(shí)間復(fù)雜度為O(N2)，可以解決40%多的數(shù)據(jù)，當(dāng)N≥10?就可能超時(shí)。

【完整代碼】

n = int(input())??????????????????????????????????# 輸入n
a = [int(i) for i in input().split()]?????????????# 輸入n個(gè)食材的美味度
ans = 0???????????????????????????????????????????# 初值為0
for i in range(n-1):??????????????????????????????# 0≤i<n-1for j in range(i+1,n):????????????????????????# i+1≤j<nif a[i] & a[j] > ans: ??????????????????? # a的下標(biāo)為1~n-1ans = a[i] & a[j]?????????????????    # ans為兩種食材的美味度的最大值
print(ans)????????????????????????????????????????# 輸出結(jié)果

【運(yùn)行結(jié)果】

方法二

因?yàn)?/span>ai≤2,147,483,647(231-1)，最多31位二進(jìn)制，從最高位開始枚舉，時(shí)間復(fù)雜度O(31N)，可以解決所有數(shù)據(jù)，不超時(shí)。

【完整代碼】

n = int(input())??????????????????????????????????????# 輸入n
a = [int(i) for i in input().split()]???????????????? # 輸入n個(gè)食材的美味度
ans = 0
for i in range(30,-1,-1):?????????????????????????????# 從最高位開始枚舉ans += 2**i?????? ????????????????????????????????# 加上當(dāng)前二進(jìn)制位為1cnt = 0???????????????????????????????????????????# 統(tǒng)計(jì)數(shù)量for j in range(n):????????????????????????????????# 遍歷所有數(shù)if (ans & a[j] == ans):cnt += 1if cnt < 2:???????????????????????????????????????# 兩個(gè)以下ans -= 2**i??????? ???????????????????????????# 這一位為0(原加1，現(xiàn)減去1)
print(ans) ???????????????????????????????????????????# 輸出結(jié)果

【運(yùn)行結(jié)果】