Python解答藍橋杯省賽真題之從入門到真題
若發現此文章消失，則是在等待稽核中，稍等一會兒即可顯示，謝謝。
另外，我會盡量晚上上傳更新題目。
此文章太長了，導致MD編輯器很卡，另寫了一篇接續
傳送門
Python解答藍橋杯省賽真題之從入門到真題 （續）
我的GitHub：https://github.com/libo-sober/LanQiaoCup
GitHub中程式碼為第二刷，對本文中的好多程式碼都進行了優化以及簡化，歡迎大家Fork和Star。
不會使用Github夥伴們可以看我出的教學。
如何把自己開發的專案上傳到GitHub倉庫或者碼雲倉庫？
如何把Github上好的專案pull到本地或者fork到本地（碼雲倉庫同理）？
搜了很多歷年藍橋杯真題解答，大多都是Java，C++，C這些語言編寫的程式碼解析。Python解析的幾乎，甚至可以說沒有。而當下Python又這麼火熱，藍橋杯也出了Python組，所以打算寫一個Python解答藍橋杯真題的部落格，供大家參考，也在這過程中和大家一起交流。
**自己編的的程式碼，有時間就會更新。有誤之處，歡迎改正。
**
1.入門篇
1.1 Fibonacci數列題
問題描述
Fibonacci數列的遞推公式為：Fn=Fn-1+Fn-2，其中F1=F2=1。
當n比較大時，Fn也非常大，現在我們想知道，Fn除以10007的餘數是多少。
輸入描述
n
輸入格式輸入包含一個整數n。
輸出描述
輸出格式輸出一行，包含一個整數，表示Fn除以10007的餘數。
說明：在本題中，答案是要求Fn除以10007的餘數，因此我們只要能算出這個餘數即可，而不需要先計算出Fn的準確值，再將計算的結果除以10007取餘數，直接計算餘數往往比先算出原數再取餘簡單。
資料規模與約定1 <= n <= 1,000,000
n = int(input())
Fib = [1 for i in range(n+1)]
k = 3
while k<=n:
Fib[k] = (Fib[k-1] + Fib[k-2]) % 10007
k += 1
print(Fib[n])
1.2 入門訓練 圓的面積
問題描述
給定圓的半徑r，求圓的面積。
輸入格式
輸入包含一個整數r，表示圓的半徑。
輸出格式
輸出一行，包含一個實數，四捨五入保留小數點後7位，表示圓的面積。
樣例輸入
4
樣例輸出
50.2654825
資料規模與約定
1 <= r <= 10000。
import math
r = int(input())
area = math.pi * r * r
print('%.7f' % area)
1.3 入門訓練 序列求和
問題描述
求1+2+3+…+n的值。
輸入格式
輸入包括一個整數n。
輸出格式
輸出一行，包括一個整數，表示1+2+3+…+n的值。
樣例輸入
4
樣例輸出
10
資料規模與約定
1 <= n <= 1,000,000,000.
注意不要用迴圈來做，否則當資料規模變大時會超時
n = int(input())
s = n * (n + 1) / 2 # 等差數列公式，節省很多時間
print('%d' % s)
1.4 入門訓練 A+B問題
問題描述
輸入A、B，輸出A+B。
輸入格式
輸入的第一行包括兩個整數，由空格分隔，分別表示A、B。
輸出格式
輸出一行，包括一個整數，表示A+B的值。
樣例輸入
12 45
樣例輸出
57
資料規模與約定
-10000 <= A, B <= 10000
# 注意：本體資料規模較小，可以正常計算
# 若資料規模過大，則考慮用字串存取大數，然後用大數加法來計算結果並輸出
a, b = map(int, input().split())
print(a + b)
2.基礎篇
2.1 數列排序
問題描述
給定一個長度為n的數列，將這個數列按從小到大的順序排列。1<=n<=200
輸入格式
第一行為一個整數n。
第二行包含n個整數，為待排序的數，每個整數的絕對值小於10000。
輸出格式
輸出一行，按從小到大的順序輸出排序後的數列。
樣例輸入
5
8 3 6 4 9
樣例輸出
3 4 6 8 9
# 程式碼1
n = int(input())
arr = list(map(int, input().split()))
arr.sort()
for i in range(n):
print(arr[i], end=' ')
# 程式碼2
n = int(input())
arr = list(map(int, input().split()))
arr.sort()
for i in range(n - 1):
print(arr[i], end=' ')
print(arr[n-1])
# 程式碼3
n = int(input())
arr = list(map(int, input().split()))
arr.sort()
for i in range(n - 1):
print(arr[i], end=' ')
print(arr[n-1], end='')
藍橋的練習系統沒有OJ那麼嚴格，故意試了一下，程式碼1最後一個數位輸出時後邊會有一個空格，OJ上這樣是不予通過的，但是藍橋練習系統這樣提交了之後仍然通過。程式碼2最後無空格進行換行，藍橋練習系統也通過了。程式碼3最後不換行，也不輸出空格，輸出最後一個數後就停止，藍橋練習系統也通過了。看來對這個藍橋要求不嚴格。考試時自己斟酌。
2.2 十六進位制轉八進位制
問題描述
給定n個十六進位制正整數，輸出它們對應的八進位制數。
輸入格式
輸入的第一行為一個正整數n （1<=n<=10）。
接下來n行，每行一個由09、大寫字母AF組成的字串，表示要轉換的十六進位制正整數，每個十六進位制數長度不超過100000。
輸出格式
輸出n行，每行為輸入對應的八進位制正整數。
【注意】
輸入的十六進位制數不會有前導0，比如012A。
輸出的八進位制數也不能有前導0。
樣例輸入
2
39
123ABC
樣例輸出
71
4435274
【提示】
先將十六進位制數轉換成某進位制數，再由某進位制數轉換成八進位制。
t = int(input())
# print(t)
for i in range(t):
n = input()
# ans = oct(int(n, 16))
# print(ans[2:])
ans = format(int(n, 16), 'o')
print(ans)
參考知識
2.3 十六進位制轉十進位制
問題描述
從鍵盤輸入一個不超過8位元的正的十六進位制數位符串，將它轉換為正的十進位制數後輸出。
注：十六進位制數中的10~15分別用大寫的英文字母A、B、C、D、E、F表示。
樣例輸入
FFFF
樣例輸出
65535
n = input()
print(int(n, 16))
# 你沒有看錯，python就是這麼幹脆，兩行搞定
2.4 十進位制轉十六進位制
問題描述
十六進位制數是在程式設計時經常要使用到的一種整數的表示方式。它有0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F共16個符號，分別表示十進位制數的0至15。十六進位制的計數方法是滿16進1，所以十進位制數16在十六進位制中是10，而十進位制的17在十六進位制中是11，以此類推，十進位制的30在十六進位制中是1E。
給出一個非負整數，將它表示成十六進位制的形式。
輸入格式
輸入包含一個非負整數a，表示要轉換的數。0<=a<=2147483647
輸出格式
輸出這個整數的16進位製表示
樣例輸入
30
樣例輸出
1E
n = int(input())
print(format(n, 'X')) # x 輸出字母為小寫 X 輸出字母為大寫
2.5 特殊迴文數
問題描述
123321是一個非常特殊的數，它從左邊讀和從右邊讀是一樣的。
輸入一個正整數n， 程式設計求所有這樣的五位和六位十進位制數，滿足各位數位之和等於n 。
輸入格式
輸入一行，包含一個正整數n。
輸出格式
按從小到大的順序輸出滿足條件的整數，每個整數佔一行。
樣例輸入
52
樣例輸出
899998
989989
998899
資料規模和約定
1<=n<=54。
Python這個時候我發現出了點問題：
同樣的程式碼C寫的程式會比Python寫的程式執行時間短。
上述題目時限為1s，C程式如下，藍橋練習系統提交通過。
#include<stdio.h>
int a(int n)//求出5位數和6位數中的迴文數函數
{
int i,j,sum,temp,len;
int a,b,c;
for(i=10000;i<1000000;++i)
{
sum=0;
temp=i;
len=0;
while(temp!=0)
{
sum=sum*10+temp%10;
temp=temp/10;
len++;//累計位數以此判斷是5位數還是6位數
}
if(sum==i)//先把迴文數求出來，下面再來比較各位數位之和是否等於n
{
a=i%10;//個位
b=i/10%10;//十位
c=i/100%10;//百位
if(5==len)
{
if(n==(2*a+2*b+c))
{
printf("%d\n",i);
}
}
if(6==len)
{
if(n==(2*a+2*b+2*c))
{
printf("%d\n",i);
}
}
}
}
}
//主函數
int main()
{
int n;
scanf("%d",&n);
a(n);
return 0;
}
然而把語言換成Python，演演算法思想一樣，提交卻超時，一看，時間已經為5s多了
import time
start = time.clock()
n = int(input())
i = 10000
while i < 1000000:
s = 0
temp = i
length = 0
while temp != 0:
s = s * 10 + temp % 10
temp = int(temp / 10)
length += 1
if s == i:
a = i % 10
b = int(i / 10) % 10
c = int(i / 100) % 10
if length == 5:
if n == 2 * (a + b) + c:
print(i)
if length == 6:
if n == 2 * (a + b + c):
print(i)
i += 1
end = time.clock()
print(end - start)
執行結果
時間為5.1s多
自己又寫了一個程式碼
import time
start = time.clock()
def is_pal(i_):
i_s = str(i_)
if i_s == i_s[::-1]:
return True
else:
return False
def sum_i(i_):
s = 0
i_s = str(i)
for j in range(len(i_s)):
s += int(i_s[j])
return s
n = int(input())
i = 10000
while i < 1000000:
if is_pal(i):
if sum_i(i) == n:
print(i)
i += 1
end = time.clock()
print(end - start)
執行結果
時間為2s多，還是不通過。
目前不清楚這個問題要怎麼解決，待解答。
2.6 迴文數
正著數和倒著數都一樣，輸出所有的這樣的四位數
如 1221
def is_pal(i_):
i_s = str(i_)
if i_s == i_s[::-1]:
return True
else:
return False
i = 1000
while i < 10000:
if is_pal(i):
print(i)
i += 1
2.7 水仙花數
問題描述
153是一個非常特殊的數，它等於它的每位數位的立方和，即153=111+555+333。程式設計求所有滿足這種條件的三位十進位制數。
輸出格式
按從小到大的順序輸出滿足條件的三位十進位制數，每個數佔一行。
def is_nar(i_):
a = i_ % 10 # 十位
b = int((i_ / 10)) % 10 # 百位 注意Python中除法一定會得到浮點數 要取整 而C中則不需要
c = int(i_ / 100)
if i_ == a ** 3 + b ** 3 + c ** 3:
return True
else:
return False
i = 100
while i < 1000:
if is_nar(i):
print(i)
i += 1
2.8 楊輝三角
問題描述
楊輝三角形又稱Pascal三角形，它的第i+1行是(a+b)i的展開式的係數。
它的一個重要性質是：三角形中的每個數位等於它兩肩上的數位相加。
下面給出了楊輝三角形的前4行：
1
1 1
1 2 1
1 3 3 1
給出n，輸出它的前n行。
輸入格式
輸入包含一個數n。
輸出格式
輸出楊輝三角形的前n行。每一行從這一行的第一個數開始依次輸出，中間使用一個空格分隔。請不要在前面輸出多餘的空格。
樣例輸入
4
樣例輸出
1
1 1
1 2 1
1 3 3 1
資料規模與約定
1 <= n <= 34。
n = int(input())
k = 2
triangle_yang = [] # 楊輝三角
for i in range(n): # 定義空的楊輝三角
triangle_yang.append([0 for j in range(i+1)])
# print(triangle_yang)
# exit()
for i in range(n): # 第一列和每一行的最後一個為1
triangle_yang[i][0] = triangle_yang[i][-1] = 1
while k < n:
m = 1
while m < k: # 兩肩數值之和
triangle_yang[k][m] = triangle_yang[k-1][m-1] + triangle_yang[k-1][m]
m += 1
k += 1
for i in range(n): # 輸出楊輝三角
for j in range(i+1):
print(triangle_yang[i][j], end=' ')
print()
2.9 查詢整數
問題描述
給出一個包含n個整數的數列，問整數a在數列中的第一次出現是第幾個。
輸入格式
第一行包含一個整數n。
第二行包含n個非負整數，為給定的數列，數列中的每個數都不大於10000。
第三行包含一個整數a，為待查詢的數。
輸出格式
如果a在數列中出現了，輸出它第一次出現的位置(位置從1開始編號)，否則輸出-1。
樣例輸入
6
1 9 4 8 3 9
9
樣例輸出
2
資料規模與約定
1 <= n <= 1000。
n = int(input())
arr = input().split()
a = input()
i = 0
while i < n:
if a == arr[i]:
print(i+1)
break
i += 1
if i == n:
print(-1)
2.10 數列特徵
問題描述
給出n個數，找出這n個數的最大值，最小值，和。
輸入格式
第一行為整數n，表示數的個數。
第二行有n個數，為給定的n個數，每個數的絕對值都小於10000。
輸出格式
輸出三行，每行一個整數。第一行表示這些數中的最大值，第二行表示這些數中的最小值，第三行表示這些數的和。
樣例輸入
5
1 3 -2 4 5
樣例輸出
5
-2
11
資料規模與約定
1 <= n <= 10000。
n = int(input())
arr = input().split()
print(max(int(arr[i]) for i in range(n))) # 最大值
print(min(int(arr[i]) for i in range(n))) # 最小值
print(sum(int(arr[i]) for i in range(n))) # 求和
注意
python的列表中的sort()函數是無法對有負數元素的列表進行排序的，這點需要謹記，以防後續使用中出現錯誤
2.11 字母圖形
問題描述
利用字母可以組成一些美麗的圖形，下面給出了一個例子：
ABCDEFG
BABCDEF
CBABCDE
DCBABCD
EDCBABC
這是一個5行7列的圖形，請找出這個圖形的規律，並輸出一個n行m列的圖形。
輸入格式
輸入一行，包含兩個整數n和m，分別表示你要輸出的圖形的行數的列數。
輸出格式
輸出n行，每個m個字元，為你的圖形。
樣例輸入
5 7
樣例輸出
ABCDEFG
BABCDEF
CBABCDE
DCBABCD
EDCBABC
資料規模與約定
1 <= n, m <= 26。
n, m = map(int, input().split())
graph = [[0 for j in range(m)] for i in range(n)] # 空二維陣列
for i in range(n):
for j in range(m):
if j >= i: # 陣列中字母規律
graph[i][j] = chr(ord('A') + j - i)
else:
graph[i][j] = chr(ord('A') + i - j)
for i in range(n): # 輸出二維陣列
for j in range(m):
print(graph[i][j], end='')
print()
字元轉ASCII碼函數：ord(‘A’)–>64
ASCII碼轉字元函數：chr(64)–>A
以上進位制轉換題目提到過ASCII碼與字元轉換，可以點選連結觀看。
2.12 字串01
問題描述
對於長度為5位的一個01串，每一位都可能是0或1，一共有32種可能。它們的前幾個是：
00000
00001
00010
00011
00100
請按從小到大的順序輸出這32種01串。
輸入格式
本試題沒有輸入。
輸出格式
輸出32行，按從小到大的順序每行一個長度為5的01串。
樣例輸出
00000
00001
00010
00011
<以下部分省略>
# Python就是兩行解決問題。。。
for i in range(32):
print("{0:0>5}".format(format(i, 'b')))
參考資料
str.format新增前導零
Format Specification Mini-Language
Python的另外三種補0方法（其實就是字串處理常式）這裡不再做程式碼演示，請讀者自行嘗試。
2.13 閏年判斷
問題描述
給定一個年份，判斷這一年是不是閏年。
當以下情況之一滿足時，這一年是閏年：
-
年份是4的倍數而不是100的倍數；
-
年份是400的倍數。
其他的年份都不是閏年。
輸入格式
輸入包含一個整數y，表示當前的年份。
輸出格式
輸出一行，如果給定的年份是閏年，則輸出yes，否則輸出no。
說明：當試題指定你輸出一個字串作為結果（比如本題的yes或者no，你需要嚴格按照試題中給定的大小寫，寫錯大小寫將不得分。
樣例輸入
2013
樣例輸出
no
樣例輸入
2016
樣例輸出
yes
資料規模與約定
1990 <= y <= 2050。
def is_leap_year(year):
if year % 4 == 0 and year % 100 != 0 or year % 400 == 0:
return True
return False
year = int(input())
if is_leap_year(year):
print('yes')
else:
print('no')
裝逼解法
# 裝逼解法
import datetime # python的標準庫，藍橋考試可以放心使用
year = int(input())
# class datetime.timedelta(days=0, seconds=0, microseconds=0, milliseconds=0, minutes=0, hours=0, weeks=0)
# All arguments are optional and default to 0. Arguments may be integers or floats, and may be positive or negative.
time_delta = datetime.timedelta(days=1) # 儲存時間的變化量
# class datetime.date(year, month, day)
dt = datetime.date(year=year, month=3, day=1) # 指定輸入年份的3月1號
res = dt - time_delta # 讓dt儲存的日期往前走一天
# print(dt)
if res.day == 29: # 如果那年的2月分又29天為閏年
print('yes')
else:
print('no')
2.14 階乘計算
問題描述
輸入一個正整數n，輸出n!的值。
其中n!=123*…*n。
演演算法描述
n!可能很大，而計算機能表示的整數範圍有限，需要使用高精度計算的方法。使用一個陣列A來表示一個大整數a，A[0]表示a的個位，A[1]表示a的十位，依次類推。
將a乘以一個整數k變為將陣列A的每一個元素都乘以k，請注意處理相應的進位。
首先將a設為1，然後乘2，乘3，當乘到n時，即得到了n!的值。
輸入格式
輸入包含一個正整數n，n<=1000。
輸出格式
輸出n!的準確值。
樣例輸入
10
樣例輸出
3628800
特別注意n的規模
首先用遞迴只能解決1到幾百以內的階乘
def factorial(n):
if n == 1:
return n
else:
return n * factorial(n-1)
n = int(input())
result = factorial(n)
print(result)
這種遞迴方式1000的階乘是算不了的！
去網上查詢到了一個用陣列處理大數階乘的思想方法，跟題目要求的一樣，用Python寫了一下，提交後執行超時？！
n = int(input())
a = [0 for i in range(10000)]
a[0] = length = 1
for i in range(2, n + 1):
carry = 0
for j in range(length):
temp = a[j] * i + carry
carry = int(temp / 10)
a[j] = temp % 10
while carry > 0:
a[length] += carry % 10
length += 1
carry = int(carry / 10)
while length > 0:
length -= 1
print(a[length], end='')
真。。。。
然後用最簡單的連乘計算，發現提交過了，100分，emmmmmmm…
程式碼如此簡單
n = int(input())
a = s =1
while a <= n:
s = s * a
a += 1
print(s)
看來有時候想的太多也不見得是一種好事啊！
2.15 長整數加法
問題描述
輸入兩個整數a和b，輸出這兩個整數的和。a和b都不超過100位。
演演算法描述
由於a和b都比較大，所以不能直接使用語言中的標準資料型別來儲存。對於這種問題，一般使用陣列來處理。
定義一個陣列A，A[0]用於儲存a的個位，A[1]用於儲存a的十位，依此類推。同樣可以用一個陣列B來儲存b。
計算c = a + b的時候，首先將A[0]與B[0]相加，如果有進位產生，則把進位（即和的十位數）存入r，把和的個位數存入C[0]，即C[0]等於(A[0]+B[0])%10。然後計算A[1]與B[1]相加，這時還應將低位進上來的值r也加起來，即C[1]應該是A[1]、B[1]和r三個數的和．如果又有進位產生，則仍可將新的進位存入到r中，和的個位存到C[1]中。依此類推，即可求出C的所有位。
最後將C輸出即可。
輸入格式
輸入包括兩行，第一行為一個非負整數a，第二行為一個非負整數b。兩個整數都不超過100位，兩數的最高位都不是0。
輸出格式
輸出一行，表示a + b的值。
樣例輸入
20100122201001221234567890
2010012220100122
樣例輸出
20100122203011233454668012
def change_length(arr, l):
"""此方法使兩字串長度相等"""
arr = '0' * (l - len(arr)) + arr
return arr
arr = input()
arr_2 = input()
# 兩數長度若不等，短的數加前導0
if len(arr) > len(arr_2):
arr_2 = change_length(arr_2, len(arr))
elif len(arr) < len(arr_2):
arr = change_length(arr, len(arr_2))
result = [0 for i in range(len(arr) + 1)] # 結果最多是最長數的長度加1
k = 0 # 進位
for i in range(len(arr)):
rs = k + int(arr[len(arr) - i - 1]) + int(arr_2[len(arr_2) - i - 1]) # 從個位開始加，同時加上進位
result[len(arr) - i] = rs % 10
k = 0
if rs >= 10:
k = int(rs / 10)
if k != 0: # k != 0 則最高位為k
result[0] = k
for i in range(len(result) - 1):
print(result[i], end='')
print(result[-1])
else: # 否則最高為為0不輸出
for i in range(len(result) - 2):
print(result[i+1], end='')
print(result[-1])
2.16 哈夫曼樹
問題描述
Huffman樹在編碼中有著廣泛的應用。在這裡，我們只關心Huffman樹的構造過程。
給出一列數{pi}={p0, p1, …, pn-1}，用這列數構造Huffman樹的過程如下：
1. 找到{pi}中最小的兩個數，設為pa和pb，將pa和pb從{pi}中刪除掉，然後將它們的和加入到{pi}中。這個過程的費用記為pa + pb。
2. 重複步驟1，直到{pi}中只剩下一個數。
在上面的操作過程中，把所有的費用相加，就得到了構造Huffman樹的總費用。
本題任務：對於給定的一個數列，現在請你求出用該數列構造Huffman樹的總費用。
例如，對於數列{pi}={5, 3, 8, 2, 9}，Huffman樹的構造過程如下：
1. 找到{5, 3, 8, 2, 9}中最小的兩個數，分別是2和3，從{pi}中刪除它們並將和5加入，得到{5, 8, 9, 5}，費用為5。
2. 找到{5, 8, 9, 5}中最小的兩個數，分別是5和5，從{pi}中刪除它們並將和10加入，得到{8, 9, 10}，費用為10。
3. 找到{8, 9, 10}中最小的兩個數，分別是8和9，從{pi}中刪除它們並將和17加入，得到{10, 17}，費用為17。
4. 找到{10, 17}中最小的兩個數，分別是10和17，從{pi}中刪除它們並將和27加入，得到{27}，費用為27。
5. 現在，數列中只剩下一個數27，構造過程結束，總費用為5+10+17+27=59。
輸入格式
輸入的第一行包含一個正整數n（n<=100）。
接下來是n個正整數，表示p0, p1, …, pn-1，每個數不超過1000。
輸出格式
輸出用這些數構造Huffman樹的總費用。
樣例輸入
5
5 3 8 2 9
樣例輸出
59
n = int(input())
arr = list(map(int, input().split()))
price = [0 for i in range(n - 1)]
for i in range(n - 1):
arr.sort()
# print(arr)
value = arr.pop(0)
value_2 = arr.pop(0)
price[i] = value + value_2
arr.append(price[i])
print(sum(price))
2.17 N皇后問題
要在n*n的國際象棋棋盤中放n個皇后，使任意兩個皇后都不能互相吃掉。規則：皇后能吃掉同一行、同一列、同一對角線的任意棋子。求所有的解。n=8是就是著名的八皇后問題了。
def queen(A, cur=0):
# 遞迴回溯思想解決n皇后問題
if cur == len(A): # 所有的皇后都正確放置完畢，輸出每個皇后所在的位置
print(A)
return 0
for col in range(len(A)):
A[cur], flag = col, True
for row in range(cur): # 檢測本次所放皇后的位置是否在同行同列或同一對角線上
if A[row] == col or abs(col - A[row]) == cur - row: # 是的話，該位置不能放，向上回溯
flag = False
break
if flag: # 否的話，繼續放下一個皇后
queen(A, cur+1)
n = int(input()) # n為8，就是著名的八皇后問題啦
queen([None] * n)
2.18 報時助手
問題描述
給定當前的時間，請用英文的讀法將它讀出來。
時間用時h和分m表示，在英文的讀法中，讀一個時間的方法是：
如果m為0，則將時讀出來，然後加上「o’clock」，如3:00讀作「three o’clock」。
如果m不為0，則將時讀出來，然後將分讀出來，如5:30讀作「five thirty」。
時和分的讀法使用的是英文數位的讀法，其中0~20讀作：
0:zero, 1: one, 2:two, 3:three, 4:four, 5:five, 6:six, 7:seven, 8:eight, 9:nine, 10:ten, 11:eleven, 12:twelve, 13:thirteen, 14:fourteen, 15:fifteen, 16:sixteen, 17:seventeen, 18:eighteen, 19:nineteen, 20:twenty。
30讀作thirty，40讀作forty，50讀作fifty。
對於大於20小於60的數位，首先讀整十的數，然後再加上個位數。如31首先讀30再加1的讀法，讀作「thirty one」。
按上面的規則21:54讀作「twenty one fifty four」，9:07讀作「nine seven」，0:15讀作「zero fifteen」。
輸入格式
輸入包含兩個非負整數h和m，表示時間的時和分。非零的數位前沒有前導0。h小於24，m小於60。
輸出格式
輸出時間時刻的英文。
樣例輸入
0 15
樣例輸出
zero fifteen
h, m = map(int, input().split())
time = {0: 'zero', 1: 'one', 2: 'two', 3: 'three', 4: 'four', 5: 'five', 6: 'six', 7: 'seven', 8: 'eight', 9: 'nine',
10: 'ten', 11: 'eleven', 12: 'twelve', 13: 'thirteen', 14: 'fourteen', 15: 'fifteen', 16: 'sixteen',
17: 'seventeen', 18: 'eighteen', 19: 'nineteen', 20: 'twenty', 21: 'twenty one', 22: 'twenty two',
23: 'twenty three', 30: 'thirty', 40: 'forty', 50: 'fifty'}
# 其實21，22，23可以不加入字典中，但為了後邊小時略去判斷簡化程式碼，直接加在字典中，方便後邊直接輸出小時
if m == 0:
print(time[h] + ' o\'clock')
else:
print(time[h], end=' ')
if 0 < m <= 20 or m == 30 or m == 40 or m == 50:
print(time[m])
elif 20 < m < 30:
print(time[20] + ' ' + time[m - 20])
elif 30 < m < 40:
print(time[30] + ' ' + time[m - 30])
elif 40 < m < 50:
print(time[40] + ' ' + time[m - 40])
else:
print(time[50] + ' ' + time[m - 50])
2.19 回形取數
問題描述
回形取數就是沿矩陣的邊取數，若當前方向上無數可取或已經取過，則左轉90度。一開始位於矩陣左上角，方向向下。
輸入格式
輸入第一行是兩個不超過200的正整數m, n，表示矩陣的行和列。接下來m行每行n個整數，表示這個矩陣。
輸出格式
輸出只有一行，共mn個數，為輸入矩陣回形取數得到的結果。數之間用一個空格分隔，行末不要有多餘的空格。
樣例輸入
3 3
1 2 3
4 5 6
7 8 9
樣例輸出
1 4 7 8 9 6 3 2 5
樣例輸入
3 2
1 2
3 4
5 6
樣例輸出
1 3 5 6 4 2
注意
行末要求不要有多餘的空格，不知意思是一個空格也不能有還是隻可以有一個空格，由於控制最後一個數的輸出很麻煩，這裡博主在行末輸出了一個空格，提交藍橋系統100分通過
另外，讀者們可以嘗試去尋找最後一個數的輸出位置規律，使得最後一個數單獨輸出，這樣就無空格啦，這裡博主有時間的話回去再嘗試，然後會發出相應程式碼，敬請期待。
m, n = map(int, input().split())
row = col = count = 0
matrix = [[] for _ in range(m)]
for i in range(m):
arr = input().split()
for j in range(n):
matrix[i].append(int(arr[j]))
while count < m * n: # 總共m*n個數
while row < m and matrix[row][col] != -1: # 向下取數
print(matrix[row][col], end=' ')
matrix[row][col] = -1 # 將去過的位置置為-1
row += 1
count += 1
row -= 1 # 上個迴圈結束後row的值為m,需要減1，否則越界
col += 1 # 列值加1，因為第零列在上個迴圈已經輸出，往右推一行
while col < n and matrix[row][col] != -1: # 向右取數
print(matrix[row][col], end=' ')
matrix[row][col] = -1 # 將去過的位置置為-1
col += 1
count += 1
row -= 1 # 往上推一行
col -= 1 # 上個迴圈使列值為n
while row >= 0 and matrix[row][col] != -1: # 向上取數
print(matrix[row][col], end=' ')
matrix[row][col] = -1 # 將去過的位置置為-1
row -= 1
count += 1
row += 1 # 上個迴圈使行值為-1
col -= 1 # 往左推一行
while col >= 0 and matrix[row][col] != -1: # 向左取數
print(matrix[row][col], end=' ')
matrix[row][col] = -1 # 將去過的位置置為-1
col -= 1
count += 1
col += 1 # 上個迴圈使列值為-1
row += 1 # 向下推一行
2.20 龜兔賽跑預測
問題描述
話說這個世界上有各種各樣的兔子和烏龜，但是研究發現，所有的兔子和烏龜都有一個共同的特點——喜歡賽跑。於是世界上各個角落都不斷在發生著烏龜和兔子的比賽，小華對此很感興趣，於是決定研究不同兔子和烏龜的賽跑。他發現，兔子雖然跑比烏龜快，但它們有眾所周知的毛病——驕傲且懶惰，於是在與烏龜的比賽中，一旦任一秒結束後兔子發現自己領先t米或以上，它們就會停下來休息s秒。對於不同的兔子，t，s的數值是不同的，但是所有的烏龜卻是一致——它們不到終點決不停止。
然而有些比賽相當漫長，全程觀看會耗費大量時間，而小華髮現只要在每場比賽開始後記錄下兔子和烏龜的資料——兔子的速度v1（表示每秒兔子能跑v1米），烏龜的速度v2，以及兔子對應的t，s值，以及賽道的長度l——就能預測出比賽的結果。但是小華很懶，不想通過手工計算推測出比賽的結果，於是他找到了你——清華大學計算機系的高才生——請求幫助，請你寫一個程式，對於輸入的一場比賽的資料v1，v2，t，s，l，預測該場比賽的結果。
輸入格式
輸入只有一行，包含用空格隔開的五個正整數v1，v2，t，s，l，其中(v1,v2<=100;t<=300;s<=10;l<=10000且為v1,v2的公倍數)
輸出格式
輸出包含兩行，第一行輸出比賽結果——一個大寫字母「T」或「R」或「D」，分別表示烏龜獲勝，兔子獲勝，或者兩者同時到達終點。
第二行輸出一個正整數，表示獲勝者（或者雙方同時）到達終點所耗費的時間（秒數）。
樣例輸入
10 5 5 2 20
樣例輸出
D
4
樣例輸入
10 5 5 1 20
樣例輸出
R
3
樣例輸入
10 5 5 3 20
樣例輸出
T
4
data = list(map(int, input().split()))
rabbit = tortoise = time = 0
flag = False
while True:
if rabbit == data[-1] or tortoise == data[-1]: # 如果兔子或烏龜到達終點，結束
break
if rabbit - tortoise >= data[2]: # 兔子達到領先條件，休息
for i in range(data[3]): # 休息時間按秒增加，烏龜路程按秒增加
tortoise += data[1]
time += 1
if tortoise == data[-1]: # 兔子休息時，烏龜到達了終點，結束。
# 注意：有可能兔子在休息中，烏龜就到達了終點
# 所以休息時間未必迴圈完
# 如：兔子要休息10s，烏龜可能在兔子休息的第9s就到達了終點
# 這裡的flag就起到提前結束的功能
flag = True
break
if flag: # 如果提前結束，則全部結束
break
time += 1 # 每走一秒，兔子和烏龜按相應速度增加相應距離
rabbit += data[0]
tortoise += data[1]
if rabbit > tortoise: # 誰先到達終點，誰的距離大
print('R')
print(time)
elif rabbit < tortoise:
print('T')
print(time)
else: # 相等則平局
print('D')
print(time)
2.21 晶片測試
問題描述
有n（2≤n≤20）塊晶片，有好有壞，已知好晶片比壞晶片多。
每個晶片都能用來測試其他晶片。用好晶片測試其他晶片時，能正確給出被測試晶片是好還是壞。而用壞晶片測試其他晶片時，會隨機給出好或是壞的測試結果（即此結果與被測試晶片實際的好壞無關）。
給出所有晶片的測試結果，問哪些晶片是好晶片。
輸入格式
輸入資料第一行為一個整數n，表示晶片個數。
第二行到第n+1行為n*n的一張表，每行n個資料。表中的每個資料為0或1，在這n行中的第i行第j列（1≤i, j≤n）的資料表示用第i塊晶片測試第j塊晶片時得到的測試結果，1表示好，0表示壞，i=j時一律為1（並不表示該晶片對本身的測試結果。晶片不能對本身進行測試）。
輸出格式
按從小到大的順序輸出所有好晶片的編號
樣例輸入
3
1 0 1
0 1 0
1 0 1
樣例輸出
1 3
解題思路：
重點是好晶片比壞晶片多
如果忽略這個問題就很難解決，本人開始你就不幸忽略了。。。
既然好晶片比壞晶片多，那麼我們只需記錄每一列0的個數就行了，若個數超過n/2，則此晶片為壞晶片
一個chip列表來記錄晶片的好壞
n = int(input())
arr = [[] for _ in range(n)]
chip = [True for _ in range(n)]
for i in range(n):
arr_ = input().split()
for j in range(n):
arr[i].append(int(arr_[j]))
for i in range(n):
count = 0
for j in range(n):
if arr[j][i] == 0:
count += 1
if count > n / 2:
chip[i] = False
for i in range(n):
if chip[i]:
print(i + 1, end=' ')
2.22 FJ字串
問題描述
FJ在沙盤上寫了這樣一些字串：
A1 = 「A」
A2 = 「ABA」
A3 = 「ABACABA」
A4 = 「ABACABADABACABA」
… …
你能找出其中的規律並寫所有的數列AN嗎？
輸入格式
僅有一個數：N ≤ 26。
輸出格式
請輸出相應的字串AN，以一個換行符結束。輸出中不得含有多餘的空格或換行、回車符。
樣例輸入
3
樣例輸出
ABACABA
n = int(input())
str_n = ''
for i in range(n):
str_n = str_n + chr(ord('A') + i) + str_n
print(str_n)
2.23 sin之舞
問題描述
最近FJ為他的奶牛們開設了數學分析課，FJ知道若要學好這門課，必須有一個好的三角函數基本功。所以他準備和奶牛們做一個「Sine之舞」的遊戲，寓教於樂，提高奶牛們的計算能力。
不妨設
An=sin(1–sin(2+sin(3–sin(4+…sin(n))…)
Sn=(…(A1+n)A2+n-1)A3+…+2)An+1
FJ想讓奶牛們計算Sn的值，請你幫助FJ列印出Sn的完整表示式，以方便奶牛們做題。
輸入格式
僅有一個數：N<201。
輸出格式
請輸出相應的表示式Sn，以一個換行符結束。輸出中不得含有多餘的空格或換行、回車符。
樣例輸入
3
樣例輸出
((sin(1)+3)sin(1–sin(2))+2)sin(1–sin(2+sin(3)))+1
解題思路：
這裡主要運用到遞迴的思想
先遞迴求An
然後求Sn
Sn通用過呼叫An求出
def A(n, k):
if n == k:
return
print('sin(%d' % (n + 1), end='')
if n + 1 != k: # 若後邊還有式子，判斷是輸出+號還是-號
if n % 2 == 1:
print('+', end='')
else:
print('-', end='')
else: # 若後邊沒有式子，輸出右括號結束
# 注意，這裡只輸出最後一次的右括號，前邊左括號對應的右括號在S()函數中補全
print(')', end='')
n += 1
A(n, k) # 遞迴呼叫自身
def S(n):
k = t = 1
if n == 0:
return
for i in range(n - 1):
print('(', end='')
while n != 0:
A(0, k)
for i in range(t - 1): # 不全A()函數中的括號
print(')', end='')
print('+%d' % n, end='')
if n != 1: # 最後一項加完整數之和不必再輸出右括號
print(')', end='')
k += 1
t += 1
n -= 1
n = int(input())
# A(0, 3)
S(n)
2.24 數的讀法
問題描述
Tom教授正在給研究生講授一門關於基因的課程，有一件事情讓他頗為頭疼：一條染色體上有成千上萬個鹼基對，它們從0開始編號，到幾百萬，幾千萬，甚至上億。
比如說，在對學生講解第1234567009號位置上的鹼基時，光看著數位是很難準確的念出來的。
所以，他迫切地需要一個系統，然後當他輸入12 3456 7009時，會給出相應的念法：
十二億三千四百五十六萬七千零九
用漢語拼音表示為
shi er yi san qian si bai wu shi liu wan qi qian ling jiu
這樣他只需要照著念就可以了。
你的任務是幫他設計這樣一個系統：給定一個阿拉伯數位串，你幫他按照中文讀寫的規範轉為漢語拼音字串，相鄰的兩個音節用一個空格符格開。
注意必須嚴格按照規範，比如說「10010」讀作「yi wan ling yi shi」而不是「yi wan ling shi」，「100000」讀作「shi wan」而不是「yi shi wan」，「2000」讀作「er qian」而不是「liang qian」。
輸入格式
有一個數位串，數值大小不超過2,000,000,000。
輸出格式
是一個由小寫英文字母，逗號和空格組成的字串，表示該數的英文讀法。
樣例輸入
1234567009
樣例輸出
shi er yi san qian si bai wu shi liu wan qi qian ling jiu
解題思路：
開始我按位元置一位一位讀，讀到1萬程式碼就開始很複雜了，所以考慮一定有相應讀法的規律
利用迴圈來搞定，苦思冥想之後，還是利用度娘，一下就清晰了。。。
首先，讀一個數，要處理開頭為1的位置要不要讀的問題
其次就是，處理多個連續0的讀法問題
處理1的程式碼塊下方已註釋
就是不要把11，讀作yi shi yi,111111不要讀作yi shi yi wan yi qian yi bai yi shi yi
處理0的連續問題程式碼塊中也給與了註釋
就是10001不要讀作yi wan ling ling ling ling yi,而是yi wan ling yi
參考以下程式碼
n = input()
pin_yin = {'0': 'ling', '1': 'yi', '2': 'er', '3': 'san', '4': 'si', '5': 'wu',
'6': 'liu', '7': 'qi', '8': 'ba', '9': 'jiu'}
pin_yin_2 = {0: '', 1: '', 2: 'shi', 3: 'bai', 4: 'qian', 5: 'wan', 6: 'shi',
7: 'bai', 8: 'qian', 9: 'yi', 10: 'shi'}
n = n + ' '
l = len(n) - 1
for i in range(l):
j = int(n[i])
if j != 0: # 不為0時的讀法
if (l - i == 2 or l - i == 6 or l - i == 10) and j == 1:
# 在十位，十萬位，十億位置且位於開頭的1不讀
# 例子：
# 1111111111 會讀出 yi shi yi yi yi qian yi bai yi shi yi wan yi qian yi bai yi shi yi
# 111111 會讀出 yi shi yi wan yi qian yi bai yi shi yi
# 11 會讀出 yi shi yi
# 加上此約束後，則不會讀出開頭的 yi
if i != 0: # 第一個1不輸出1， 若不新增此條件，12會讀出 yi shi er
print(pin_yin['1'], end=' ')
print(pin_yin_2[2], end=' ')
continue
print(pin_yin[n[i]], end=' ')
print(pin_yin_2[l - i], end=' ')
else: # 處理0的讀法問題
if l - i == 5 or l - i == 9: # 如果此0是在萬位或億位，則讀出萬或億
print(pin_yin_2[l - i], end=' ')
if n[i + 1] == '0' or i == l - 1: # 如果後一位仍然為0，或者，當前是最後以為，則不讀此0
continue
print(pin_yin['0'], end=' ') # 否則才讀出這個零
2.25 完美的代價
問題描述
迴文串，是一種特殊的字串，它從左往右讀和從右往左讀是一樣的。小龍龍認為迴文串才是完美的。現在給你一個串，它不一定是迴文的，請你計算最少的交換次數使得該串變成一個完美的迴文串。
交換的定義是：交換兩個相鄰的字元
例如mamad
第一次交換 ad : mamda
第二次交換 md : madma
第三次交換 ma : madam (迴文！完美！)
輸入格式
第一行是一個整數N，表示接下來的字串的長度(N <= 8000)
第二行是一個字串，長度為N.只包含小寫字母
輸出格式
如果可能，輸出最少的交換次數。
否則輸出Impossible
樣例輸入
5
mamad
樣例輸出
3
解題思路
兩種情況：
1.impossible的情況：如果有一個字元出現的次數是奇數次數，而且n是偶數，那麼不可能構成迴文。
如果n是奇數，但是已經有一個字元出現的次數是奇數次數了，那麼如果又有一個字元是奇數次數，就不可能構成迴文。
2.如果n是奇數，計算中間那個字元交換的次數的時候，不需要模擬把這個數移動到中間去，因為移動到中間的話假設有一對數都在左邊或者都在右邊。那麼交換成迴文的時候就要經過中間，就會每次把cnt多加了1，而這個1是沒有必要的，因為可以所有的迴文移動完了之後再把這個獨立的奇數移動過去，才能保證交換次數最少。
例如：
此圖片參照自部落格：qq_40605470
n = int(input())
pal = list(input())
count = flag = 0 # count計數，flag判斷是否已經有一個單獨的奇個數的字元了
m = n - 1
for i in range(m): # 從頭遍歷到倒數第二個字元
for k in range(m, i - 1, -1): # 從後面往前一直到i尋找和pal[i]相同的pal[k]
if k == i: # 如果找不到相同的
if n % 2 == 0 or flag == 1: # impossible的兩種情況
print('Impossible')
exit()
flag = 1
count += int(n / 2) - i
elif pal[k] == pal[i]:
for j in range(k, m): # 找到相同的，進行交換
pal[j], pal[j + 1] = pal[j + 1], pal[j]
count += 1 # 計數器加1
m -= 1 # 最後拍好序的不在進行比較
break
print(count)
這個出現了之前遇到同樣的問題，提交後十組測試資料，九組正確，但是有一組超時，不得分。但是同樣的演演算法，C++版本的程式碼提交後完美通過，100分！目前不知道怎麼辦還，有明白的請不吝賜教，非常感謝。
C++版程式碼如下：
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
string s;
cin >> s;
int j = n - 1;
int cnt = 0;//cnt用來統計交換的次數
int flag = 0;//flag判斷是否已經有一個單獨的奇個數的字元了
for(int i = 0; i < j; i++) {//i指標從頭遍歷到倒數第二個字元
for(int k = j; k >= i; k--) {//k指標從後面往前一直到i尋找和s[i]相同的s[k]
if(k == i) {//如果找不到相同的
if(n % 2 == 0 || flag == 1) {//impossible的兩種情況
cout << "Impossible";
return 0;
}
flag = 1;
cnt += n / 2 - i;
} else if(s[k] == s[i]) {
for(int l = k; l < j; l++) {
swap(s[l], s[l+1]);//把s[k]換到s[j]處
cnt++;//統計交換次數
}
j--;
break;
}
}
}
cout << cnt;
return 0;
}
注：此程式碼完美通過！
2.26 矩形面積交
問題描述
平面上有兩個矩形，它們的邊平行於直角座標系的X軸或Y軸。對於每個矩形，我們給出它的一對相對頂點的座標，請你程式設計算出兩個矩形的交的面積。
輸入格式
輸入僅包含兩行，每行描述一個矩形。
在每行中，給出矩形的一對相對頂點的座標，每個點的座標都用兩個絕對值不超過10^7的實數表示。
輸出格式
輸出僅包含一個實數，為交的面積，保留到小數後兩位。
樣例輸入
1 1 3 3
2 2 4 4
樣例輸出
1.00
解題思路：
重點是找到兩個矩形產生交集的條件
矩陣1的對角點座標的橫座標取最小， 矩陣2的對角點座標的橫座標取最小，然後再從這兩個值中取最大，得x1
矩陣1的對角點座標的橫座標取最大， 矩陣2的對角點座標的橫座標取最大，然後再從這兩個值中取最小，得x2
如果x1<x2，這兩個矩形才會有交集
縱座標同理
最後交集的面積就為：
area = (x2 - x1) * (y2 - y1)
rect_1 = list(map(float, input().split()))
rect_2 = list(map(float, input().split()))
area = 0
x1 = max(min(rect_1[0], rect_1[2]), min(rect_2[0], rect_2[2]))
y1 = max(min(rect_1[1], rect_1[3]), min(rect_2[1], rect_2[3]))
x2 = min(max(rect_1[0], rect_1[2]), max(rect_2[0], rect_2[2]))
y2 = min(max(rect_1[1], rect_1[3]), max(rect_2[1], rect_2[3]))
if x1 < x2 and y1 < y2:
area = (x2 - x1) * (y2 - y1)
print('%.2f' % area)
else:
print('%.2f' % area)
2.27 矩陣乘法
問題描述
給定一個N階矩陣A，輸出A的M次冪（M是非負整數）
例如：
A =
1 2
3 4
A的2次冪
7 10
15 22
輸入格式
第一行是一個正整數N、M（1<=N<=30, 0<=M<=5），表示矩陣A的階數和要求的冪數
接下來N行，每行N個絕對值不超過10的非負整數，描述矩陣A的值
輸出格式
輸出共N行，每行N個整數，表示A的M次冪所對應的矩陣。相鄰的數之間用一個空格隔開
樣例輸入
2 2
1 2
3 4
樣例輸出
7 10
15 22
注意：
1.不要忘記方陣的0次冪這一特殊情況，它的結果是人為定義的，為n階單位陣。
2.博主的程式碼中矩陣乘法函數，是一個普遍適用的矩陣乘法函數，即不是兩個方陣相乘也行，只要兩矩陣滿足矩陣乘法定理即可，相應解釋已在程式碼塊中給出。
3.若你在參加考試，則程式碼越簡化越好，如這題的矩陣乘法函數，題中給的輸入矩陣必為n階方陣，所以寫矩陣乘法的函數就只針對n階方陣來寫就好了，以降低出錯率，相應程式碼請讀者自行寫出，以加深理解。
def multi_rect(rect_1, shape_1, rect_2, shape_2):
"""矩陣乘法
:param rect_1: 矩陣A
:param shape_1: 矩陣A的形狀
:param rect_2: 矩陣B
:param shape_2: 矩陣B的形狀
:return: 兩矩陣之積和積的矩陣形狀
"""
if shape_1[1] != shape_2[0]:
return
rect_ = [[0 for _ in range(shape_2[1])] for _ in range(shape_1[0])]
shape_ = (shape_1[0], shape_2[1])
for i in range(shape_1[0]):
for k in range(shape_2[1]):
for j in range(shape_1[1]):
rect_[i][k] += rect_1[i][j] * rect_2[j][k] # 矩陣乘法定義
return rect_, shape_
n, m = map(int, input().split())
rect = [[] for _ in range(n)]
for i in range(n):
arr = input().split()
for j in range(n):
rect[i].append(int(arr[j]))
result, shape = rect, (n, n)
if m == 0: # 0次冪只有為方陣才有，此時result為n階單位陣
result = [[0 for _ in range(n)] for _ in range(n)] # shape仍然為(n, n)
for i in range(n):
result[i][i] = 1
else: # m不為0，計算它的m次冪
for _ in range(m - 1):
result, shape = multi_rect(rect, (n, n), result, shape)
for i in range(shape[0]):
for j in range(shape[1]):
print(result[i][j], end=' ')
print()
2.28 2n皇后問題
問題描述
給定一個n*n的棋盤，棋盤中有一些位置不能放皇后。現在要向棋盤中放入n個黑皇后和n個白皇后，使任意的兩個黑皇后都不在同一行、同一列或同一條對角線上，任意的兩個白皇后都不在同一行、同一列或同一條對角線上。問總共有多少种放法？n小於等於8。
輸入格式
輸入的第一行為一個整數n，表示棋盤的大小。
接下來n行，每行n個0或1的整數，如果一個整數為1，表示對應的位置可以放皇后，如果一個整數為0，表示對應的位置不可以放皇后。
輸出格式
輸出一個整數，表示總共有多少种放法。
樣例輸入
4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
樣例輸出
2
樣例輸入
4
1 0 1 1
1 1 1 1
1 1 1 1
1 1 1 1
樣例輸出
0
前面2.17簡單介紹了N皇后問題，這裡的題目為2n皇后問題，就是先放置好白皇后，然後再不衝突的情況下按上述規則放置黑皇后
例2.17是網上給出的python版經典求解N皇后問題演演算法，此處作者自己查閱資料寫了個N皇后問題程式碼，下方貼出，因為2n皇后問題求解是在此基礎上求解的。
def n_queen(k):
global count
for i in range(k - 1): # 判斷是否可放置皇后的條件
judge = queen[i] - queen[k - 1]
if judge == 0 or abs(k - 1 - i) == abs(judge):
return
if k == n:
print(queen) # 輸出皇后放置序列
count += 1 # 解的個數
return
for i in range(n): # 放置皇后
queen[k] = i
n_queen(k + 1)
count = 0
n = 4 # 此處的n為幾，則為幾皇后問題
queen = [0 for _ in range(n)]
n_queen(0)
print(count)
下面給出2n皇后問題解的python程式碼，但是提交後十組測試資料有九組通過，一組執行超時，但結果也是正確的，同意的程式碼思想，改編為C語言版就能通過，而不會提示執行超時，這個問題遇到過不止一次了，一直不知道怎麼解決，是在重新設計一個更快的演演算法才行嗎，很苦惱。
同樣演演算法思想寫出的程式碼，python執行時間會比C,C++的執行時間長，從而導致提交python程式碼後結果為執行超時，而其他程式碼則完美通過。
python程式碼，得分83分，有一組資料執行超時。
def black_queen(k):
global count
for i in range(k - 1):
judge = b_queen[i] - b_queen[k - 1]
if judge == 0 or abs(k - 1 - i) == abs(judge):
return
if k == n:
count += 1
return
for i in range(n):
if i != w_queen[k] and chessboard[k][i] == 1:
b_queen[k] = i
black_queen(k + 1)
def white_queen(k):
for i in range(k - 1):
judge = w_queen[i] - w_queen[k - 1]
if judge == 0 or abs(k - 1 - i) == abs(judge):
return
if k == n:
black_queen(0)
return
for i in range(n):
if chessboard[k][i] == 1:
w_queen[k] = i
white_queen(k + 1)
n = int(input())
count = 0
chessboard = [[] for _ in range(n)]
for i in range(n):
arr = input().split()
for j in range(n):
chessboard[i].append(int(arr[j]))
w_queen = [0 for _ in range(n)]
b_queen = [0 for _ in range(n)]
white_queen(0)
print(count)
C語言程式碼，100分。
#include<stdio.h>
#include<string.h>
#include<math.h>
#define MAXSIZE 1000
int bqueen[MAXSIZE];//黑皇后
int wqueen[MAXSIZE];//白皇后
int chessboard[MAXSIZE][MAXSIZE];//1:能放 0:不能放
int count =0;
int n;
int BlackQueen(int k)
{
int i;
int j;
for(i =0; i < k -1; i++)
{
int judge = bqueen[i]- bqueen[k -1];
if(judge ==0|| fabs(k -1- i)== fabs(judge))
return 0;
}
if(k == n)
{
count++;
return 0;
}
for( j =0; j < n; j++)
{
if(j != wqueen[k]&& chessboard[k][j])
{
bqueen[k]= j;
BlackQueen(k +1);
}
}
}
int WhiteQueen(int k)
{
int i;
int j;
for( i =0; i < k -1; i++)
{
int judge = wqueen[i]- wqueen[k -1];
if(judge ==0|| fabs(k -1- i)== fabs(judge))
return 0;
}
if(k == n)
{
BlackQueen(0);
return 0;
}
for( j =0; j < n; j++)
{
if(chessboard[k][j])
{
wqueen[k]= j;
WhiteQueen(k +1);
}
}
}
int main(void)
{ int i;
int j;
// freopen("input3.txt","r",stdin);//這是我直接從檔案中讀取資料
scanf("%d",&n);
for(i =0; i < n; i++)
for(j =0; j < n; j++)
scanf("%d",&chessboard[i][j]);
WhiteQueen(0);
printf("%d\n",count);
return 0;
}
2.29 分解質因數
問題描述
求出區間[a,b]中所有整數的質因數分解。
輸入格式
輸入兩個整數a，b。
輸出格式
每行輸出一個數的分解，形如k=a1a2a3…(a1<=a2<=a3…，k也是從小到大的)(具體可看樣例)
樣例輸入
3 10
樣例輸出
3=3
4=22
5=5
6=23
7=7
8=222
9=33
10=25
提示
先篩出所有素數，然後再分解。
資料規模和約定
2<=a<=b<=10000
解題思路：
對一個數進行質因數分解
首先判斷它本身是否為質數
是，則直接輸出等於自身
否，進行迴圈，從2開始，輸出最多的因數個數後才遞增，這樣保證不會有非質數因子
如，8 = 2 * 2 * 2
首先把最多的2輸出，之後就不會出現2的倍數這樣的因數啦。
又出現了同樣的問題，python程式碼超時，C程式碼執行100分！好煩哦~
python程式碼
def is_prime(n):
for i in range(2, n):
if n % i == 0:
return False
return True
a, b = map(int, input().split())
for i in range(a, b + 1):
if is_prime(i): # 如果是素數，則等於它本身
print(i, '=', i, sep='')
else:
print(i, '=', sep='', end='')
temp = i
j = 2
while temp > 1:
if temp % j == 0: # 分解質因數，從j=2開始除,直到對i取餘不為0時，才j += 1，保證每個j出現最多
temp = int(temp / j)
print(j, end='')
if temp != 1:
print('*', end='')
else:
j += 1
print()
C語言程式碼
#include<iostream>
using namespace std;
bool issu(int n){ //判斷素數
bool t = true;
for(int i = 2;i <= n - 1;i++){
if(n % i == 0){
t = false;
break;
}
}
return t;
}
int main(){
int a;
int b;
cin>>a>>b;
for(int i = a;i <= b;i++){
if(issu(i)){
cout<<i<<"="<<i<<endl;
}else{
cout<<i<<"=";
int tt = i;
int j = 2;
while(tt > 1){ //分解質因數，從i=2開始除,直到對i取餘不為0時，才i++
// 保證每個i出現最多
if(tt % j == 0){
tt = tt / j;
cout<<j;
if(tt != 1){
cout<<"*";
}
}else{
j++;
}
}
cout<<endl;
}
}
return 0;
}
2.30 字串對比
問題描述
給定兩個僅由大寫字母或小寫字母組成的字串(長度介於1到10之間)，它們之間的關係是以下4中情況之一：
1：兩個字串長度不等。比如 Beijing 和 Hebei
2：兩個字串不僅長度相等，而且相應位置上的字元完全一致(區分大小寫)，比如 Beijing 和 Beijing
3：兩個字串長度相等，相應位置上的字元僅在不區分大小寫的前提下才能達到完全一致（也就是說，它並不滿足情況2）。比如 beijing 和 BEIjing
4：兩個字串長度相等，但是即使是不區分大小寫也不能使這兩個字串一致。比如 Beijing 和 Nanjing
程式設計判斷輸入的兩個字串之間的關係屬於這四類中的哪一類，給出所屬的類的編號。
輸入格式
包括兩行，每行都是一個字串
輸出格式
僅有一個數位，表明這兩個字串的關係編號
樣例輸入
BEIjing
beiJing
樣例輸出
3
注意：
程式碼塊中的upper函數也可以改為lower函數
就是樣字串中的英文字母全部改為大寫或者小寫
str_1 = input()
str_2 = input()
if len(str_1) != len(str_2):
print(1)
elif str_1 == str_2:
print(2)
elif str_1.upper() == str_2.upper():
print(3)
else:
print(4)
參考知識：
2.31 時間轉換
問題描述
給定一個以秒為單位的時間t，要求用H:M:S的格式來表示這個時間。H表示時間，M表示分鐘，而S表示秒，它們都是整數且沒有前導的「0」。例如，若t=0，則應輸出是「0:0:0」；若t=3661，則輸出「1:1:1」。
輸入格式
輸入只有一行，是一個整數t（0<=t<=86399）。
輸出格式
輸出只有一行，是以「H:M:S」的格式所表示的時間，不包括引號。
樣例輸入
0
樣例輸出
0:0:0
樣例輸入
5436
樣例輸出
1:30:36
解題思路：
這道題目就是單純的把秒轉換成小時和分鐘，較為簡單，不再贅述。
n = int(input())
h = int(n / 3600)
m = int((n - h * 3600) / 60)
s = int(n - h * 3600 - m * 60)
print(h, ':', m, ':', s, sep='')
3.提高篇
3.1 預測身高
問題描述：
生理衛生老師在課堂上娓娓道來：
你能看見你未來的樣子嗎？顯然不能。但你能預測自己成年後的身高，有公式：
男孩成人後身高=（父親身高+母親身高）/21.08
女孩成人後身高=(父親身高0.923+母親身高）/2
數學老師聽見了，回頭說：這是大樣本統計擬合公式，準確性不錯。
生物老師聽見了，回頭說：結果不是絕對的，影響身高的因素很多，比如營養、疾病、體育鍛煉、睡眠、情緒、環境因素等。
老師們齊回頭，看見同學們都正在預測自己的身高。
毛老師見此情形，推推眼鏡說：何必手算，程式設計又快又簡單…
約定：
身高的單位用米表示，所以自然是會有小數的。
男性用整數1表示，女性用整數0表示。
預測的身高保留三位小數
輸入格式
用空格分開的三個數，整數 小數 小數
分別表示：性別 父親身高 母親身高
輸出格式
一個小數，表示根據上述表示預測的身高（保留三位小數）
樣例輸入
1 1.91 1.70
樣例輸出
1.949
樣例輸入
0 1.00 2.077
樣例輸出
1.500
資料規模和約定
父母身高範圍（0，3]
時間限制1.0秒
隨機從演演算法訓練裡抽取的一道題目，題幹挺長，但是讀完後發現太簡單啦，不想發出來侮辱大家智商。但是做都做啦，就更新一下吧。。。
gender, father_height, mother_height = map(float, input().split())
if gender == 1:
height = (father_height + mother_height) / 2 * 1.08
else:
height = (father_height * 0.923 + mother_height) / 2
print('%.3f' % height)
3.2 最長滑雪道
問題描述
小袁非常喜歡滑雪， 因為滑雪很刺激。為了獲得速度，滑的區域必須向下傾斜，而且當你滑到坡底，你不得不再次走上坡或者等待升降機來載你。 小袁想知道在某個區域中最長的一個滑坡。區域由一個二維陣列給出。陣列的每個數位代表點的高度。如下：
一個人可以從某個點滑向上下左右相鄰四個點之一，當且僅當高度減小。在上面的例子中，一條可滑行的滑坡為24-17-16-1。當然25-24-23-…-3-2-1更長。事實上，這是最長的一條。
你的任務就是找到最長的一條滑坡，並且將滑坡的長度輸出。 滑坡的長度定義為經過點的個數，例如滑坡24-17-16-1的長度是4。
輸入格式
輸入的第一行表示區域的行數R和列數C(1<=R, C<=10)。下面是R行，每行有C個整數，依次是每個點的高度h（0<= h <=10000）。
輸出格式
只有一行，為一個整數，即最長區域的長度。
樣例輸入
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
樣例輸出
25
解題思路：
1.偶然發現了一中二位陣列輸入的更簡便方式：
arr = [list(map(int, input().split())) for _ in range(row)]
以後按二維陣列的輸入統統按此方法處理，前邊已經寫好的程式碼不再進行修改。
2.對於區域內每個點進行dfs，對每個點來說進行四個方向的dfs取最大值，然後取所有點為起點的最大長度的最大值，即為答案。
3.詳細解釋在程式碼塊中相應位置給出。
def dfs(x, y):
"""
深度遞迴搜尋
:param x: 橫座標
:param y: 縱座標
:return: 最大距離
"""
max_height = 1 # 初始距離為1
if dp[x][y] > 0: # 如果已經有了當前位置出發的最大距離，則直接返回
return dp[x][y]
for k in range(4): # 判斷該位置的上下左右四個位置
tx = x + next_[k][0]
ty = y + next_[k][1]
if tx < 0 or tx >= row or ty < 0 or ty >= col: # 越界情況
continue
if arr[tx][ty] >= arr[x][y]: # 不符合高到低的情況
continue
max_height = max(max_height, dfs(tx, ty) + 1) # 符合，遞迴搜尋下一個位置且距離加1
dp[x][y] = max_height # 最終距離放在此矩陣中儲存
return dp[x][y] # 返回該位置下的最大距離
row, col = map(int, input().split())
dp = [[0 for _ in range(col)] for _ in range(row)] # 記錄從每個位置(x, y)開始，它的最大長度
arr = [list(map(int, input().split())) for _ in range(row)] # 這裡發明了二位陣列python輸入方法的一種全新方式，偶然發現的
next_ = [[0, 1], [1, 0], [0, -1], [-1, 0]] # 用來表示(x, y)的上下左右四個位置
ans = 0
for i in range(row):
for j in range(col):
ans = max(ans, dfs(i, j))
print(ans)
3.3 K好數
資源限制
時間限制：1.0s 記憶體限制：256.0MB
問題描述
如果一個自然數N的K進位製表示中任意的相鄰的兩位都不是相鄰的數位，那麼我們就說這個數是K好數。求L位K進位制數中K好數的數目。例如K = 4，L = 2的時候，所有K好數為11、13、20、22、30、31、33 共7個。由於這個數目很大，請你輸出它對1000000007取模後的值。
輸入格式
輸入包含兩個正整數，K和L。
輸出格式
輸出一個整數，表示答案對1000000007取模後的值。
樣例輸入
4 2
樣例輸出
7
資料規模與約定
對於30%的資料，KL <= 106；
對於50%的資料，K <= 16， L <= 10；
對於100%的資料，1 <= K,L <= 100。
動態規劃DP問題
「L位K進位制數」：如：「2位4進位制數」，它是指這個數是個兩位數，其中個位數是4進位制數（即從[0,3]中取一個數作為個位），十位數也是4進位制數。同理，「3位7進位制數」則指這個數是個3位數，其中個位、十位、百位都是7進位制數。
K好數的要求：任意相鄰的兩位不是相鄰的數位。
核心：dp[i][j]=dp[i][j]+dp[i-1][k]
當前位置的數總數=當前位置的數的數目+前一個位置的數的總數。
def count(length, kind, ans):
for i in range(1, kind):
dp[0][i] = 1
for i in range(1, length):
for j in range(kind):
for k in range(kind):
if abs(j - k) != 1:
if j - 1 == 0 and k == 0: # 排除首位為0的情況
continue
dp[i][j] = dp[i][j]+dp[i-1][k]
dp[i][j] %= MOD
for i in range(kind):
ans += dp[length - 1][i]
ans %= MOD
return ans
K, L = map(int, input().split())
ans = 0
MOD = 1000000007
dp = [[0 for _ in range(max(L,K))] for _ in range(max(L,K))]
if K == 1 and L == 1:
print(0)
elif K > 1 and L == 1: # 1位的K進位制的K好數總數就是K個
print(K)
elif L > 1:
print(count(L, K, ans))
3.4 石子游戲
資源限制
時間限制：1.0s 記憶體限制：256.0MB
問題描述
石子游戲的規則如下：
地上有n堆石子，每次操作可選取兩堆石子（石子個數分別為x和y）並將它們合併，操作的得分記為(x+1)×(y+1)，對地上的石子堆進行操作直到只剩下一堆石子時停止遊戲。
請問在整個遊戲過程中操作的總得分的最大值是多少？
輸入格式
輸入資料的第一行為整數n，表示地上的石子堆數；第二行至第n+1行是每堆石子的個數。
輸出格式
程式輸出一行，為遊戲總得分的最大值。
樣例輸入
10
5105
19400
27309
19892
27814
25129
19272
12517
25419
4053
樣例輸出
15212676150
資料規模和約定
1≤n≤1000，1≤一堆中石子數≤50000
每次取最大的，符合貪心原則
這裡直接排序，然後選取兩個前二大數
計算結果，合併，刪掉最後一個
列表長度不為1時迴圈
python的列表可以看作棧或佇列
n = int(input())
result = 0
data = [int(input()) for _ in range(n)]
while len(data) != 1:
data.sort()
result += (data[-1] + 1) * (data[-2] + 1)
data[-2] += data[-1]
data.pop(-1)
print(result)
3.5 幸運顧客
資源限制
時間限制：2.0s 記憶體限制：256.0MB
為了吸引更多的顧客，某商場決定推行有獎抽彩活動。「本商場每日將產生一名幸運顧客，凡購買30元以上商品者均有機會獲得本商場提供的一份精美禮品。」該商場的幸運顧客產生方式十分奇特：每位顧客可至抽獎臺抽取一個幸運號碼，該商場在抽獎活動推出的第i天將從所有顧客中（包括不在本日購物滿30元者）挑出幸運號第i小的顧客作為當日的幸運顧客。該商場的商品本就價廉物美，自從有獎活動推出後，顧客更是絡繹不絕，因此急需你編寫一個程式，為他解決幸運顧客的產生問題。
【輸入資料】
第1行一個整數N，表示命令數。
第2~N+1行，每行一個數，表示命令。如果x>=0，表示有一顧客抽取了號碼x；如果x=-1，表示傍晚抽取該日的幸運號碼。
【輸出資料】
對應各命令-1輸出幸運號碼；每行一個號碼。(兩個相同的幸運號看作兩個號碼)
樣例輸入
6
3
4
-1
-1
3
-1
樣例輸出
3
4
4
解釋
只關注獲獎的號碼是多少，每個號碼可以獲獎多次。
資料規模及約定
共10組資料。
對100%的資料，N=10^6所有命令為-1或int範圍內的非負數，前i的命令中-1的數量不超過[i/2]（向下取整）。
很簡單，不多說啦。
n = int(input())
arr = []
rs = []
ans = 0
for i in range(n):
data = int(input())
if data != -1:
arr.append(data)
else:
arr.sort()
rs.append(arr[ans])
ans += 1
for i in range(len(rs)):
print(rs[i])
3.6 最長公共子序列（LCS）
資源限制
時間限制：1.0s 記憶體限制：256.0MB
問題描述
給定兩個字串，尋找這兩個字串之間的最長公共子序列。
輸入格式
輸入兩行，分別包含一個字串，僅含有小寫字母。
輸出格式
最長公共子序列的長度。
樣例輸入
abcdgh
aedfhb
樣例輸出
3
樣例說明
最長公共子序列為a，d，h。
資料規模和約定
字串長度1~1000。
動態規劃問題，參考下面連結
最長公告子序列詳解
def lcs(str_a, str_b):
len_a = len(a)
len_b = len(b)
arr = [[0 for _ in range(len_b + 1)] for _ in range(len_a + 1)]
for i in range(len_a + 1):
for j in range(len_b + 1):
if i == 0 or j == 0:
arr[i][j] = 0
elif i > 0 and j > 0 and str_a[i - 1] == str_b[j - 1]:
arr[i][j] = arr[i - 1][j - 1] + 1
else:
arr[i][j] = max(arr[i][j - 1], arr[i - 1][j])
return arr[len_a][len_b]
a = input()
b = input()
print(lcs(a, b))
3.7 複數求和
資源限制
時間限制：1.0s 記憶體限制：512.0MB
從鍵盤讀入n個複數（實部和虛部都為整數）用連結串列儲存，遍歷連結串列求出n個複數的和並輸出。
樣例輸入:
3
3 4
5 2
1 3
樣例輸出:
9+9i
樣例輸入:
7
1 2
3 4
2 5
1 8
6 4
7 9
3 7
樣例輸出:
23+39i
列表中的元素是元組
n = int(input())
real = 0
imaginary = 0
com = [tuple(map(int, input().split())) for _ in range(n)]
for i in range(n):
real += com[i][0]
imaginary += com[i][1]
print(real, '+', imaginary, 'i', sep='')
3.8 成績排名（結構體）
資源限制
時間限制：1.0s 記憶體限制：256.0MB
問題描述
小明剛經過了一次數學考試，老師由於忙碌忘記排名了，於是老師把這個光榮的任務交給了小明，小明則找到了聰明的你，希望你能幫他解決這個問題。
輸入格式
第一行包含一個正整數N，表示有個人參加了考試。接下來N行，每行有一個字串和一個正整數，分別表示人名和對應的成績，用一個空格分隔。
輸出格式
輸出一共有N行，每行一個字串，第i行的字串表示成績從高到低排在第i位的人的名字，若分數一樣則按人名的字典序順序從小到大。
樣例輸入
3
aaa 47
bbb 90
ccc 70
樣例輸出
bbb
ccc
aaa 【資料規模和約定】
人數<=100,分數<=100,人名僅包含小寫字母。
主要是對排序函數的利用
sort()函數
n = int(input())
information = [tuple(input().split()) for _ in range(n)]
information.sort(key=lambda x: x[0]) # 先排姓名，按字母順序
information.sort(key=lambda x: int(x[1]),reverse=True) # 後排成績，從大到小
for i in range(n):
print(information[i][0])
3.9 遞迴倒置字元陣列
資源限制
時間限制：1.0s 記憶體限制：512.0MB
問題描述
完成一個遞迴程式，倒置字元陣列。並列印實現過程
遞迴邏輯為：
當字元長度等於1時，直接返回
否則，調換首尾兩個字元，在遞迴地倒置字元陣列的剩下部分
輸入格式
字元陣列長度及該陣列
輸出格式
在求解過程中，列印字元陣列的變化情況。
最後空一行，在程式結尾處列印倒置後該陣列的各個元素。
樣例輸入
Sample 1
5 abcde
Sample 2
1 a
樣例輸出
Sample 1
ebcda
edcba
edcba
Sample 2
a
有一點需要注意
字串是不可變的，要想改變，需要把它強轉為列表
再者，提醒一下
這個符號 // 是取商，這個符號 % 是求餘
還有python中獨有的二變數交換
a, b = b, a
n, s = input().split()
n = int(n)
s = list(s)
i = 0
while i < n // 2:
s[i], s[n - i - 1] = s[n - i - 1], s[i]
print(''.join(s))
i += 1
print('\n'+''.join(s))
3.10 字串跳步
資源限制
時間限制：1.0s 記憶體限制：256.0MB
問題描述
給定一個字串，你需要從第start位開始每隔step位輸出字串對應位置上的字元。
輸入格式
第一行一個只包含小寫字母的字串。
第二行兩個非負整數start和step，意義見上。
輸出格式
一行，表示對應輸出。
樣例輸入
abcdefg
2 2
樣例輸出
ceg
資料規模和約定
start從0開始計數。
字串長度不超過100000。
python如此簡單
s = input()
start, step = map(int, input().split())
print(s[start: : step])
3.11 最長字元序列（同LCS）
資源限制
時間限制：1.0s 記憶體限制：256.0MB
最長字元序列
問題描述
設x(i), y(i), z(i)表示單個字元，則X={x(1)x(2)……x(m)}，Y={y(1)y(2)……y(n)}，Z={z(1)z(2)……z(k)},我們稱其為字元序列，其中m,n和k分別是字元序列X，Y，Z的長度，括號()中的數位被稱作字元序列的下標。
如果存在一個嚴格遞增而且長度大於0的下標序列{i1,i2……ik}，使得對所有的j=1,2,……k，有x(ij)=z(j)，那麼我們稱Z是X的字元子序列。而且，如果Z既是X的字元子序列又是Y的字元子序列，那麼我們稱Z為X和Y的公共字元序列。
在我們今天的問題中，我們希望計算兩個給定字元序列X和Y的最大長度的公共字元序列，這裡我們只要求輸出這個最大長度公共子序列對應的長度值。
舉例來說，字元序列X=abcd，Y=acde，那麼它們的最大長度為3，相應的公共字元序列為acd。
輸入格式
輸入一行，用空格隔開的兩個字串
輸出格式
輸出這兩個字元序列對應的最大長度公共字元序列的長度值
樣例輸入
aAbB aabb
樣例輸出
2
資料規模和約定
輸入字串長度最長為100，區分大小寫。
def lcs(str_a, str_b):
len_a = len(a)
len_b = len(b)
arr = [[0 for _ in range(len_b + 1)] for _ in range(len_a + 1)]
for i in range(len_a + 1):
for j in range(len_b + 1):
if i == 0 or j == 0:
arr[i][j] = 0
elif i > 0 and j > 0 and str_a[i - 1] == str_b[j - 1]:
arr[i][j] = arr[i - 1][j - 1] + 1
else:
arr[i][j] = max(arr[i][j - 1], arr[i - 1][j])
return arr[len_a][len_b]
a, b = input().split()
print(lcs(a, b))
3.12 佇列操作
問題描述
佇列操作題。根據輸入的操作命令，操作佇列（1）入隊、（2）出隊並輸出、（3）計算隊中元素個數並輸出。
輸入格式
第一行一個數位N。
下面N行，每行第一個數位為操作命令（1）入隊、（2）出隊並輸出、（3）計算隊中元素個數並輸出。
輸出格式
若干行每行顯示一個2或3命令的輸出結果。注意：2.出隊命令可能會出現空隊出隊（下溢），請輸出「no」，並退出。
樣例輸入
7
1 19
1 56
2
3
2
3
2
樣例輸出
19
1
56
0
no
資料規模和約定
1<=N<=50
N = int(input())
queue = []
for _ in range(N):
command = list(map(int, input().split()))
if command[0] == 1:
queue.append(command[1])
elif command[0] == 2:
if len(queue) == 0:
print('no')
else:
print(queue[0])
queue.pop(0)
else:
print(len(queue))
3.13 字串操作
問題描述
給出一個字串和多行文字，在這些文字中找到字串出現的那些行。你的程式還需支援大小寫敏感選項：當選項開啟時，表示同一個字母的大寫和小寫看作不同的字元；當選項關閉時，表示同一個字母的大寫和小寫看作相同的字元。
輸入格式
輸入的第一行包含一個字串S，由大小寫英文字母組成。
第二行包含一個數位，表示大小寫敏感的選項，當數位為0時表示大小寫不敏感，當數位為1時表示大小寫敏感。
第三行包含一個整數n，表示給出的文字的行數。
接下來n行，每行包含一個字串，字串由大小寫英文字母組成，不含空格和其他字元。
輸出格式
輸出多行，每行包含一個字串，按出現的順序依次給出那些包含了字串S的行。
樣例輸入
Hello
1
5
HelloWorld
HiHiHelloHiHi
GrepIsAGreatTool
HELLO
HELLOisNOTHello
樣例輸出
HelloWorld
HiHiHelloHiHi
HELLOisNOTHello
樣例說明
在上面的樣例中，第四個字串雖然也是Hello，但是大小寫不正確。如果將輸入的第二行改為0，則第四個字串應該輸出。
評測用例規模與約定
1<=n<=100，每個字串的長度不超過100。
S = input()
alpha_switch = int(input())
n = int(input())
for _ in range(n):
s_ = input()
if alpha_switch == 1:
if S in s_:
print(s_)
else:
if S.upper() in s_.upper():
print(s_)
字串大小寫轉換函數
字串的find()、index()、rfind()、rindex()
參考地址
3.14 金陵十三釵
問題描述
在電影《金陵十三釵》中有十二個秦淮河的女人要自我犧牲代替十二個女學生去赴日本人的死亡宴會。為了不讓日本人發現，自然需要一番喬裝打扮。但由於天生材質的原因，每個人和每個人之間的相似度是不同的。由於我們這是程式設計題，因此情況就變成了金陵n釵。給出n個女人和n個學生的相似度矩陣，求她們之間的匹配所能獲得的最大相似度。
所謂相似度矩陣是一個n*n的二維陣列like[i][j]。其中i,j分別為女人的編號和學生的編號，皆從0到n-1編號。like[i][j]是一個0到100的整數值，表示第i個女人和第j個學生的相似度，值越大相似度越大，比如0表示完全不相似，100表示百分之百一樣。每個女人都需要找一個自己代替的女學生。
最終要使兩邊一一配對，形成一個匹配。請程式設計找到一種匹配方案，使各對女人和女學生之間的相似度之和最大。
輸入格式
第一行一個正整數n表示有n個秦淮河女人和n個女學生
接下來n行給出相似度，每行n個0到100的整數，依次對應二維矩陣的n行n列。
輸出格式
僅一行，一個整數，表示可獲得的最大相似度。
樣例輸入
4
97 91 68 14
8 33 27 92
36 32 98 53
73 7 17 82
樣例輸出
354
資料規模和約定
對於70%的資料，n<=10
對於100%的資料，n<=13
樣例說明
最大相似度為91+92+98+73=354
n皇后弱化版
def queen(cur=0):
global sum1, n
if cur == n: # 所有的皇后都正確放置完畢，輸出每個皇后所在的位置
sum2 = 0
for i in range(n):
sum2 += a[i][b[i]]
if sum2 > sum1:
sum1 = sum2
return 0
for i in range(n):
flag = True
for j in range(cur): # 檢測本次所放的位置是否在同行同列
if b[j] == i: # 是的話，該位置不能放，向上回溯
flag = False
break
if flag: # 否的話，繼續放下一個
b[cur] = i
queen(cur+1)
n = int(input())
sum1 = 0
a = [list(map(int, input().split())) for _ in range(n)]
b = [0 for _ in range(n)]
queen()
print(sum1)
4.真題篇
待更新…
4.1不同子串
題目描述
一個字串的非空子串是指字串中長度至少為 1 的連續的一段字元組成 的串。例如，字串aaab 有非空子串a, b, aa, ab, aaa, aab, aaab，一共 7 個。 注意在計算時，只算本質不同的串的個數。
請問，字串0100110001010001 有多少個不同的非空子串？
【答案提交】
這是一道結果填空的題，你只需要算出結果後提交即可。本題的結果為一 個整數，在提交答案時只填寫這個整數，填寫多餘的內容將無法得分。
這道題不難，大家都是能想到的應該。話不多說，直接上程式碼。
var = '0100110001010001' # var = 'aaab' 執行結果為7 表示演演算法正確
num = 1 # 自身也是1個，迴圈中沒有去考慮他串本身，所以這裡基數直接設定為1
sep = 1
var_n = []
while sep < len(var):
var_n.append(var[0:sep])
for i in range(len(var)-sep): # 以sep為間隔依次向前推進，sep每輪迴圈增1
if var[i+1:i+sep+1] in var_n:
continue
else:
var_n.append(var[i+1:i+sep+1])
sep += 1
num += len(var_n)
# print(var_n)
var_n = []
print(num)
執行結果
直接提交100就可以了。
4.2 年號字串
小明用字母A 對應數位1，B 對應2，以此類推，用Z 對應26。對於27
以上的數位，小明用兩位或更長位的字串來對應，例如AA 對應27，AB 對
應28，AZ 對應52，LQ 對應329。
請問2019 對應的字串是什麼？
實際上即為進位制轉換
"""
類似於進位制轉換，只是多了一步，把對應的字母換上
A~Z代表1~26，每26進1，27即為AA
17 77 Q
25 2 Y
2 0 B
BYQ
17 + 25 * 26 + 2 * 26 * 26 = 2019
"""
string = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
ans = [0 for _ in range(5)]
index = 0
n = 2019
while n != 0:
t = n % 26
n = int(n / 26)
ans[index] = string[t - 1]
# print(t, n, ans[index])
index += 1
for i in range(index - 1, -1, -1):
print(ans[i], end='')
直接提交BYQ就可以啦。
4.3 數列求值
【問題描述】
給定數列 1, 1, 1, 3, 5, 9, 17, …，從第 4 項開始，每項都是前 3 項的和。求第 20190324 項的最後 4 位數位。
【答案提交】
這是一道結果填空的題，你只需要算出結果後提交即可。本題的結果為一個 4 位整數（提示：答案的千位不為 0），在提交答案時只填寫這個整數，填寫多餘的內容將無法得分。
只求後四位就可以啦
arr = [0 for _ in range(20190325)]
arr[0] = arr[1] = arr[2] = 1
for i in range(3, 20190324):
arr[i] = (arr[i - 1] + arr[i - 2] + arr[i - 3]) % 10000
print(arr[20190323])
答案：4659
4.4 數的分解
【問題描述】
把 2019 分解成 3 個各不相同的正整數之和，並且要求每個正整數都不包含數位 2 和 4，一共有多少種不同的分解方法？
注意交換 3 個整數的順序被視為同一種方法，例如 1000+1001+18 和 1001+1000+18 被視為同一種。
【答案提交】
這是一道結果填空的題，你只需要算出結果後提交即可。本題的結果為一 個整數，在提交答案時只填寫這個整數，填寫多餘的內容將無法得分。
count = 0
def check(x):
while x != 0:
t = x % 10
x = int(x / 10)
if t == 2 or t == 4:
return False
return True
for i in range(1, 2019):
if check(i):
for j in range(i + 1, 2019):
if check(j):
k = 2019 - i - j
if k > j and check(k):
count += 1
print(i, j, k)
print(count)
答案：40785
4.5 迷宮
資料
01010101001011001001010110010110100100001000101010
00001000100000101010010000100000001001100110100101
01111011010010001000001101001011100011000000010000
01000000001010100011010000101000001010101011001011
00011111000000101000010010100010100000101100000000
11001000110101000010101100011010011010101011110111
00011011010101001001001010000001000101001110000000
10100000101000100110101010111110011000010000111010
00111000001010100001100010000001000101001100001001
11000110100001110010001001010101010101010001101000
00010000100100000101001010101110100010101010000101
11100100101001001000010000010101010100100100010100
00000010000000101011001111010001100000101010100011
10101010011100001000011000010110011110110100001000
10101010100001101010100101000010100000111011101001
10000000101100010000101100101101001011100000000100
10101001000000010100100001000100000100011110101001
00101001010101101001010100011010101101110000110101
11001010000100001100000010100101000001000111000010
00001000110000110101101000000100101001001000011101
10100101000101000000001110110010110101101010100001
00101000010000110101010000100010001001000100010101
10100001000110010001000010101001010101011111010010
00000100101000000110010100101001000001000000000010
11010000001001110111001001000011101001011011101000
00000110100010001000100000001000011101000000110011
10101000101000100010001111100010101001010000001000
10000010100101001010110000000100101010001011101000
00111100001000010000000110111000000001000000001011
10000001100111010111010001000110111010101101111000
其他語言都為廣度搜尋，此方法類似，用佇列來操作節點
此題為藍橋練習系統的一道原題（非常類似，答案完全可以拿來直接用）：學霸的迷宮
class Node(object): # 節點類
def __init__(self, x, y, w): # 新增類變數
self.x = x
self.y = y
self.w = w
def __str__(self): # 類方法，呼叫此方法時返回w的內容
return self.w
def up(node):
return Node(node.x - 1, node.y, node.w+"U") # 向上的情況
def down(node):
return Node(node.x + 1, node.y, node.w+"D") # 向下的情況
def left(node):
return Node(node.x, node.y - 1, node.w+"L") # 向左的情況
def right(node):
return Node(node.x, node.y + 1, node.w+"R") # 向右的情況
if __name__ == '__main__':
m, n = map(int, input().split())
visited = set() # 儲存存取過的節點
queue = [] # 首先建一個空佇列用來儲存存取的節點
map_int = [[0] * (n + 1)] # 第一行全置0
for i in range(1, m+1):
map_int.append([0]*(n+1))
nums = input() # 輸入資料
nums = "0" + nums # 第一列全置0
for j in range(0, n+1):
map_int[i][j] = ord(nums[j]) - 48 # 把字元‘1’、‘0’轉為數位
# print(map_int)
# exit()
node = Node(1, 1, "") # 開始位置節點
queue.append(node) # 放入佇列
while len(queue) != 0: # 隊不空時迴圈
moveNode = queue[0] # 移動節點
queue.pop(0) # 移動節點出佇列
moveStr = str(moveNode.x) + " "+ str(moveNode.y) # 移動節點位置
if moveStr not in visited: # 移動節點若未存取
visited.add(moveStr) # 放入已存取節點列表
if moveNode.x == m and moveNode.y == n: # 到達最後位置時停止迴圈
print(len(moveNode.__str__())) # 輸出步數，即長度
print(moveNode) # 輸出路徑
break
if moveNode.x < m:
if map_int[moveNode.x + 1][moveNode.y] == 0: # 向下的情況
queue.append(down(moveNode))
if moveNode.y > 1:
if map_int[moveNode.x][moveNode.y - 1] == 0: # 向左的情況
queue.append(left(moveNode))
if moveNode.y < n:
if map_int[moveNode.x][moveNode.y + 1] == 0: # 向右的情況
queue.append(right(moveNode))
if moveNode.x > 1:
if map_int[moveNode.x - 1][moveNode.y] == 0: # 向上的情況
queue.append(up(moveNode))
參考答案：
DDDDRRURRRRRRDRRRRDDDLDDRDDDDDDDDDDDDRDDRRRURRUURRDDDDRDRRRRRRDRRURRDDDRRRRUURUUUUUUULULLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDDRRRRRDDRRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR
共186步
4.6 特別數的和
此題資料規模不大，直接暴力搜尋解決就可以，較為簡單
n = int(input())
s = 0
for i in range(1, n + 1):
a = i
while a != 0:
temp = a % 10
a = int(a / 10)
if temp in [2, 0, 1, 9]:
s += i
falg = True
break
print(s)
4.7 完全二元樹的和
解題思路：
完全二元樹每一行的最後一個數的下標都是等於(2^n)-1
用deep表示當前深度，從當前這行的第一項加到最後一項然後和最大值max_sum比較。
n = int(input())
data = list(map(int, input().split()))
deep = flag_deep = 1
max_sum = 0
while 2 ** deep - 1 <= n:
data_sum = sum(data[2 ** (deep - 1) - 1:(2 ** deep)])
if max_sum < data_sum:
max_sum = data_sum
flag_deep = deep
deep += 1
print(flag_deep)
# 一組測試資料
# 15
# 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
# 4
4.8 等差數列
解題思路：
先排序，然後找出等差數列的差值（各相鄰數差值最小的），之後從所給陣列的最小到最大開始迴圈，步長為所求的差值diff，利用count來計數
n = int(input())
data = list(map(int, input().split()))
count = 0
data.sort()
diff = float('inf') # float('inf') 為無窮大，float('-inf') 為無窮小
for i in range(1, n):
now_diff = data[i] - data[i - 1]
if now_diff < diff:
diff = now_diff
for i in range(data[0], data[-1], diff):
count += 1
print(count + 1)
4.9 換鈔票
x星球的鈔票的面額只有：100元，5元，2元，1元，共4種。
小明去x星旅遊，他手裡只有2張100元的x星幣，太不方便，恰好路過x星銀行就去換零錢。
小明有點強迫症，他堅持要求200元換出的零鈔中2元的張數剛好是1元的張數的10倍，
剩下的當然都是5元面額的。
銀行的工作人員有點為難，你能幫助算出：在滿足小明要求的前提下，最少要換給他多少張鈔票嗎？
（5元，2元，1元面額的必須都有，不能是0）
注意，需要提交的是一個整數，不要填寫任何多餘的內容。
for one in range(1,10):
five = 0
two = one * 10
money = 200 - two * 2 - one
if money % 5 == 0:
five = money / 5
count = one + two + five
print(one, two, five, count)
因為數目較小，很簡單。這裡程式碼直接列出了所有情況，執行結果如下：
排除5元張數為0的情況就只剩下一種啦。
且結果為整數，則為74.
4.10 調手錶
小明買了塊高階大氣上檔次的電子手錶，他正準備調時間呢。
在 M78 星雲，時間的計量單位和地球上不同，M78 星雲的一個小時有 n 分鐘。
大家都知道，手錶只有一個按鈕可以把當前的數加一。在調分鐘的時候，如果當前顯示的數是 0 ，那麼按一下按鈕就會變成 1，再按一次變成 2 。如果當前的數是 n - 1，按一次後會變成 0 。
作為強迫症患者，小明一定要把手錶的時間調對。如果手錶上的時間比當前時間多1，則要按 n - 1 次加一按鈕才能調回正確時間。
小明想，如果手錶可以再新增一個按鈕，表示把當前的數加 k 該多好啊……
他想知道，如果有了這個 +k 按鈕，按照最優策略按鍵，從任意一個分鐘數調到另外任意一個分鐘數最多要按多少次。
注意，按 +k 按鈕時，如果加k後數位超過n-1,則會對n取模。
比如，n=10, k=6 的時候，假設當前時間是0，連按2次 +k 按鈕，則調為2。
「輸入格式」
一行兩個整數 n, k ，意義如題。
「輸出格式」
一行一個整數
表示：按照最優策略按鍵，從一個時間調到另一個時間最多要按多少次。
「樣例輸入」
5 3
「樣例輸出」
2
「樣例解釋」
如果時間正確則按0次。否則要按的次數和操作系列之間的關係如下：
1：+1
2：+1, +1
3：+3
4：+3, +1
「資料範圍」
對於 30% 的資料 0 < k < n <= 5
對於 60% 的資料 0 < k < n <= 100
對於 100% 的資料 0 < k < n <= 100000
資源約定：
峰值記憶體消耗（含虛擬機器器） < 256M
CPU消耗 < 1000ms
請嚴格按要求輸出，不要畫蛇添足地列印類似：「請您輸入…」 的多餘內容。
注意：
main函數需要返回0;
只使用ANSI C/ANSI C++ 標準;
不要呼叫依賴於編譯環境或作業系統的特殊函數。
所有依賴的函數必須明確地在原始檔中 #include
不能通過工程設定而省略常用標頭檔案。
提交程式時，注意選擇所期望的語言型別和編譯器型別。
記住要求：
按照最優策略下的最多次數
開始我就困擾了，求成了最少次數
每次加1，遇到被整除的地方，原先的計數器置零，整除計數器加1
記錄每次整除後的數值，求出最大的哪個數就是
n, k = map(int, input().split())
ans = []
count = count_ =0
for i in range(1, n):
if i % k != 0:
count += 1
else:
count = 0
count_ += 1
ans.append(count + count_)
print(max(ans))
樣例中的 5 3
對應的ans=[1, 2, 1, 2]
最大為2
比網上的其他df和bfs之類的要簡單而且好理解的多
4.11 矩陣求和
經過重重筆試面試的考驗，小明成功進入 Macrohard 公司工作。 今天小明的任務是填滿這麼一張表： 表有 n 行 n 列，行和列的編號都從1算起。 其中第 i 行第 j 個元素的值是 gcd(i, j)的平方， gcd 表示最大公約數，以下是這個表的前四行的前四列： 1 1 1 1 1 4 1 4 1 1 9 1 1 4 1 16
小明突然冒出一個奇怪的想法，他想知道這張表中所有元素的和。 由於表過於龐大，他希望藉助計算機的力量。
「輸入格式」 一行一個正整數 n 意義見題。
「輸出格式」 一行一個數，表示所有元素的和。由於答案比較大，請輸出模 (10^9 + 7)(即：十億零七) 後的結果。
「樣例輸入」 4
「樣例輸出」 48
「資料範圍」 對於 30% 的資料，n <= 1000 存在 10% 的資料，n = 10^5 對於 60% 的資料，n <= 10^6 對於 100% 的資料，n <= 10^7
暴力求解是大家都會想到的，但是肯定會超時
這個題滿分的話要用到數論的知識：尤拉函數+莫比烏斯反演。
暴力程式碼
def gcd(i, j):
while j !=0:
k = i % j
i = j
j = k
return i
n = int(input())
sum_arr = 0
mod = 10 ** 9 + 7
for i in range(n):
for j in range(n):
t = gcd(i, j) ** 2
sum_arr += t % mod
print(sum_arr)
能得到一部分分數，考試時不會可以拿到一定的分數。
MOD = 10 ** 9 + 7
phi = []
sum_ = []
ans = 0
def euler_table(n):
for _ in range(n + 1):
phi.append(0)
sum_.append(0)
phi[1] = 1
for i in range(2, n + 1):
if phi[i] == 0:
j = i
while j <= n:
if phi[j] == 0:
phi[j] = j
phi[j] = int(phi[j] / i) * (i - 1)
j += i
sum_[1] = 1
for i in range(2, n + 1):
sum_[i] = sum_[i - 1] + phi[i] * 2
n = int(input())
euler_table(n)
for i in range(1, n + 1):
ans = (ans + sum_[int(n / i)] * i % MOD * i % MOD) % MOD
print(ans)
4.12 分數
標題：分數
1/1 + 1/2 + 1/4 + 1/8 + 1/16 + …
每項是前一項的一半，如果一共有20項,
求這個和是多少，結果用分數表示出來。
類似：
3/2
當然，這只是加了前2項而已。分子分母要求互質。
注意：
需要提交的是已經約分過的分數，中間任何位置不能含有空格。
請不要填寫任何多餘的文字或符號
求出分母，分子為2^19
用gcd函數通分
def gcd(a, b):
while b != 0:
c = a % b
a = b
b = c
return a
molecule = 0
for i in range(20):
molecule += 2 ** i
gc = gcd(molecule, 2 ** 19)
print(molecule // gc,'/',2 ** 19 // gc, sep='')
4.13 購物單
標題： 購物單
小明剛剛找到工作，老闆人很好，只是老闆夫人很愛購物。老闆忙的時候經常讓小明幫忙到商場代為購物。小明很厭煩，但又不好推辭。
這不，XX大促銷又來了！老闆夫人開出了長長的購物單，都是有打折優惠的。
小明也有個怪癖，不到萬不得已，從不刷卡，直接現金搞定。
現在小明很心煩，請你幫他計算一下，需要從取款機上取多少現金，才能搞定這次購物。
取款機只能提供100元面額的紙幣。小明想盡可能少取些現金，夠用就行了。
你的任務是計算出，小明最少需要取多少現金。
以下是讓人頭疼的購物單，為了保護隱私，``物品名稱被隱藏了。
**** 180.90 88折
**** 10.25 65折
**** 56.14 9折
**** 104.65 9折
**** 100.30 88折
**** 297.15 半價
**** 26.75 65折
**** 130.62 半價
**** 240.28 58折
**** 270.62 8折
**** 115.87 88折
**** 247.34 95折
**** 73.21 9折
**** 101.00 半價
**** 79.54 半價
**** 278.44 7折
**** 199.26 半價
**** 12.97 9折
**** 166.30 78折
**** 125.50 58折
**** 84.98 9折
**** 113.35 68折
**** 166.57 半價
**** 42.56 9折
**** 81.90 95折
**** 131.78 8折
**** 255.89 78折
**** 109.17 9折
**** 146.69 68折
**** 139.33 65折
**** 141.16 78折
**** 154.74 8折
**** 59.42 8折
**** 85.44 68折
**** 293.70 88折
**** 261.79 65折
**** 11.30 88折
**** 268.27 58折
**** 128.29 88折
**** 251.03 8折
**** 208.39 75折
**** 128.88 75折
**** 62.06 9折
**** 225.87 75折
**** 12.89 75折
**** 34.28 75折
**** 62.16 58折
**** 129.12 半價
**** 218.37 半價
**** 289.69 8折
需要說明的是，88折指的是按標價的88%計算，而8折是按80%計算，餘者類推。
特別地，半價是按50%計算。
請提交小明要從取款機上提取的金額，單位是元。
答案是一個整數，類似4300的樣子，結尾必然是00，不要填寫任何多餘的內容。
特別提醒：不許攜帶計算器入場，也不能開啟手機。
首先在把資料複製到記事本中
其次用Ctrl+H鍵替換
把****用空格替換
把7折、8折、9折替換為70、80、90
半價替換為50
其餘折用空格替換
預處理後資料為
180.90 88
10.25 65
56.14 90
104.65 90
100.30 88
297.15 50
26.75 65
130.62 50
240.28 58
270.62 80
115.87 88
247.34 95
73.21 90
101.00 50
79.54 50
278.44 70
199.26 50
12.97 90
166.30 78
125.50 58
84.98 90
113.35 68
166.57 50
42.56 90
81.90 95
131.78 80
255.89 78
109.17 90
146.69 68
139.33 65
141.16 78
154.74 80
59.42 80
85.44 68
293.70 88
261.79 65
11.30 88
268.27 58
128.29 88
251.03 80
208.39 75
128.88 75
62.06 90
225.87 75
12.89 75
34.28 75
62.16 58
129.12 50
218.37 50
289.69 80
然後用程式碼計算就可以了
def result(s):
return (float(s[0]) * float(s[1])) / 100
file = open('data.txt', 'r')
ans = 0
for line in file.readlines():
s = line.split()
ans += result(s)
file.close()
print(ans)
執行後結果
5136.859500000001
所以最終答案為5200
4.14 等差素數列
2,3,5,7,11,13,…是素數序列。
類似：7,37,67,97,127,157 這樣完全由素陣列成的等差數列，叫等差素數數列。
上邊的數列公差為30，長度為6。
2004年，格林與華人陶哲軒合作證明了：存在任意長度的素數等差數列。
這是數論領域一項驚人的成果！
有這一理論為基礎，請你藉助手中的計算機，滿懷信心地搜尋：
長度為10的等差素數列，其公差最小值是多少？
注意：需要提交的是一個整數，不要填寫任何多餘的內容和說明文字。
解釋註釋部分
def init_num():
global tot
for i in range(2, N):
if dp[i] == 1:
continue
prim[tot] = i # 記錄N以內的所有素數
tot += 1
j = i
while i * j < N:
dp[i * j] = 1 # 不是素數的位置標記1
j += 1
N = 1000010 # N的大小自己可以估計一下 想想也應該挺大的 多試幾次
dp = [1, 1] + [ 0] * N
tot = 0
dif = 1
prim = [0] * N
init_num()
# print(dp[:100])
# print(prim[:100])
print(tot)
while dif * 10 < N:
for j in range(tot):
flag, temp = True, prim[j]
for k in range(1, 10): # temp後邊是否再有9個滿足等差條件的素數
if temp + dif >= N or dp[temp + dif] == 1:
flag = False
break
else:
temp += dif
if flag == True:
print(dif, prim[j])
exit()
dif += 1
執行結果
78499
210 199
解釋：
N以內一共78499個素數
dif為210
起點199
十個數為：
dif_arr = [199]
dif = 210
for i in range(9):
dif_arr.append(dif_arr[-1] + dif)
print(dif_arr)
[199, 409, 619, 829, 1039, 1249, 1459, 1669, 1879, 2089]
4.15 承壓計算
X星球的高科技實驗室中整齊地堆放著某批珍貴金屬原料。
每塊金屬原料的外形、尺寸完全一致，但重量不同。
金屬材料被嚴格地堆放成金字塔形。
7
5 8
7 8 8
9 2 7 2
8 1 4 9 1
8 1 8 8 4 1
7 9 6 1 4 5 4
5 6 5 5 6 9 5 6
5 5 4 7 9 3 5 5 1
7 5 7 9 7 4 7 3 3 1
4 6 4 5 5 8 8 3 2 4 3
1 1 3 3 1 6 6 5 5 4 4 2
9 9 9 2 1 9 1 9 2 9 5 7 9
4 3 3 7 7 9 3 6 1 3 8 8 3 7
3 6 8 1 5 3 9 5 8 3 8 1 8 3 3
8 3 2 3 3 5 5 8 5 4 2 8 6 7 6 9
8 1 8 1 8 4 6 2 2 1 7 9 4 2 3 3 4
2 8 4 2 2 9 9 2 8 3 4 9 6 3 9 4 6 9
7 9 7 4 9 7 6 6 2 8 9 4 1 8 1 7 2 1 6
9 2 8 6 4 2 7 9 5 4 1 2 5 1 7 3 9 8 3 3
5 2 1 6 7 9 3 2 8 9 5 5 6 6 6 2 1 8 7 9 9
6 7 1 8 8 7 5 3 6 5 4 7 3 4 6 7 8 1 3 2 7 4
2 2 6 3 5 3 4 9 2 4 5 7 6 6 3 2 7 2 4 8 5 5 4
7 4 4 5 8 3 3 8 1 8 6 3 2 1 6 2 6 4 6 3 8 2 9 6
1 2 4 1 3 3 5 3 4 9 6 3 8 6 5 9 1 5 3 2 6 8 8 5 3
2 2 7 9 3 3 2 8 6 9 8 4 4 9 5 8 2 6 3 4 8 4 9 3 8 8
7 7 7 9 7 5 2 7 9 2 5 1 9 2 6 5 3 9 3 5 7 3 5 4 2 8 9
7 7 6 6 8 7 5 5 8 2 4 7 7 4 7 2 6 9 2 1 8 2 9 8 5 7 3 6
5 9 4 5 5 7 5 5 6 3 5 3 9 5 8 9 5 4 1 2 6 1 4 3 5 3 2 4 1
X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X
其中的數位代表金屬塊的重量（計量單位較大）。
最下一層的X代表30臺極高精度的電子秤。
假設每塊原料的重量都十分精確地平均落在下方的兩個金屬塊上，
最後，所有的金屬塊的重量都嚴格精確地平分落在最底層的電子秤上。
電子秤的計量單位很小，所以顯示的數位很大。
工作人員發現，其中讀數最小的電子秤的示數為：2086458231
請你推算出：讀數最大的電子秤的示數為多少？
注意：需要提交的是一個整數，不要填寫任何多餘的內容。
把資料存到二維表裡進行計算
arr = [[0] * 30 for _ in range(30)]
k = 0
file = open('data.txt', 'r')
for line in file.readlines():
new_line = line.split()
for i in range(len(new_line)):
arr[k][i] = int(new_line[i])
k += 1
for i in range(1, 30):
for j in range(29):
arr[i][j] += arr[i - 1][j] / 2
arr[i][j + 1] += arr[i - 1][j] / 2
# print(min(arr[29]), max(arr[29]))
print(2086458231 / min(arr[29]) * max(arr[29]))
72665192664.0
接續篇傳送門
Python解答藍橋杯省賽真題之從入門到真題（續）