結果填空

空間

256*1024*1024*8/32=67108864

卡片

n=1 #卡片1所用數量
x=1
while n<2021:
    x+=1
    n+=str(x).count("1")
if n == 2021:
    print(x)
else:
    print(x-1)
#3181

直線

這題的話借鑑大佬的思路，用兩點式直線方程：
(y1-y2) * x +(x2-x1) * y +( x1 * y2 - x2 * y1)=0

最後算出的結果是Ax+By+C=0的格式，只要約分後的A、B、C不相同即可視為不同直線

lt=[]
for i in range(20):
    for j in range(21):
        lt.append((i,j))
def gcd(x,y):
    if y==0:
        return x
    return gcd(y,x%y)

out=set()
for i in range(len(lt)-1):
    x1,y1=lt[i]
    for j in range(i+1,len(lt)):
        x2,y2=lt[j]
        A=y1-y2
        B=x2-x1
        C=x1*y2-x2*y1
        k=gcd(gcd(A,B),C)  #最大公約數
        out.add((A/k,B/k,C/k))
print(len(out)) 
#40257

貨物擺放

import math

n=2021041820210418
lt=set() #集合會比列表更快
out=0
for i in range(1,int(math.sqrt(n))+1):
    if n%i==0:
        lt.add(i)
        lt.add(n//i)
for i in lt:
    for j in lt:
        for k in lt:
            if i*j*k ==n:
                out+=1
print(out)
#2430

路徑

開始想用Floyd解法，發現要跑很久，後面參考大佬部落格學習了一下DP(動態規劃)。

思路：

lcm(x,y)函數用於返回x和y的最小公倍數
列表out中存放最短距離，例如out[i]是從節點1到節點i的最短距離，當i在[1,22]範圍時，out[i]=i.
但是從i=23開始，就有out[i]=min(out[i-1]+lcm(i-1,i),out[i-2]+lcm(i-2,i),…out[i-20]+lcm(i-20,i),out[i-21]+lcm(i-21,i))
以此類推，一直算到out[2021]即可

out = [0]*2022

def gcd(x,y): #最大公約數
    if y==0:
        return x
    return gcd(y,x%y)
def lcm(x,y): #最小公倍數
    g=gcd(x,y)
    return x*y//g

for i in range(1,2022):
    d = 21 #間隔
    if i < 23:
        out[i] = i
    else:
        out[i] = out[i-d] + lcm(i-d,i) 
        while d:
            if out[i-d]+lcm(i-d,i) < out[i]:
                out[i] = out[i-d] + lcm(i-d,i)
            d -= 1   

print(out[2021])

程式設計

時間顯示

n=input()
x=int(n[:-3])%(3600*24)
h,d=divmod(x,3600)
m,s=divmod(d,60)

print("{}:{}:{}".format(str(h).zfill(2),str(m).zfill(2),str(s).zfill(2)))

砝碼稱重

我最初的想法是給每一個砝碼品質分配一個係數k，k的值是[1,0,-1]的其中之一，每一個品質乘上係數k之後放在同一側，看共有多少個可能性，但是太繁瑣了…

看了下大佬們的思路發現這題也可以DP，思路就是定義二維陣列f[i][j]，i是砝碼數量，j是總重量，如果用i個砝碼可以稱出重量j，則f[i][j]=1。每加入一個新砝碼(重為x)，則有：

f[i][x] = 1
同時若用i-1個砝碼可以稱出重量j，則用i個砝碼也可以稱出重量j，即f[i][j] = f[i-1][j]
在已有組合的基礎上，在天平左右各放一次新砝碼，即f[i][j+x]=1、f[i][abs(j-x)]=1

最後統計f[n-1]中1的個數即可，最後兩個測試點超時了

n=int(input())

count=0
_max = 0 #能稱出的最大重量
a=list(map(int,input().split())) #存放每個砝碼的品質
for i in a:
    _max += i
    
f = [[0]*2*_max for i in range(n+1)] #用於dp的陣列
f[0][a[0]] = 1 #f[i][j]的值為1代表用i個砝碼可以稱出品質j

for i in range(1,n):
    x = a[i] #當前加入砝碼的品質
    f[i][x] = 1
    for j in range(1,_max+1):
        if f[i-1][j]:
            f[i][j] = f[i-1][j] #i-1個砝碼能稱出的品質i個砝碼也可以
    for j in range(1,_max+1):
        if f[i-1][j]: #在前一狀態的基礎上進行新砝碼的擺放
            f[i][j+x]=1
            f[i][abs(j-x)]=1
            
#統計
for i in range(1,_max+1):
    if f[n-1][i]:
        count += 1
print(count)

楊輝三角形

自己寫老是超時，參考y神部落格寫的，大佬的思路真的強…

n=int(input())

def c(a,b):
    res = 1
    i = a
    for j in range(1,b+1):
        res = res * i / j
        if res > n:
            return res
        i -= 1
    return res
def check(k):
    l = 2 * k
    r = max(n,l)
    while l<r:
        mid = l + r >>1
        if c(mid,k) >= n:
            r = mid
        else:
            l = mid +1

    if c(r,k) != n:
        return False
    print(int(r*(r+1)/2+k+1))
    return True

for i in range(16,0,-1):
    if check(i):
        break

括號序列

可以用DP做，合法的括號序列需要滿足兩個條件：

1.左右括號數相同
2.任意字首中左括號數不小於右括號數

結合這兩個條件，可以先用count來表示左括號比右括號多多少個，遍歷一遍括號序列，當遇到左括號，count+=1，否則count-=1。當count<0時不滿足第二個條件，需要新增一個左括號，同時count+=1，最後得到count的值就是需要新增右括號的個數。

然後定義二維陣列f[i][j]為前i個括號中，左括號比右括號多j個的方案數.因而有f[i][j]=f[i-1][j+1]+f[i][j-1]

具體思路看y神部落格