o079. 4. 最佳選擇

 題目描述：

給一個長度為 n 的正整數序列 a1,a2...an ，你可以執行多次操作 (包含 0 次)，每次操作只能選擇這個序列的第一個或最後一個數字，再將這個數字從序列中刪除並自己搜集起來。

求滿足總和不超過 k 且搜集的數字奇數和偶數個數相同的條件下，所能搜集的數字總和最大為多少。

這題步驟比較多，簡單來說，怎麼選都是前面選幾個，後面選幾個，將總和加起來，所以第一步要先得出前後綴和。：

假設測資a1...an分別是1,2,3,4,5,6

1.先算出前後綴和pre = [1,3,6,10,15,21] , ends = [6,11,15,18,20,21]，

再來就是前後綴合的組合囉，想法是這樣，我們取出pre[0]去跟ends的每一個結合看看，可以結合的標準是範圍不重複，且奇偶數個數相同，且總和不超過k，的可能中求最大，先別管時間問題了，光要做這件事情，我們就必須在算前後綴和時，順便紀錄了每一個前後綴合的奇偶數個數，我把前綴和記錄成這樣：

pre = [[0,0],[1,-1],[3,0],[6,-1],[10,0],[15,-1],[21,0]]，這代表組成21的時候奇偶個數沒差別，15的時候奇偶個數差1。

再來end我記成這樣：

endIndex = {1: [-5, -3, -1], 0: [-4, -2, 0]}

endSum = {1: [6, 15, 20], 0: [11, 18, 21]}

代表偶數比奇數多一個的後綴和有6,15,20其最左邊的資料在第5,3,1個位置，解釋一下，以20為例，20是2,3,4,5,6相加的結果，其中，偶數多奇數一個，且資料起始位置是1(2在a的第一個位置)，補充一下，為什麼5,3,1記成-5,-3,-1，因為我希望保持結構是升序排序，那麼我後面做二分搜的時候比較容易。

所以有了pre,endIndex,endSum之後該怎麼做呢，依樣，依序取出pre的每一個資料，假設拿到pre[1]，那麼因為pre[1]又等於[1,-1]，其中1代表前綴和是1，1代表取到第一個位置，-1代表奇偶差是1，所以我們要的資料就是在endIndex[1],endSum[1]之中，那要怎麼快速找到位置不重複，且相加小於k的資料呢，這邊我們就是用二分搜了，我很懶，直接用工具了。

上面這段說明，記得跟一下文字的標色，會比較好閱讀。

以下是完整程式碼：

import bisect
n,k = [int(i) for i in input().split()]
d = [int(i) for i in input().split()]

pre = [[0,0]]
for i in range(0,len(d)):
    if d[i] % 2 == 0: 
        p = 1
    else:
        p = -1
    last = pre[-1]
    pre.append([last[0]+d[i] , last[1]+p])
    
ends = 0
endoe = 0
endSum = {}
endIndex = {}
for i in range(len(d)-1 , -1 , -1):
    if d[i] % 2 == 0: 
        endoe += 1
    else:
        endoe += -1
    ends += d[i]
    if endoe in endSum:
        endSum[endoe].append(ends)
        endIndex[endoe].append(-i)
    else:
        endSum[endoe] = [ends]
        endIndex[endoe] = [-i]
#print(pre)
#print(ends)
#print(endIndex)
#print(endSum)
ans = 0
for i in range(n+1):
    p = pre[i][1]
    if pre[i][0] > ans and p == 0 and pre[i][0] <= k:
        ans = pre[i][0]
    if -p in endSum:
        #print('endSum[-p]' , endSum[-p] , pre[i][0] , k - pre[i][0])
        q = bisect.bisect_left(endSum[-p], k - pre[i][0]+1)#找與pre[i][0](前綴)相加小於k的資料位置
        if q > 0:
            #print(pre[i][0] , endSum[-p][q-1])
            q = bisect.bisect_left(endIndex[-p][0:q],-i)#找到所有相加符合標準中，起始位置最左邊的後綴合(後綴起始位置越左邊越大)
            if q > 0:
                #print(q)
                ans = max(ans , pre[i][0] + endSum[-p][q-1])
                #print(ans)
        
print(ans)

o077. 2. 電子畫布

題目描述：

有一個 H ╳ W 的電子畫布，一開始數值都是 0 代表未填色，接下來請模擬 N 次畫筆操作。

每次畫筆操作為選一個座標 (r,c) 停留 t 秒，他會將曼哈頓距離 <= t 的區塊染上顏色 x。若有多個顏色重複填到相同區塊，顏色的數值會累加起來。

請輸出 N 次操作後的畫布狀態。

這題簡單來說就是要想個找出距中心點等距的菱形座標。

我思考的方式很簡單，首先找到中心點，並根據該點的資料找出他離他最遠單的Y座標端點。

得到,以下這個迴圈。

for y in range(r-t,r+t+1):

注意一下，菱形的關鍵就是從中心點到任一端點都是等距，所以我們先把中心點座標取這次拿到的Y座標算出差距得到：

ydif = abs(r-y)#ydif就是中心點與這次y座標的差距

已知ydif+xdif=t，現在t跟ydif都是已知，所以xdif = t-abs(ydif)，所以就可以得出下面這個迴圈：

for x in range(c-(t-ydif) , c+(t-ydif)+1):

菱形矩陣搞定後，這題就沒有其他問題囉，以下是完整程式。

def t():
    h,w,n = [int(i) for i in input().split()]
    tt = [[0 for i in range(w)] for j in range(h)]
    
    
    for j in range(n):
        r,c,t,q = [int(i) for i in input().split()]
        for y in range(r-t,r+t+1):
            if y < 0 or y > h-1: 
                continue
            ydif = abs(r-y)
            for x in range(c-(t-ydif) , c+(t-ydif)+1):
                if x < 0 or x > w-1:
                    continue
                tt[y][x] += q
    for i in tt:
        for j in i:
           print(j , end = ' ')
        print()
t()

o076. 1. 特技表演

有一個城鎮有 n 棟高樓，樓高分別為 h1,h2,.....hn，市長想要在城鎮中心舉辦高空特技表演，該特技表演會從某棟大樓上朝右側滑翔至地面。

為了表演人員的安全，滑翔的路徑樓高必須越來越低，請你找出一個最長的滑翔路徑。

簡單來說就是要從資料中找出最長的降冪集合，這題沒什麼時間問題，直接透過迴圈查找

def t():

    n = int(input())

    d = [int(i) for i in input().split()]

    c = 0

    k = 9999999999

    ans = 0

    for i in d:

        if i < k:

            c += 1

        else:

            if ans < c:

                ans = c

            c = 1

        k = i

    if ans < c:

        ans = c

    print(ans)

t()

o078. 3. 缺字問題

 題目敘述：

給定一個大小為 K 個字母的集合和字串 S，求出在使用該集合所組出長度為 L 字串中，不為字串 S 子字串的最小字典序字串為何。

自如字母集合{a,c,m}，其能組出長度為 2 的字串字典序由小到大排序為： aa < ac < am  < ca < cc < cm < ma < mc < mm。字串 S 為accaamcm，因此 ma 為不在 S 內的最小字典序字串。

這題看起來就很dfs，一般APCS第三題時間上是不會過關，但這題可以，想必官方考慮到國高中生期末考將至，難度有稍微調降了。簡單來說，想辦法求出a,c,m中不重複的所有排序組合。

以下是超白話思考順序

DFS思考的重點有兩個，每次要做什麼，終止條件是什麼。

啥都還沒想到的時候就先寫出

def dfs():#先把函式建起來

再來開始思考每次呼叫函示要做什麼，以這題為例，我們要嘗試在函式內組出不同的字母排列組合，所以應該需要一個字串參數帶入函式之中。所以：

def dfs(s):

有了參數後，可以想想看終止條件是什麼，終止條件就是組出長度為L的字串，所以：

def dfs(s):

    if len(s) == L:

        dosomething

長度到了之後呢，我們程式的目標是要找出不在字串S中的子字串啊，所以：

def dfs(s):

    if len(s) == L:

        if s not in S:#代表s不在S之中

            print(s)

            return False#不要繼續找了

        return True#繼續找吧

    for i in k:

        if dfs(ss+i) == False:

            return False

k = list(input())

l = int(input())

S = input()

dfs("" )

再加上剪枝(優化加速)，就變成以下這樣囉：

def dfs(ss):
    if ss in dic:
        return True
    dic[ss] = 1
    if len(ss) == l:
        if ss not in existStr:
            print(ss)
            return False
        return True
    for i in k:
        if dfs(ss+i) == False:
            return False

k = list(input())
l = int(input())
s = input()

existStr = set(s[i:i+l] for i in range(len(s) - l + 1))
dic = {}
dfs("" )

我把剪枝(用來加速)的部分標藍色，基本上這題不剪枝，也不會超時，非常佛心呢。