第十三屆藍橋杯模擬賽第二期python組個人題解

👨?🎓 作者簡介：大家好，我是可可卷，在十二屆藍橋杯中僥幸獲得國家三等獎，自知實力有限，代碼不足之處還請各位大佬多多批評指正~
📜主攻領域：【python演算法】【資料分析】【數學建模】【機器學習】【深度學習】【資料可視化】
📖個人主頁：可可卷的博客

題目1

小藍的IP地址為 192.168.*.21，其中 * 是一個數字，請問這個數字最大可能是多少 ?

答案：255

題解：計算機網路的內容，IP地址以8位二進制表示一個位，所以范圍是【0，2^8-1】，因此最大值為255

題目2

如果一個整數 g 能同時整除整數 A 和 B，則稱 g 是 A 和 B 的公約數，例如：43 是 86 和 2021 的公約數，
請問在 1（含） 到 2021（含） 中，有多少個數與 2021 存在大于 1 的公約數，請注意 2021 和 2021 有大于 1 的公約數，因此在計算的時候要算一個，

答案：89

題解：

先給大家二份計算最大公約數的代碼：

# 迭代寫法
def gcd(a,b):
    while b:
        a,b=b,a%b
    return a
    
# 遞回寫法
def gcd(a,b):
    if not a%b:return b
    return gcd(b,a%b)

然后計算與 2021 存在大于 1 的公約數的【數】的個數

res = 1
for i in range(1, 2021):
    if gcd(i, 2021) > 1:
        res += 1

print(res)

注意res初值為1，下面這份代碼也是等價的

res = 0
for i in range(1, 2022):
    if gcd(i, 2021) > 1:
        res += 1

print(res)

題目3

2021 是一個非常特殊的數，它可以表示成兩個非負整數的平方差，2021 = 45 * 45 - 2 * 2，
2025 也是同樣特殊的數，它可以表示成 2025 = 45 * 45 - 0 * 0，
請問，在 1 到 2021 中有多少個這樣的數？
請注意，有的數有多種表示方法，例如 9 = 3 * 3 - 0 * 0 = 5 * 5 - 4 * 4，在算答案時只算一次，

答案：1516

題解：記住3個點

• 平方差公式：a^2 - b^2 = （a+b)（a-b）

• 確定內層回圈范圍：b<a，即內層回圈最大值不大于外層回圈當前值

• 確定外層回圈范圍：b=a-1時取得最小正數，此時（a+b)（a-b）=（2a-1)，令2a-1=2021,得到a的上限1011

代碼：

nums=[0]*2022
for i in range(1,1012):
    for j in range(i):
        tmp=i*i-j*j
        if tmp<=2021:nums[tmp]=1
res=sum(nums)
print(res)

題目4

小藍要用01串來表達一段文字，這段文字包含 a, b, c, d, e, f 共 6 個字母，每個字母出現的次數依次為：a 出現 10 次，b 出現 20 次，c 出現 3 次，d 出現 4 次，e 出現 18 次，f 出現 50 次，
　小藍準備分別對每個字母使用確定的01串來表示，不同字母的01串長度可以不相同，
　在表示文字時，將每個字母對應的01串直接連接起來組成最終的01串，為了能夠正常還原出文字，小藍的編碼必須是前綴碼，即任何一個字符對應的01串都不能是另一個字符對應的01串的前綴，
　例如，以下是一個有效的編碼：
　a: 000
　b: 111
　c: 01
　d: 001
　e: 110
　f: 100
　其中 c 的長度為 2，其它字母的編碼長度為 3，這種方式表示這段文字需要的總長度為：103+203+32+43+183+503=312，
　上面的編碼顯然不是最優的，將上面的 f 的編碼改為 10，仍然滿足條件，但是總長度為 262，要短 50，
　要想編碼后的總長度盡量小，應當讓出現次數多的字符對應的編碼短，出現次數少的字符對應的編碼長，
　請問，在最優情況下，編碼后的總長度最少是多少？

答案：219

題解：哈夫曼編碼，作圖如下

按左樹為0，右樹為1編碼：
c: 3 11000
d: 4 11001
a: 10 1101
e: 18 111
b: 20 10
f: 50 0

5*3+5*4+4*10+3*18+2*20+1*50=219

題目5

下面的矩陣中包含 ABCDEF 六種字符，請問出現最多的字符出現了幾次？
　FFEEFEAAECFFBDBFBCDA
　DACDEEDCCFFAFADEFBBA
　FDCDDCDBFEFCEDDBFDBE
　EFCAAEECEECDCDECADDC
　DFAEACECFEADCBFECADF
　DFBAAADCFAFFCEADFDDA
　EAFAFFDEFECEDEEEDFBD
　BFDDFFBCFACECEDCAFAF
　EFAFCDBDCCBCCEADADAE
　BAFBACACBFCBABFDAFBE
　FCFDCFBCEDCEAFBCDBDD
　BDEFCAAAACCFFCBBAAEE
　CFEFCFDEEDCACDACECFF
　BAAAFACDBFFAEFFCCCDB
　FADDDBEBCBEEDDECFAFF
　CDEAFBCBBCBAEDFDBEBB
　BBABBFDECBCEFAABCBCF
　FBDBACCFFABEAEBEACBB
　DCBCCFADDCACFDEDECCC
　BFAFCBFECAACAFBCFBAF

答案：78

題解：哈希表，或者用Counter

from collections import Counter
s = "FFEEFEAAECFFBDBFBCDA\
　DACDEEDCCFFAFADEFBBA\
　FDCDDCDBFEFCEDDBFDBE\
　EFCAAEECEECDCDECADDC\
　DFAEACECFEADCBFECADF\
　DFBAAADCFAFFCEADFDDA\
　EAFAFFDEFECEDEEEDFBD\
　BFDDFFBCFACECEDCAFAF\
　EFAFCDBDCCBCCEADADAE\
　BAFBACACBFCBABFDAFBE\
　FCFDCFBCEDCEAFBCDBDD\
　BDEFCAAAACCFFCBBAAEE\
　CFEFCFDEEDCACDACECFF\
　BAAAFACDBFFAEFFCCCDB\
　FADDDBEBCBEEDDECFAFF\
　CDEAFBCBBCBAEDFDBEBB\
　BBABBFDECBCEFAABCBCF\
　FBDBACCFFABEAEBEACBB\
　DCBCCFADDCACFDEDECCC\
　BFAFCBFECAACAFBCFBAF\\"

cnt=Counter(s)
print(cnt.most_common(1))

控制臺顯示: [('F', 78)]

題目6

小藍要到店里買鉛筆，
鉛筆必須一整盒一整盒買，一整盒 12 支，價格 p 元，
小藍至少要買 t 支鉛筆，請問他最少花多少錢？
輸入格式
輸入一行包含兩個整數 p、t，用一個空格分隔，
輸出格式
輸出一行包含一個整數，表示答案，
樣例輸入
5 30
樣例輸出
15
樣例說明
小藍至少要買3盒才能保證買到30支鉛筆，總共花費 15 元，
評測用例規模與約定
對于所有評測用例，1 <= p <= 100，1 <= t <= 10000，

題解：取整

代碼：

p, t = map(int, input().split())
n = t // 12
if t % 12 != 0:
    n += 1
print(n * p)

題目7

給定一個三角形的三條邊的長度 a, b, c，請問這個三角形是不是一個直角三角形，
輸入格式
輸入一行包含三個整數 a, b, c，表示三角形三邊的長度，相鄰整數之間用一個空格分隔，
輸出格式
如果是直角三角形，輸出“YES”（全大寫），否則輸出“NO”（全大寫），
樣例輸入
3 4 5
樣例輸出
YES
樣例輸入
4 5 4
樣例輸出
NO
評測用例規模與約定
對于所有評測用例，1 <= a, b, c <= 1000，

題解：先排序，再判斷最短兩邊a、b與斜邊c是否能構成直角三角形

代碼：

def check(a, b, c):
    a,b,c=sorted([a,b,c])
    return a * a + b * b == c * c

a, b, c = map(int, input().split())
if check(a, b, c):
    print("YES")
else:
    print("NO")

題目8

n 個小朋友正在做一個游戲，每個人要分享一個自己的小秘密，
每個小朋友都有一個 1 到 n 的編號，編號不重復，
為了讓這個游戲更有趣，老師給每個小朋友發了一張卡片，上面有一個 1 到 n 的數字，每個數字正好出現一次，
每個小朋友都將自己的秘密寫在紙上，然后根據老師發的卡片上的數字將秘密傳遞給對應編號的小朋友，如果老師發給自己的數字正好是自己的編號，這個秘密就留在自己手里，
小朋友們拿到其他人的秘密后會記下這個秘密，老師會再指揮所有小朋友將手中的秘密繼續傳遞，仍然根據老師發的卡片上的數字將秘密傳遞給對應編號的小朋友，
這樣不斷重復 n 次，
現在，每個小朋友都記下了很多個秘密，
老師現在想找一些小朋友，能說出所有秘密，請問老師最少要找幾個小朋友？
輸入格式
輸入的第一行包含一個整數 n，
第二行包含 n 個整數 a[1], a[2], …, a[n]，相鄰的整數間用空格分隔，分別表示編號 1 到 n 的小朋友收到的數字，
輸出格式
輸出一行包含一個整數，表示答案，
樣例輸入
6
2 1 3 5 6 4
樣例輸出
3
樣例說明
最終小朋友 1, 2 互相知道了對方的秘密，小朋友 3 只知道自己的秘密，小朋友 4, 5, 6 互相知道了對方的秘密，
至少要找 3 個小朋友才能說出所有秘密，
評測用例規模與約定
對于 30% 的評測用例，2 <= n <= 30，
對于 60% 的評測用例，2 <= n <= 1000，
對于所有評測用例，2 <= n <= 100000，

題解：構造并查集，判斷最終有幾個連通分支（可以看下我的并查集板子）

代碼：

f={}
def find(x):
    f.setdefault(x,x)
    if x!=f[x]:
        f[x]=find(f[x])
    return f[x]

def union(x,y):
    f[find(x)]=f[find(y)]


n = int(input())
nums = list(map(int, input().split()))
for i,v in enumerate(nums):
    union(i+1,v)

for k in f.keys():
    f[k] = find(f[k])
res=len(set(f.values()))
print(res)

題目9

一個 1 到 n 的排列被稱為半遞增序列，是指排列中的奇數位置上的值單調遞增，偶數位置上的值也單調遞增，
例如：(1, 2, 4, 3, 5, 7, 6, 8, 9) 是一個半遞增序列，因為它的奇數位置上的值是 1, 4, 5, 6, 9，單調遞增，偶數位置上的值是 2, 3, 7, 8，也是單調遞增，
請問，1 到 n 的排列中有多少個半遞增序列？
輸入格式
輸入一行包含一個正整數 n，
輸出格式
輸出一行包含一個整數，表示答案，答案可能很大，請輸出答案除以 1000000007 的余數，
樣例輸入
5
樣例輸出
10
樣例說明
有以下半遞增序列：
　(1, 2, 3, 4, 5)
　(1, 2, 3, 5, 4)
　(1, 2, 4, 3, 5)
　(1, 3, 2, 4, 5)
　(1, 3, 2, 5, 4)
　(1, 4, 2, 5, 3)
　(2, 1, 3, 4, 5)
　(2, 1, 3, 5, 4)
　(2, 1, 4, 3, 5)
　(3, 1, 4, 2, 5)
評測用例規模與約定
對于 50% 的評測用例，2 <= n <= 20，
對于所有評測用例，2 <= n <= 1000，

題解：動態規劃，可以類比下楊輝三角

代碼：

n = int(input())
k = n // 2
dp = [0] * 1001
mod = 1000000007
for i in range(1, n + 1):
    dp[0] = 1
    dp[i] = 1
    for j in range(i-1,0,-1):
        dp[j]=(dp[j]+dp[j-1])%mod
print(dp[k])

題目10

小藍住在 LQ 城，今天他要去小喬家玩，
LQ 城可以看成是一個 n 行 m 列的一個方格圖，
小藍家住在第 1 行第 1 列，小喬家住在第 n 行第 m 列，
小藍可以在方格圖內走，他不愿意走到方格圖外，
城市中有的地方是風景優美的公園，有的地方是熙熙攘攘的街道，小藍很喜歡公園，不喜歡街道，他把方格圖中的每一格都標注了一個屬性，或者是喜歡的公園，標為1，或者是不喜歡的街道標為2，小藍和小喬住的地方都標為了1，
小藍每次只能從一個方格走到同一行或同一列的相鄰方格，他想找到一條路徑，使得不連續走兩次標為 2 的街道，請問在此前提下他最少要經過幾次街道？
輸入格式
輸入的第一行包含兩個整數 n, m，用一個空格分隔，
接下來 n 行，每行一個長度為 m 第數字串，表示城市的標注，
輸出格式
輸出一行包含一個整數，表示答案，如果沒有滿足條件的方案，輸出 -1，
樣例輸入
3 4
1121
1211
2211
樣例輸出
2
樣例輸入
3 4
1122
1221
2211
樣例輸出
-1
樣例輸入
5 6
112121
122221
221212
211122
111121
樣例輸出
5
評測用例規模與約定
對于 50% 的評測用例，2 <= n, m <= 20，
對于所有評測用例，2 <= n, m <= 300，

題解：DFS深度優先搜索，但是注意一定要剪枝，不然一定會導致迭代次數過多，關于深搜，可以看下我的DFS板子

代碼：

n, m = map(int, input().split())
grid = []
for _ in range(0, n):
    tmp = [int(x) for x in input()]
    grid.append(tmp)

road=[(0,1),(0,-1),(-1,0),(1,0)] # 上下左右
inf=0x3f3f3f    # 無窮大
seen = [[0]*m for _ in range(0, n)]
temp = [[inf]*m for _ in range(0, n)]
res = [inf]     # 不能直接用res=inf記錄，可以想想為什么

def dfs(x, y, step, t):
    if x == n - 1 and y == m - 1:
        res[0] = min(res[0],step)
        return

    if step < temp[x][y]:
        temp[x][y] = step
    else:  # 剪枝，非最優路徑提前結束搜索
        return

    for dx,dy in road:
        tx,ty=x+dx,y+dy
        if tx in(-1,n) or ty in (-1,m):continue
        if seen[tx][ty]:continue

        if grid[tx][ty] == 2:
            if t == 1:continue  # 剪枝，遇到2次街道
            if step == res[0]:continue  # 剪枝，因為繼續搜索得到的路徑一定更大
            seen[tx][ty] = 1
            dfs(tx, ty, step + 1, 1)
            seen[tx][ty] = 0
        else:
            seen[tx][ty] = 1
            dfs(tx, ty, step, 0)
            seen[tx][ty] = 0

seen[0][0] = 1
dfs(0, 0, 0, 0)
if res[0] == inf:
    print(-1)
else:
    print(res[0])

經驗之談

• 藍橋杯與acm等競賽相比，難度較低，題目多為暴力、思維和搜索，并且有騙分的可能，建議可以多總結下騙分技巧（bushi），

• 暴力寫得好，動態規劃再熟悉下，python省一就差不多，搜索和剪枝寫得好，python國二也不是夢，

• 起步建議做codeforces的div2的ab題，也可以結合力扣里相應的tag刷熟相應資料結構和演算法技巧，如前綴和，并查集等，這里我也總結了一些板子

• 書籍的話不推薦劉汝佳演算法競賽入門經典，可以看看挑戰程式競賽（白書）

• 對于入門者來說，自己看書學可能會有一點點難度，這里推薦acwing，有藍橋杯歷年題可以提交評測，并且拿獎還可以返還學費（國獎全返哦~）