APCS
peienwu
thanksone
Wed, Sep 8, 2021 3:40 PM
總共有ABC三種規則,就每一種都比對一次就可以了!
時間複雜度: 共有 組對聯,每一組都 檢查,時間 。(不過n最大也才50,不論什麼複雜度都可以吧)
這一題是去模擬每一個魔王移動的狀況,要特別注意每一輪的國王是同時移動的,沒有先後順序,也就是說一顆炸彈可以炸掉不只一位魔王,如果有多個魔王移動到同一個格子,則他們會一起被炸掉。
時間複雜度: 有點難估計,因為很難確定每一個魔王的移動狀況次數,不過由於數字範圍不大,且 只有到500,因此直接做複雜度是可行的。
以區間最小值作為區分點將數列分成兩半,可以利用線段樹找區間最小值,利用迴圈模擬每一次範圍縮小的情況。
不過這一題比較特別,他的區間範圍一定會越來越小,且區間外的數字也就不需要使用到,因此可以將數列做一次排序,從頭開始找如果遇上區間外的數字則不理他,否則使用它當作區間的分隔點(這一定會是最小值,因為由小到大排序),將區間範圍縮小。
至於挑選左右區間的區間和,則可以透過前綴和 算出答案。
時間複雜度: 如果是一個遞增或遞減的序列,則每一次區間大小只會縮減1,此時複雜度為 ,加上最一開始的排序是 ,總共為 。
如果用線段樹實作,尋找區間最小值,可以在 的時間內詢問。在最差的情況下,一共會詢問 次,因此總時間複雜度一樣是 。實作上也不複雜,建立線段樹以及區間詢問,區間修改和懶標之類的東西。可以比較一下時間:
線段樹的表現稍微好一點,不過其實是相當接近的!
有一種二元樹,我也不知道叫啥,根為全序列最小值,左節點為左邊序列最小值,右節點為右邊序列最小值。
thanksone
紀錄每個位置左、右邊離自己最近、比自己小的,爸爸就是兩個之中比較大的那一個。
thanksone
時間複雜度: 種樹加跑答案總共
thanksone
如果把範測的笛卡爾樹具象化,大概長這樣:
8
3 9 4 5 1 6 2 8
大致步驟就是:
總共有三個不同的作法,使用到排序、線段樹、笛卡兒樹的作法。其中,他們的間複雜度分別是 、、。
在笛卡兒樹的作法中,對每一個數字尋找兩側第一個小於它的數字(這可以用單調隊列完成),之後把每一個數字的父親節點設為找到的兩端數字中較大的那一個。
此作法的概念是,假設序列中第 個數字找到兩側數字分別是 以及 ,當他如果是區間最小時,區間必須在 之中,否則它就不會是最小值了。
至於為何是選擇 當做父節點?則是因為如果選擇較小的那一個,在縮小區間範圍後,無法確定另外一個是否在區間外,如果包含區間內,則 便不會是最小值,違反了定義。換言之,選擇了較大的那一個當作父節點,按照定義當走到這個父節點時,它是區間的最小值,將它排除之後, 就會是下一個區間的最小值!
對於序列中k個連續的區間,每一個區間滿足區間內的元素皆不重複,區間範圍可以重疊(不過重疊部分只會算一次),找出這k個連續區間所能覆蓋到的最大長度。
感覺跟背包問題的概念有點像,n個物品可以對應到k個區間,重量則對應到這裡的序列中的數字。這題用DP解。
定義 為 個試吃員,看了前 個攤位,最多可以吃到幾個攤位。
維護一個函數 表示如果試吃員吃了第 個攤位的美食,他所能吃到最左端的攤位的索引值。也就是說,試吃員可以吃 到 攤位的美食。
轉移式代表了要使用第 的攤位作為右端點,或是不要使用(直接用前一個),取兩者的最大值。後面一串加減是計算區間大小
從轉移式可以看到他空間可以用滾動DP優化!
GREEDY的作法?
如果每一次都選擇最大的區間,並將這個區間的值都改成0,做7次,得到答案,是正確的做法嗎?
最大的區間不一定會被完全選到。以下測資:
12 2
5 4 3 2 1 3 4 5 6 4 3 2
如果是Greedy會選擇 ,然後從兩邊挑一邊。答案是 。
但是用DP做會是 加上 ,答案是 。
thanksone
時間複雜度: 兩層迴圈總共是
熟悉的題目,大的感人的k。如果依照上面的做法肯定TLE。
俗話說得好 : "好的DP定義是AC的一半"
因此經過一系列通靈,我們得到了一個非常漂亮的定義
thanksone
必須選第 家,能吃最多的攤販數量,需要的人數是一個
thanksone
維護一個函數 ,其實就是樓上的 ,但是我比較想要叫他
thanksone
Aliens優化 : 利用penalty限制人數
每當有一個人加入,便扣除 個攤販的業績
當總人數超過 ,表示 不夠大,仍然有太多人利大於弊
反之,當總人數小於 ,表示 太大,有太多人弊大於利
看出來了嗎? 可以二分搜喔!
thanksone
時間複雜度: 二分搜加每次DP
感謝 東霖
幫忙抓bug
thanksone