2020藍橋杯省賽第二場Python組題解（不太全，有的不會，有的不記得了）

A 門牌制作

題目描述：

大概就是說制作門牌號是一個一個數字網上貼的，比如1017需要2個1，1個0，1個7，然后問你制作1到2020一共需要多少個數字2

結果：624

題解：

# 沒啥好說的直接字串查找
s=0
for i in range(1,2021):# 遍歷1到2020
    s+=str(i).count('2')# 查找有多少個2
print(s)

B 2020？

題目描述：第二題好像是數2020個數那個吧？

就是給你一個300*300的2和0的字串，問你他包含多少個2020（這個不能用count的，因為202020是2個）

只能從左往右橫著數或者從上往下豎著數，或者從左上往左下謝著數

比如下面這個有7個，橫著1個，豎著3個，斜著3個，

2 0 2 0 0 2
0 0 0 0 2 0
0 0 2 0 2 2
0 0 0 0 0 0
0 0 0 0 2 0
0 0 0 0 0 0
（我空格是為了方便查看，真實的里邊沒有空格，）

結果： 這誰記得啊，我又沒有他的資料，嗚嗚嗚

題解：

# 這題，這題我是把它橫著拆成1個串列，豎著拆1個，斜著拆1個，，還挺費時間的，
def count(s):
    s1=0
    for i in range(3,len(s)):# 0,1,2,3->1,2,3,4一個個的排查
        if s[i-3:i+1]=='2020':s1+=1# 字串切片s[0:4]就是0,1,2,3
    return s1

with open("2020.txt",'r')as f:
    a=f.readlines()# 橫著的數列
    n=len(a)# n行
    for i in range(n):# 因為他最后是帶一個\n符的，我把它消掉，
        a[i]=a[i][:-1]
    m=len(a[0])# m列
    b=['' for i in range(m)]# b來豎著存這些數，所以有列條字串
    for i in range(m):
        for j in range(n):
            b[i]+=a[j][i] # b[0]+=a[0][0]、a[1][0]、a[2][0]、...
    c=[]# 斜著的最麻煩了，，我的辦法是以對角線為分界，寫兩個回圈，
    for i in range(n-1,-1,-1):# 打算先從左下角找到左上角
        s=''
        for j in range(n-i):# 每次只添加n-i個，即從1個到n個長度遞增（因為長寬相等）
            s+=a[i+j][j]# 也就是第一次(n-1,0)，第二次(n-2,0和n-1,1)
        c.append(s)
    for j in range(1,n):# 換j從0到n遍歷了，i初始不變
        s=''
        for i in range(n-j):
            s+=a[i][i+j]# (0,1)(1,2),...,(n-2,n-1),(0,2)(1,3),...,(0,n-1)
        c.append(s)
    s=0
    for i in a:
        s+=count(i)
    for i in b:
        s+=count(i)
    for i in c:
        s+=count(i)
    print(s)# 把3個串列都遍歷一遍，找出所有2020，用我上面那個例子就是輸出7沒錯啦！

C 蛇形數列

題目描述：

數列大概長這樣：就是右走2個，然后斜著走到頭，再下走2個，然后斜著走到頭，再右走2個，…回圈

1  2  6  7 15 16 ..
3  5  8  14 17 ..
4  9  13 18 ..
10 12 19 ..
11 20 ..
21 .. 
..

然后問你，第20行第20列是啥，（下標從1開始）

結果：761（我咋好像當時填的685，難道我還填錯了？哭、、了）

題解：

# 我真的是一點點模擬的他怎么走找的啊，后來聽他們說有規律，
# 就是[1][1]是1，[2][2]是5，[3][3]是13，[4][4]是25你會發現1和2差4，2和3差8，3和4差12，，，
# 因為i和j相同簡化成一維，于是有dp[1]=1,dp[i]=dp[i-1]+4*(i-1)
dp=[0,1]
for i in range(2,21):
    print(i-1,dp[-1])
    dp.append(dp[-1]+4*(i-1))
print(len(dp)-1,dp[-1])

D 跑步訓練

題目描述：

一個小孩，從2000年1月1日到2020年10月10日每天都跑1千米，而周一或月初（每月1號）他會跑2千米，如果既是周一也是月初也是跑2千米，問他一共跑了多少千米，

結果：8879

題解：

# 這題我也哭死啊，都算出來周一或月初一共有多少天了，直接交了，忘了加每天都要跑的1km了，，，（但愿是我記錯了，嗚嗚嗚）
# 哦，這里說一個小技巧，你可以用dir(datetime)來查看他的方法和類啥的，
# 還有idle的help里有一個python doc也是可以打開的，（我就是現查的datetime類的使用方法查了好久，導致忘了題目，嗚嗚嗚）
from datetime import datetime as dt
from datetime import timedelta as td
time1=dt(2000,1,1)# 創建起始時間物件
time2=dt(2020,10,1)# 創建結束時間物件
day=td(days=1)# 創建增加一天用的物件，（注意這里是td，是timedelta）
s=0
while time1<=time2:# 時間是可以直接比較的
    if time1.day==1 or time1.weekday()==0: s+=1# weekday()是方法，[0-6]，day是屬性
    s+=1# 不是特殊的也要加1，我當時好像忘加了嗚嗚嗚
    time1+=day# datetime物件只能與timedelta物件進行運算，回傳datetime物件，
print(s)

E 排序，還是叫什么來著

題目描述：

就是他說如果只交換相鄰的元素的話，冒泡排序的交換次數是最少的，比如lan只用交換a和l，就是1次，

然后讓你找排序時要交換100次的最短的字串中字典序最小的那個，然后他把可以有重復元素那句刪了，（我不知道是不是代表不能有重復元素）

結果：這題我不會，把我的發一下吧，找了長度15的一個字串，

jonmlkihgfedcba

題解：

瞎試的沒題解，

F 統計成績？

題目描述：

前兩道簡單編程題我都沒啥印象了，可能順序也搞混了，這題就是，60分及以上及格，85分及以上優秀，讓你求及格率和優秀率，輸出的時候要65%這種格式，四舍五入，

題解：

n=int(input())# n個學生
su,ji,you=0,0,0# 三個統計
for i in range(n):
    x=int(input())
    su+=1
    if x>=60: ji+=1
    if x>=85: you+=1
print(f'{ji*100/su:.0f}%')# 我用格式化字串輸出的，
print(f'{you*100/su:.0f}%')

G 單詞分析

題目描述：

哈哈哈，看了隔壁Java組題解想起來這道題了，（果然Python，Java，C組的題目重合率很高23333）

言歸正傳，這道題的大意就是統計一個只包含小寫字母的字串中出現最多的是哪個，并輸出次數和字母是誰，次數相同的話輸出字典序最小的，

樣例：

輸入：
lanqiao
輸出：
2
a
輸入：
longlonglongistoolong
輸出：
6
o

題解：

s=input()
m1,m2=0,0 # m1代表最多的次數，m2代表對應的字母
for i in range(25):
    c=chr(97+i) # 遍歷a-z
    t=s.count(c) # 查找字母出現的次數
    if t>m1: # 這里要大于才可以，等于也不換，才能保證是字典序最小的，
        m1=t
        m2=c
print(m1)
print(m2)

H 撿水果還是啥的？

題目描述：

就是一個小孩一層層地撿水果，每層只能往左下和右下最近的那個走，問最多能撿幾個，往左走和往右走的次數相差不能超過1，哎，這題也挺可惜的，我當時沒讀懂題，，還寫了賊久，，

樣例（我自己編的）：

輸入：
4
7
9 10
9 6 9
2 6 10 9
輸出：
36
提示：
左走就是往下，右走就是往右下，
樣例是右右下7+10+9+10=36，

題解：

因為沒讀懂題這題我糾結了好久，比完賽才做出來這道題，，，

# 下面會同時寫遞回版（超時）和動態規劃版兩種解法，（遞回版用來對拍判斷正確與否的）
ss=0
def dfs(i,j,l,r,s):
    # 遞回出口：如果到了最后一層
    if i==n-1:
        # 如果左走右走次數相差超過1，直接回傳
        if abs(l-r)>1: return
        # 否則，ss取較大的那個，（因為s從0開始，所以每次要加上a[i][j]）
        global ss
        ss=max(ss,s+a[i][j])
        return
    # 遞回左走和右走的情況，左走就是i+1，j不變，l+1,
    dfs(i+1,j,l+1,r,s+a[i][j])
    # 右走就i+1，j也+1，r+1.s統一都要加a[i][j]，代表到當前這一步的總和，（而不是到下一步的和）
    dfs(i+1,j+1,l,r+1,s+a[i][j])

# 用的是自造的例子，最大n為100
for ww in range(16):
    with open(f"{ww+1}.in",'r')as f:
        # --------錄入資料
        n=int(f.readline())#int(input())
        a=[[] for i in range(n)]# 初始化n個串列
        for i in range(n):# 每個串列直接繼承每一行的輸入（好像直接等于也成，捂臉）
            a[i].extend([*map(int,f.readline().split())])#([*map(int,input().split())])
        # --------計算結果
        # 遞回版解法，暴力對拍用，到我的第4個例子就算不動了，大概也就到n=三四十吧？
        # 每次到最后一層的時候比較ss和結果誰大，ss取大的，最后輸出ss，
        # ss=0
        # 5個引數分別是i,j,l,r,s.i和j是坐標，l和r是左右走的次數，s是和的結果，
        # dfs(0,0,0,0,0)
        # print(ss)
        # 下面是動態規劃版解法
        # 初始化一個形如[[0],[0,0],[0,0,0],...]的dp陣列
        dp=[[0 for j in range(i+1)] for i in range(n)]
        dp[0][0]=a[0][0] # 起點是a[0][0]
        # 遍歷每一層
        for i in range(1,n):
            # 如果j是0的話，只可能是從上一層的0走下來的，所以直接dp[i-1][0]+a[i][0]就是這層結果了，
            dp[i][0]=dp[i-1][0]+a[i][0]
            # 之后j遍歷[1,i-1]
            for j in range(1,i):
                # 這個時候，就有兩種可能了，可能是左上往右走下來的，也可能是正上往左走下來的，
                # 就要比較得出他們中較大的那個再加a[i][j]，
                dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+a[i][j]
            # 同樣每層的最后一個只可能是上一層最后一個走下來的，
            dp[i][i]=dp[i-1][i-1]+a[i][i]
        # 你可能會想，如果這樣的話，到最后一層的時候，你怎么知道他是左右各走了幾次呢？
        # 這個其實是又規律的，因為他左右相差不能超過1，所以他最多只可能走到下面的兩個點，
        # 還要分n是奇數還是偶數，如果n是奇數，他左走和右走的次數是一樣的，（因為第一層是0步嘛）
        # 所以此時他只可能走到dp[-1][n//2]，（因為左走j不變，右走j+1，右走一半次，無論如何都是走到中間，）
        if n%2: print(dp[-1][n//2])
        # 而如果n是偶數的話，只可能是左走多一次或者右走多一次，右走多一次就是n//2，右走少一次就是n//2-1
        else: print(max(dp[-1][n//2],dp[-1][n//2-1]))

I （未解）平面切割？

題目描述：

好像是給你幾個k和b，y=kx+b啥的嘛，然后讓你判斷這幾條線會把平面分成幾部分，

這題我沒有思路，也沒時間了，

J （未解）怪物獵人？（名字肯定不叫這個）

題目描述：

太長了，記不清，

題解：

記不清了，只記得最后幾分鐘勉強寫出了一個缺億點細節，但是能過樣例的答案，