某 M 現在正在平面座標上的原點 $(0, 0)$，現在四周被擺放了很多很多鏡子，某 M 可以藉由鏡子與他的人格小夥伴對話，請問那些鏡子可以見到小夥伴。
鏡子可以當作一個線段，線段之間不會交任何一點，只要能見到該鏡子中一小段區域就算可見到。
備註：不考慮反射看到，保證鏡子不會通過原點。
|
|
|
|
對於每一個線段，可以化作極角座標上的一個角度區間$[\theta_{start}, \theta_{end}]$，做一次極角排序，維護從原點射出的射線，找到該射線交到的所有角度區間，意即維護射線和線段交的最近距離，用一個平衡樹 set<Seg> 維護。由於線段之間不會相交，平衡樹靠遠近當作權重比較，遠近關係是單調的，故不影響插入和刪除。若發生遠近問題可採用 multiset<Seg> 來進行。
由於每一個線段可能拆分好幾個可視線段，而大多數的線段全是不可視的，可以考慮分治去處理，但我的實作效果並不好，其原因在於並沒有維護極角的 skyline，而是保留整個線段。
|
|
|
|
給定一個有根樹，詢問兩個節點 $(u, v)$ 的距離，點數最多 $V = 2000000$。
|
|
|
|
明顯地不可能使用 LCA-RMQ 的 $O(Q \log V)$ 在線詢問，要套用 tarjan 算法中的 Offline-LCA，但 tarjan 算法靠的是遞迴遍歷，在 V = 20000000 很容易發生 stackoverflow，為了解決這一點採用非遞迴的方式實作。
這一題還有特別卡的地方，有向邊的儲存，之前 tarjan 都用在無向樹上，所以普遍都會儲存 $2 E$ 條邊，這一題必須只儲存 $E$ 條邊，常數卡得緊，不掛上優化輸入時間限制是在 TLE 邊緣。
|
|
影像處理中，給定一張圖，準確地找到點、線、邊、角都是相當困難的，由於圖片會受到干擾、顏色屬性的差異，使得擷取特徵相當困難。
對於 $N \times M$ 的像素圖片，方便起見只由黑白影像構成，0 表示暗、1 表示亮，對於每一個像素位置判斷是否可能是角點。
在角點偵測的算法中，有一個由 Rosten and Drummond 提出的 FAST (Features from Accelerated Segment Test) 方法。概念由一個 $7 \times 7$ 的遮罩，待測點 $p$ 位於遮罩中心，由遮罩內圈上的 16 個像素的灰階判斷 $p$ 是否為角點。遮罩樣子如下所示：
|
|
只要這個圈上出現連續大於等於 12 個相同的暗像素或者是亮像素，則 $p$ 就被視為一個角點。
不幸地，這會造成在一個角上出現很多角點，通常會根據掃描的順序找到角點，當找到一個角點後，會抑制鄰近區域不可以是角點。此題不考慮抑制情況，對於每一個角點必須在 16 個像素在圖片上才進行判斷，圖片邊界不進行偵測。
輸出一個 $N \times M$ 的矩陣，按照原圖片位置，若該點是角點則為 1，反之為 0。
|
|
|
|
這一題的技巧不是演算法，而是實作的加速細節。
同時，來實驗老師上課說的優化策略的用處，由於要連續 12 個，根據鴿籠原理的方式，挑選位置 1, 5, 9, 13 出來，若連續三個狀態相同再進行 $O(16)$ 的判斷。然而挑出這四個位置，可以加速 50%，相較於只有 $O(16)$ 的判斷效能，可以參考下方的樸素解。
樸素寫法並不是最快的，因為 branch 太多，導致速度至少為 800ms，去處理一張 $1920 \times 1080$ 的影像，更好的方案是使用 bitmask，預處理在 16bits 下，連續 9 個相同狀態的位元情況，搭配 loop unrolling 的方式去撰寫，直接 $O(16)$ 判斷，為了減少代碼量，採用巨集的前處理展開。請參考 bitmask 版本。速度來到 140ms，加速幾乎 8 倍。
單純的 bitmask 還不是最快，直接建表 $O(2^{16} \times 16)$ 得到 16bits 是否是角點，建表消耗時間，但單一判斷變成 $O(1)$。請參考 bitmask2 版本。速度來到 76ms，直接翻了快兩倍。
最終 bitmask3 版本 56ms，採用以下的方案：
(a&mask) == 0 || (a&mask) == mask) 將只會有 (a&mask) == mask，需要 (a&mask) == 0 的判斷，則先 a = ~a 再進行 (a&mask) == mask。g[x][y] 取址使用時，會動用到一次乘法和一次加法，對於每一個角點偵測，動用到 16 次的乘法運算。若矩陣大小事先已知，那麼對於某一行的角點，g[x] 可以用一次乘法計算，接著該行所有角點偵測，只會剩下 16 次的加法。__builtin_popcount() 提供剪枝。當然，以上變態至極的作法，倒不如樸素解直接開 g++ -O3 或者是 g++ -Ofast 來的省事，速度慢一點也是沒問題的對吧。
|
|
|
|
|
|
|
|
|
|
動畫 遊戲人生《No Game No Life》中，史蒂芙 (Stephanie Dola) 常常被欺負，儘管她以學院第一畢業，對於遊戲一竅不通的她在這個世界常常被欺負。現在就交給你來幫幫她。
兩個人輪流在一個大棋盤上下棋，每一步棋的得分根據這一步棋與最鄰近的敵方棋子的曼哈頓距離。
對於兩個點 $p, q$ 座標 $(p_x, p_y), (q_x, q_y)$，曼哈頓距離 (Manhattan distance) 為 $|p_x - q_x| + |p_y - q_y|$。
|
|
|
|
把鄰近搜索問題做個總結，普遍處理的是靜態資料跟單一詢問，而在最近餐館那一題已經用 KD-tree 處理過 KNN 問題。這一題是採用動態插入和詢問以及數學性質較強的曼哈頓距離，離線處理也是個選擇。
此問題限制在 $n = 50000$ 的情況下，進行測試討論，除了分桶、方格法外，探討三種思路：
Dynamic KD-tree 利用替罪羊樹的概念完成，看著卦長的代碼以及卡車口述概要，終於敲敲打打拼湊起來，掛上啟發式的搭配具有不錯的成效。空間複雜度 $O(n)$，插入複雜度 $O(\log^2 n)$，查詢 $O(\log n)$ (據說是在曼哈頓距離下的緣故)，速度是暴力法 $O(n^2)$ 二十倍左右。
Segment tree + 平衡樹，空間複雜度 $O(n \log n)$，時間複雜度 $O(\log^3 n)$，使用座標轉換將菱形轉換成正方形，套上二分邊長去查找區域內部是否有點。由於 $n$ 的緣故，速度比 Dynamic KD-tree 慢上許多，若用暴力法 $O(n^2)$ 只快兩倍之多。實作測試提供者 liouzhou_101。
離線處理 CDQ 分治，空間複雜度 $O(n)$，總時間複雜度 $O(n \log^2 n)$，採用思路為曼哈頓距離切割成四個象限進行極值查找。比暴力法快十倍所右。
前兩個作法比較裸，在此特別補充 CDQ 分治，曼哈頓距離可以考慮成四個象限，詢問 $(x, y)$ 的最鄰近點，首先考慮左下角 $(x', y')$，亦即 $x' \le x, \; y' \le y$，則曼哈頓距離 $dist = (x - x') + (y - y') = (x + y) - (x' + y')$，明顯地求最近距離要讓 $x' + y'$ 最大化。同理其他象限。
為了解決這詢問，套用 CDQ 分治，按照 $x$ 座標排序，接著二分操作順序，切割操作 $[l, mid], [mid+1, r]$，在左右兩塊仍然按照 $x$ 排序。單獨看 $[mid+1, r]$ 的操作會受 $[l, mid]$ 和自己本身影響，對於前者而言，採用歸併排序那樣，按照 $x$ 座標慢慢合併 (概念上)，合併過程套用 Binary indexed tree 進行極值查找。對於後者，就進行遞迴求解，明顯地 $[l, mid]$ 只會受 $[l, mid]$ 影響。
CDQ 分治的概要，按照其中一個關鍵排序，接著二分操作順序進行分置處理。國外是有論文在描述這個 Online to Offline 的算法，CDQ 命名就是人名，會給國外看笑話吧。
|
|
備註「欸欸，加上悔棋的話，是不是持久化 kd-tree」
關於 kd-tree 實作細節探討，與通常會犯的錯誤，關係到速度有常數差異。
在 closest() 中，常犯的錯誤是 探索順序 ，盡可能先靠近，啟發式才能更加快速，別像我打出錯誤的搜索順序如下：
|
|
實作的順序應該如下，別總是先探訪左子樹、在去探訪右子樹，kd-tree 必須注意順序。
|
|
假設資料大小 sizeof(dim_element) 很大，通常會利用指針陣列來進行排序，這樣可以降低搬運大型資料複製時間，但奇怪的是由於指針陣列佔有一定空間，索引資料時又會佔據一段空間，估計是快取方面出了點問題 (或者是我寫不好)，導致直接搬運資料是來得比較快速，這個修改在 b348. 最近餐館 也有進行測試，速度有提升。
接著可以藉由函數參數少量，來拉快程式在堆疊參數所需要的時間，在節點內部宣告採用維度 d
|
|
這個修改造成詢問時，不僅僅在走訪傳遞參數少了一個，還少 k+1 的計算。測試結果中，光靠這一點速度沒有明顯提升。kd tree 還有一個靠臉吃飯的邊界分割，要是相同時分左分右，這一點是最痛苦的，在此就不去討論，當然可以利用隨機擾動來解決這問題。
至於要使用 sort() 進行 $O(n \log n)$、還是使用 nth_element() 的 $O(n)$ 找到中位數，根據兩題的測試，由於 $n$ 都不大，照理來講 nth_element() 快於 sort()，但根據實際測試於 liouzhou_101 的代碼，sort() 的速度會比較快，其一是運氣、其二是未知情況。就從以下代碼中，差異並不明顯。
沒有提供垃圾回收，靠內存持運作，要是 RE 就放大一點。
|
|
|
|
求出$F_{2^n} \mod m$ 的結果。
|
|
|
|
一般的矩陣計算，利用 $M^n$ 求出$F_n$，其中
$$M = \begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}$$如果是求$F_n$ 時間複雜度 $O(\log n)$，而這一題求的是$F_{2^n}$，時間複雜度 $O(n)$。
為了加速運算，目標是要找到 $\mod p$ 下的循環長度 $L$，最後求出$F_{2^n \mod L}$，根據待會的證明，保證 $L \le p$，那複雜度就可以回到 $O(\log L)$ 解決。但為了要找到 $L$ 又是一段很長的故事，總時間複雜度為 $O(\sqrt{p})$，不用保證 $p$ 是質數。
數列$F_0 = 1, F_1 = 1, F_2 = 2, \cdots$，循環是連續兩項出現重複，而費氏數列會完全循環，也就是出現連續兩項$F_i = 0, F_{i-1} = 1$。下方是一個 $\mod 4$ 的情況。
|
|
要找到恰好連續兩項$F_i = 0, F_{i-1} = 1$ 是困難的，考慮去找到$F_i = 0$ 即可，接著再去想辦法讓$F_{i-1} = 1$。
假設最小的 $k$ 滿足$F_k = 0 \mod p$，而$F_{k-1} = a \mod p$，那麼之後的序列$F_{i} = a^j F_{i+j \times k} \mod p$。從矩陣乘法的概念中可以理解，是一個常數為 $a$ 的初始項，第二輪循環常數就會變成 $a^2$，類推。
接下來
現在問題落在 $k$ 怎麼找到，若能找到 $k$，其循環長度落在 $k$ 的倍數，或者有更好的獲取方式。
關於二次剩餘的判斷，在模質數 $p$ 下，對於 $gcd(x, p) = 1$，藉由歐拉定理得到 $x^{p-1} \equiv 1 \mod p$，以下不保證是正確的說法，提供理解的一個方案。
回過頭來，看一下費氏數列的公式解
$F_n = \frac{1}{\sqrt{5}} \left [ \left ( \frac{1+\sqrt{5}}{2} \right )^n - \left (\frac{1-\sqrt{5}}{2} \right )^n \right ]$藉由展開公式，儘管它是實數、根號，展開之後一定只會剩下整數冪次的總和。令 $a = \sqrt{5}$，觀察二次剩餘與否和滿足$F_n = 0$ 的關係。
在模質數 $p$ 下，滿足二次剩餘$F_n \equiv 0 \mod p$，當 $n = p-1$ 的時候成立，可以藉由噁心的展開式得到。同理在非二次剩餘情況，$n = 2(p+1)$，找到一個最大的倍數情況，答案一定落在其因數下。詳細推導請看參考資料，太噁心就不提。
參考資料中有特別提到，有一個地方還 沒有確認 ，對於模數 $p^k$ 的循環長度 $g(p) \times p^{k-1}$ 如何證明。但我想根據中國餘式定理，能了解循環長度倍數的模關係吧。接著由於大整數分解期望是 $O(\sqrt{n})$，中間也要找到所有因數來得到循環長度的驗證，還要搭配快速矩陣乘法，最後也是 $O(\sqrt{n})$。
這一題是更進階的費氏數列計算，從建表、矩陣乘法，最後來到循環搜尋，這些證明不久之後就會忘記了，二次剩餘判斷的想法還會留著，其他就忘得一乾二淨吧。
|
|
曾經某 M 被期望值坑，就只是在計算 $x^y \mod z$ 時偷偷替換成 $x^{y-1} \times x \mod z$，結果得到 Time Limit Exceeded。
根據分析 $y = 16$ 時，用二進制表示為$(10000)_{2}$，若變成 $y = 15$，就會變成$(01111)_{2}$，通常快速求冪的乘法次數與二進制的 1 個數成正比，所以速度就慢非常多。
|
|
讓我們來一場 $x^y \mod z$ 的期望值試驗吧，基礎目標是減少乘法次數。
其中 $1 \le x, z \le 10^{18}$, $0 \le y \le 2^{2^{20}}$，在這場試驗中展現你的優化吧。
|
|
|
|
詳細可以參考《資訊安全 - 近代加密 快速冪次計算》那一篇。
| Algorithm | Table Size | #squaring | Average #Multiplication |
|---|---|---|---|
| Right-To-Left | 1: $x^{2^i}$ | $n$ | $n/2$ |
| Left-To-Right | 1: $x$ | $n$ | $n/2$ |
| Left-To-Right(2-bits) | 3: $x$, $x^2$, $x^3$ | $n$ | $3n/8$ |
| Left-To-Right(sliding) | 2: $x$, $x^3$ | $n$ | $n/3$ |
減少乘法次數，但以上期望乘法次數是跟 1 的個數有關，雖然最好是從 $n/2$ 降到 $n/3$，並不表示速度會真的快上 $1.5$ 倍左右，畢竟還有所謂的基礎乘法次數需求，根據實驗下來大約能快個 10% 到 20% 之間，加上 -Ofast 編譯此時的差異又會再少一點，看起來實作方法影響很嚴重。
例如在不加編譯優化參數下
|
|
上述做法會比下述來得快上許多
|
|
最後，產出一個 cheat 版本，使用 L-to-R-2bits 的概念下去擴充，使用 loop unrolling 進行加速，由於會發生不被整除的問題，小測資就靠 L-to-R-sliding 的方案去解決。
在 zerojudge 主機上平台上，隨機測資下的運作情況如下：
| Algorithm | Time |
|---|---|
| Right-To-Left | 5.4s |
| Left-To-Right(2-bits) | 4.9s |
| Left-To-Right(sliding) | 4.8s |
| Left-To-Right-sliding-cheat | 4.2s |
|
|
|
|
|
|
|
|
某 M 成功在最後一刻內完成服務學習時數，卻英文畢業門檻待在學校暑修英文，為期長達三周，每周一到五每天上六小時的課程，是否會改變某 M 什麼呢？
在六月盛夏，看著同學們匆匆忙忙地走向人生下一階段的道路，學校逐漸空無一人，認識、見過的人越來越少，儘管是臉盲的我，想不出名字、不確定是不是見過面的人的次數也變少，想必是更沒機會遇到真正的人吧。
暑修開始的第一天，老想著「只有愚蠢的自己會遇到這種遭遇」清幽無人的早晨，看著外頭在這一學期耕耘的稻田，在稻田小路中騎著腳踏車出門上課成了另一股滋味。在第一次課前，順道去便利商店拿網路訂購的書《程式設計的解題策略》，這個暑假能做出不同於去年嗎？儘管沒有特別的回憶或收穫，看看新書也許還不錯，但好像沒有曾經那股傻裡傻氣的衝勁。
很久沒到綜合教學大樓，想著裡面有為數不少的語言中心，那便是一場深入敵營的戰鬥，原本想在教室外看看新買來的書籍，想著與世隔絕的數學問題，好安慰心靈。沒想到能遇到曾經住宿在一起的轉學生。
「嘿！你也來了。」好久沒遇到人這樣打招呼。比起班上同學，住宿一段時間的差異是很明顯的，雖然不同科系，曾經那段在宿舍互相抱怨的日子相當回味，若遇到班上同學，由於不算熟識，聽取抱怨時還要多想想。
「你為什麼來了？英文不是不差嗎？」
「是啊，但是管院的英文門檻太高。同學還跟我說『考前一天弄一下聽力閱讀，就拿七八百』」
「這種事情我也明白，鄉民常說到用猜的都有五六百，我都開始懷疑這個世界。」
平時自己想著一個簡單的數學問題不斷打轉，甚少去注意那些禮節，大多時候擔心別人正在忙，不打招呼應該比較好，說不定我還認錯人，也許他根本不認識我，不增加別人困擾！聊著聊著未來和現況，道出自己的我是話癆吧。
第一門課是為前測而來，發現有不少的學生也來修英文，看著助教和老師匆匆忙忙地換了大教室和準備上課事項公布，正式開始之前，老師似乎非常意外地有這麼多學生。
「怎麼這麼多人，我們班有五十多位同學，你們有多少是大四生？舉個手一下。」老師問道。
「！」坦蕩蕩地舉了手，對於英文這種小事，早就羞恥感全沒了。
「哇，還挺多人的。為什麼你們要等到最後才來解決這個？」台下躁動了一下，想必在場都有各式各樣的原因。
「萬一暑假沒開這門課，你們打算怎麼辦？」老師接著問道，偷偷細語地說「就延畢吧！」
「好吧，暑假這門課有點趕、時間有點緊湊，所以大家要主動積極一點。」老師帶有苦衷地說道。
「不知道你們未來在外面會遇到、需要什麼英文。這門課就當作離開前的訓練吧。」
其實咱們都明白「主動積極一點」暗示著什麼，也就是沒有人會去管、必須得自己來，那我們又是因什麼原因聚集在一起？大多不就是自己來失敗了嗎？
過了不久，按照規定每天閱讀兩篇文章、寫兩篇英文摘要，提交給線上檢測系統，「英文也有檢測系統？」大部分 ACM 競賽的人大多都有這樣的疑惑，對於模稜兩可的語言評分是一件很困難的事情，儘管系統不甚完美，對於「這群英文廢物」而言相當和藹可親，只要騙過系統就完事。畢竟這是學校花錢購買的系統，咱們也不好多說什麼。
過了兩周，雖說一天繳交兩篇，實際上跟英文搏鬥是個難事，專注力無法像寫程式那樣一直運轉，因為寫程式明白一點「停下來可能就寫不出來。」因此一天總要花個四五個小時寫一篇單字不算難、語法錯誤連篇、邏輯不通的作文，拿著 google 翻譯與系統抗衡。
每天爬起床的第一個想法是「還是寫寫英文好了。」做什麼都提不起勁，已經過了兩周，每天催眠自己提交英文，除了系統回報，很希望聽聽人的意見，不然每天上一個全英網站，看著系統回饋的英文訊息，這段日子就像活得世界只有一個人似的。
除了英文摘要，最後一階段好像是寫作，所以比較困難吧。如果要問為什麼英文選擇題答不好，常有人說是日常生活用語，儘管單字看得懂，沒有那所謂的普遍日常，那要怎麼回答問題，每個選項都可以接受。
過去的我已經不在。
給定 $n$ 和 $m$，請你統計有序對 $(a,b)$ 的個數，其中 $1 \le a \le n, 1 \le b \le m$ 且 $a$ 與 $b$ 互質。
$a$ 與 $b$ 互質的定義是：$a$ 與 $b$ 的最大公約數等於 $1$。
|
|
|
|
柳柳州出數論基礎－「莫比烏斯反演 (Möbius inversion formula)」
之前放棄看完的內容又要撿回來看，百般痛苦，之前沒看懂啊。但能知道的是莫比烏斯反演類似排容原理，就像錯排依樣。先不管莫比烏斯，看到「線性時間求出所有乘法反元素」真的可以嗎？那也是件很有趣的事情。
了解莫比烏斯反演之前，要先介紹積性函數
回顧歐拉函數 (Euler’s totient function) $\phi$
$\phi(n)$ 是一個積性函數，但不是完全積性函數。根據中國餘數定理 或者 基本算術可以證明之。
歐拉定理 $a^{\phi(n)} \equiv 1 \mod n, \text{ when } gcd(a, n) = 1$。
特性 1：$\sum_{d|n} \phi(d) = n$。當作把互質個數 $\phi(n)$ 相加不互質個數 $s$，由於 $d$ 是 $n$ 的因數，則與 $d$ 互質 $x$ 個數 $\phi(d)$，把那些 $x' = x \times d/n$ 就會補上那些不互質的個數 $s = |set(x')|$。
特性 2：$1 \cdots n$ 與 $n$ 互質的數和為 $n\phi(n)/2$。原因很簡單，若 $gcd(x, n) = 1$，則會滿足 $gcd(n-x, n) = 1$，看起來就是一個對稱總和。
根據積性函數的性質，我們得到莫比烏斯反演的基礎：
莫比烏斯反演公式 $f(n)$
$f(n) = \sum_{d|n} \mu(d) g(\frac{n}{d})$莫比烏斯函數 $\mu(n)$
$$\mu(n) = \left\{\begin{matrix} 1 && n = 1\\ (-1)^k && n = p_1 p_2 \cdots p_k \\ 0 && \text{otherwise} \end{matrix}\right.$$在此簡單說一次，莫比烏斯反演公式就像排容原理，而莫比烏斯函數 $\mu(n)$ 就像一加一減，之所以在 $n = p_1 p_2 \cdots p_k$ 為 $\mu(n) = (-1)^k$，也就是說當 $n$ 只全由質數相乘 (不允許冪次方大於 1，否則為 0)，相當於一般認知，奇數次要扣，偶數次要補回來的排容口訣。而特定自然不必多說，其中數學表達 $[n = 1]$ 相當於程式中的 n == 1 ? 1 : 0。
簡單展示歐拉函數 $\phi(n)$
關於公式$\phi(n) = \sum_{d|n} \frac{\mu(d) n}{d}$ 可以這麼理解。
利用莫比烏斯函數 特性 1：$\sum_{d|n} \mu(d) = [n = 1]$
$$\begin{align*} & \sum_{a = 1}^{N} \sum_{b = 1}^{M} [gcd(a, b) = 1] \\ & = \sum_{a = 1}^{N} \sum_{b = 1}^{M} \sum_{d|gcd(a, b)} \mu(d) \\ & = \sum \mu(d) \left ( \sum_{1 \le a \le N \text{ and } d | a} \left ( \sum_{1 \le b \le M \text{ and } d | b} 1 \right ) \right )\\ & = \sum \mu(d) \left \lfloor \frac{n}{d} \right \rfloor \left \lfloor \frac{m}{d} \right \rfloor \end{align*}$$第二行就是抽換莫比烏斯，第三行則是交換順序，第四行則是可以快速找到 $d|a$ 的總數為 $\lfloor n/d \rfloor$ 所導致。
若直接窮舉 $d$ 時間複雜度為 $O(min(n, m))$，可以利用塊狀的概念優化到 $O(\sqrt{n} + \sqrt{m})$。因為 $\lfloor n/d \rfloor$ 的值只有 $2\lfloor \sqrt{n} \rfloor$ 種可能，同理 $\lfloor m/d \rfloor$ 也是，那麼對於同一個 $d$ 的計數會是一個連續區間不斷地移動。
以下是一個簡單的 $\lfloor n/d \rfloor$ 示意圖，用 $\lfloor n/d \rfloor$ 不同當作劃分。
|
|
程式只要處理打 X 的位置即可，時間複雜度 $O(\sqrt{n} + \sqrt{m})$，可以參照一般解。代碼短，但除法次數多。
加速一般解由 liouzhou_101 提供。開一次根號 sqrt()，省下 $O(\sqrt{n})$ 次的除法，賺了 400 ms，代碼長了 800 B。加速 25% 的效能，可謂除法的可怕，根據研究差異後才發現到這一點。
|
|
|
|
將 N 張小正方形拼成長條圖，並且每一次挑選一個正方形區域黏貼在長條後，黏貼的條件是比較重疊一半的區域，利用能量最少路徑進行裁剪後併在一起。
如果最少能量大於等於某個值，則再隨機挑選一個正方形區域進行黏貼，捨棄掉這次黏貼操作，若嘗試 50 次沒有成功低於閥值，則取消全部的黏貼操作。
當初的問題在於 連續 50 次 看得似懂非懂，然後還以為是要碎形圖，只找一個正方形去重疊得到 N 個。
|
|
|
|
接續上一題 b438. 裁剪尺寸 的作法，現在多一個串接和重疊的操作。
感謝蔡星 asas 對此題描述的解說。
|
|
要讓影像的寬度減少，其一的方案就是每一列刪除一個像素，為了讓刪除更加地完善、盡可能看不出來突兀的地方，採用一個一條由上而下路徑進行刪除。
刪除路徑採用最少費用，這個費用採用 sobel operator，也就是說費用越高表示可能是邊緣像素，減少突兀就是盡可能不要去刪除到邊緣像素，這是顯而易見的方案。接著就是採用貪心方案，依序刪除 n 次路徑。
|
|
|
|
題目說明最好的選擇方案是一次 n 條不相交的由上而下的路徑，但這個定義是總花費，還是最小化最大花費路徑這是有疑惑的，若單純總花費可以採用最小費用流去完成，但複雜度對這個影像處理會可怕，點數跟邊數都是破萬，複雜度 $O(VE)$ 的算法要跑非常久，因此貪心是個好選擇。
找尋花費最小的路徑是採用 dynamic programming 的方式得到，並且要回溯得到左側最小的一條路徑。每刪除一條路徑後，sobel operator 要重新計算每一個像素的異動，刷新這一塊可以指更動路徑的右側和鄰近路徑的像素即可，這可以大幅度地增加速度。
|
|