Problem
給予兩個顏色的像素，在一張空白影像中使用漸層效果。
- 水平由左到右的漸層
- 從中心點擴散的漸層
Sample Input
|
|
Sample Output
|
|
Solution
線性內插，特別小心中心點 (x, y) 會是一個浮點數情況。
|
|
b426. 宇宙光明體
Problem
模擬兩張圖片的合成。
將前景圖片疊在背景圖片之上，按照權重比例來融合重疊部分得像素。
Sample Input
|
|
Sample Output
|
|
Solution
原來是宇宙光明體，還以為是宇宙大覺者呢。
按照公式純模擬即可。
|
|
b425. 抽菸動作 請勿模仿
Problem
替影像打上馬賽克效果，馬賽克效果是把區域內部的每一個像素改變，改變的方法為從舊的圖像中，搜索以其為中心的 11 x 11 方形內部所有像素的平均。
這一題要馬賽克區域為圓形，接著找到方形內部的像素平均即可。
Sample Input
|
|
Sample Output
|
|
Solution
馬賽克的方案也許還有其他，從這裡可以知道平均造就出新的像素顏色。那麼可以列出方程式，所謂的解馬賽克估計也是去找線性聯立方程組，利用高斯消去法就能求解，可惜的是會有多組解的情況吧。
|
|
b424. 圖片縮放
Problem
此題有精準度誤差，未能提交成功。
進行圖片縮放，有兩種方案來補足缺失或者是簡化的像素計算。不管縮放如何，在新的坐標系的點可以對應到舊坐標系中，並且會有四個像素點 (正方形) 包含這個對應點，有可能會有所缺失，但至少包含一個點。
- 最近鄰點法 (nearest-neighbor approach)
找正方形中哪個點最靠近新的對應點，就令其像素顏色等於最靠近的點。 - 雙線性內插 (bi-linear interpolation)
顏色由相鄰四個點決定，使用雙性內插來得到新的像素顏色。
特別注意，雖然邊長根據縮放四捨五入，但在計算時先不考慮最終結果的長寬，否則縮放倍率也會跟著四捨五入。
可以參考 中央大學影像處理實驗室 課程 講義第二章
Sample Input
|
|
Sample Output
|
|
Solution
除了陷阱的邊長四捨五入外，精準度根據雙性內插影響。
雙線性內插可以由下列兩種方案，或者還有其他的
- 兩次 lerp 插值，先水平後垂直或者先垂直後水平
- 特別的 $f(x, y) = (1-a)(1-b) g(j, k) + a(1-b) g(j+1, k) + (1-a) b g(j, k+1) + a b g(j+1, k+1)$
特別發現到，第二種方案沒有用到除法運算，但乘法運算的優先順序會影響到誤差。然而我的代碼是混用造成難以評估的誤差。關於第二種方案的坐標系，可以參考講義中的圖示。
|
|
b423. 魔術橡皮擦
Problem
提供影像去背、相鄰去色兩種方案。
- 去背對整張影像找像素差小於某一個範圍內，就將其 alpha 值設成 0。
- 相鄰去色對鄰近四個方向上下左右進行搜索，將像素差低於某個閥值的都加入到集合中進行 alpha 值設成 0。
Sample Input
|
|
Sample Output
|
|
Solution
|
|
b422. Colorful Life and Monochromatic Life
Problem
將一張 rgb 表示的彩色影像變成灰階影像。
套用公式 round((r + g + b)/3) 得到新的像素色彩。
Sample Input
|
|
Sample Output
|
|
Solution
|
|
b419. 公平的硬幣
Problem
一天，liouzhou_101 去打印店裏打印了幾張複習資料，花了 4 毛錢，他給了店主1張塊錢的鈔票，結果店主補了他兩枚硬幣，一個5毛錢，一個 1 毛錢。
在走回宿舍的途中，liouzhou_101 一直在想一個問題，5 毛錢的硬幣和 1 毛錢的硬幣哪個更公平？所謂公平，就是指將一枚硬幣拋擲 1 次，他正面朝上的概率是 12，反面朝上的概率也是 12。
結果他一會去就把1毛錢的硬幣拋了 1000 次， 記下來有 531 次正面朝上。然後他突然說道：“這硬幣不公平！！！”
真的不公平嗎？他希望你計算一下出現這種情況的概率。
Sample Input
|
|
Sample Output
|
|
Solution
跟柳柳州互相出題目，已經來到了第 n 天，儘管我出的都是垃圾跟搬運題目，一出題被電得好愉悅，出在多的垃圾題都電不到柳柳州。
在擲硬幣找區間次數 $[a, b]$ 的機率，由於是離散的統計上就只能推組合數學，但又不是曲棍棒的模型 (Hockey Stick Pattern)，算了先手動窮舉，用 Stirling’s formula 計算組合，後來發現有幾組數據有問題。
當 n 太大的時候，機率分布就相當稀疏，直接套用數值積分，直接去積分自然分布得到公式稍微困難，利用 simpson 或者是 romberg 去解決，但這樣還會有一個問題，只有在平均值的部分機率非常高 (類似離散的 00000100000)，導致自適應辛普森積分會判斷錯誤，提醒剖半積分後測資就正確了不少。似乎合作出了一個可怕的題目，儘管如此，還是得用 mathlab 或者是 wolframalpha 來協助測資的檢驗，剩下的部分就交給柳柳州了。
關於自然分布 (normal distribution)：
- 骰子擲 $n$ 次，命中的機率 $p = 1/2$
- 期望值 $\mu = np = n/2$
- 標準差為 $\sigma = \sqrt{np(1-p)} = \sqrt{n/4}$。
期望值 $E[x] = \sum_{k=1}^{n} k \binom{n}{k} p^k (1-p)^{n-k}$，消階層之後提出，計算後得到 $E[x] = np$。
而標準差 $\sigma$ 先從變異數下手
- 定義： $Var[x] = E[(x - \mu)^2] = \sum (x - \mu)^2 P[X = x]$
- 拆解步驟 1： $Var[x] = \sum (x^2 - 2 \mu x + \mu^{2}) P[X = x]$
- 拆解步驟 2： $Var[x] = E[x^2] - 2 E[x] E[x] + E[x] E[x] = E[x^2] - E[x]^2$
- 拆解步驟 3： $E[x^2] = E[x(x-1)] + E[x] = n(n-1)p^2 + np$
- 拆解步驟 4： $Var[x] = np(1-p)$
接下來直接帶入自然分布的公式，參數 $(\mu, \sigma)$，特別小心使用辛普森積分 $[a, b]$ 時，由於問題是離散的，要改變成 $[a - 0.5, b + 0.5]$，防止 $a = b$ 時造成積分錯誤。
特別感謝學弟 firejox 的數學指導。
不久之後，firejox 說道內建函數 erf() 可以解決積分問題，詳見 wiki Gauss error function，因此這一題也可以不寫辛普森積分，套用內建函數在不到 10 行內解決此題。
暴力檢測
|
|
數值積分
|
|
b417. 區間眾數
Problem
背景
大學上課是怎麼回事的呢？談論到學期成績計算，很多奇聞軼事可以說的，例如教授任選三題批改、同學任選三題作答、滿分三百、沒有考試、 … 等。筆試類型的考試只是最常見的一種，還有所謂的多才華加分，例如上台報告、舉手發問、參與展覽、參加競賽、 … 等。
不幸地，某 M 修了一堂怪課，教授每一堂課結束後總是會大聲宣揚「葛萊分多加 5 分」對於需要不斷複習演練的某 M 而言，這門課的即時評分方式讓其非常挫敗。神奇的是，有一次教授這麼問同學「給一序列，請計算眾數、平均數、中位數，答對加分。」某 M 剎那間傻住，大學的學期成績可以用這種問題獲得，當他在懷疑這個問題時，問題早已被同學回答走。
某 M 非常不甘心，計算眾數、平均數、中位數就能夠加分，要求只是 n = 10 的序列。既然加分有理，出題吧！
題目描述
平均數、中位數可以藉由區間總和、區間 K 小問題來完成，現在來解決眾數。
給定一個長度為 $n$ ( $1 \le n \le 100000$ ) 的正整數序列 $s$ ($1 \le s_i \le n$)，對於 $m$ ( $1 \le m \le 1000000$) 次詢問 $l, r$，每次輸出 $[s_l, \text{… },s_r]$ 中，出現最多次的次數以及有多少種數字出現最多次。
Sample Input
|
|
Sample Output
|
|
Solution
眾數區間查找 Range mode query 性質可以參考維基百科。
在這一題中，這裡提供三種解法，但我的寫法中只有莫隊算法可以通過，其餘算法受到時間跟空間上的限制，需要額外的優化，細節就不多做說明：
- 莫隊算法
只能離線處理，無法強制在線詢問，維護眾數最高頻率指針，來統計眾數的對應次數和等價眾數的個數，由於指針移動都是 $O(1)$，整體上時間效能為 $O(N^{1.5})$。 - 分塊在線 1
離線預處理 $O(N^{0.5} \times N^{0.5} \times \log{N})$
提供在線詢問 $O(\text{ans} \times \log{N})$，由於知道每一個塊中的代表眾數都可能是答案，因此預處理每一個塊的眾數，其餘的非眾數捨棄掉，最慘情況是每個數字都出現一次，在線詢問時複雜度會掉到 $O(N \log N)$。 - 分塊在線 2
- 離線預處理時間 $O(N \times L^2)$，提供在線詢問 $O(N/L)$，其中 $L$ 表示有多少個分塊。
- 預處理分塊編號 $PILE[i, j]$ 的眾數情況 (類似莫隊維護指針)，因此記憶體消耗 $O(N \times L^2)$。
- 對於每一處詢問，會對應預處理中的區域塊的紀錄 $PILE[L, R]$，接著頭尾兩端的殘存數字再依序加入，意即 $A[a, L-1]$ 和 $A[R+1, b]$ 的數字加入的複雜度 $O(1)$，隨後再進行撤銷 $O(1)$。
- 假設詢問次數 $Q$ 與 $N$ 呈現性關係，整體需要 $O(N \times L^2 + N^2 / L)$，則 $L = N^{1/3}$ 是最好的情況，意即每一個塊具有 $O(N^{2/3})$ 個數字，最後得到整體時間效能為 $O(N^{1.66})$。
由於這一題目標不是找到眾數為何 (這牽涉到最小字典順序)，而是找眾數的出現個數和有幾種眾數可能，莫隊算法會快於其他算法。若是要求最小眾數莫隊算法需要 $O(N^{1.5} \log{N})$，分塊在線 1 也是 $O(N^{1.5} \log{N})$。
分塊在線 2 在此題不僅僅遇到記憶體過大，只好鬆弛 $L$ 來壓低記憶體用量，但增加時間需求，時間上慢個 10 倍以上。
莫隊算法
|
|
分塊在線 1
|
|
分塊在線 2
|
|
b418. 八成真物
Problem
「偽物比真物更有價值」—貝木泥舟
「真物和偽物一樣有價值」—忍野咩咩
「偽娘比真娘更有價值」—精英島民
任兩個物品的相似度 $sim(A, B) = \frac{|A \cap B|}{|A \cup B|}$，換句話說把 $A$ 具有的特徵和 $B$ 具有的特徵類型取交集、聯集個數，相除就能得到其相似度。例如有 5 個特徵，若 A 表示成 11001、B 表示成 01100，$sim(A, B) = \frac{|{2}|}{|{1, 2, 3, 5}|} = 0.25$。
現在盤面上有 N 個物品、M 種特徵，請問相似度大於等於 0.8 的相似對數 $S$ 有多少種。為了讓這一題更有趣味，算法允許偽物，輸出 $\frac{S}{N(N-1)/2} \times 100$。
Sample Input
|
|
Sample Output
|
|
Solution
利用 std::bitset 加速交集和聯集運算，將數個屬性壓縮到一個 32-bits 單位，然後藉 bitcount 盡可能在 $O(1)$ 的時間內完成，就有機會通過這一題。一般的 $O(N^2 M)$ 比 $O(N^2 M/32)$ 慢個五六倍。
此外，特別小心浮點數計算誤差，5.0/4.0 >= 0.8 == false，用乘法判定大於閥值的操作。
關於 LSH 的部分，還在進行測試，若 signature 計算太慢，還不如直接暴力法，若能分散找到 signature 或者是預先有辦法處理好，那分桶計算就會好一點。
|
|
b413. 虛擬女友
Problem
曾經有一部採訪影片《BBC 紀錄片：別和日本人談性 No Sex. We’re Japanese.》在網路上流傳，其中有一段談到虛擬遊戲中的生活，不少男性以遊戲中的女角發生關係，其中以一款遊戲「Love Plus」為大宗，即使是擁有現實和虛擬的生活，若要選擇其中一方站，不少男性仍然「我選擇死亡」回答。
現在先不解決男女雙方的問題、在彼此關係上要如何運作，如何回到早些年沒有遊戲機、沒有網路、更沒有虛擬女友的交際生活，只有同性朋友要怎麼交流呢？於是有一場專門為這些男性舉行的一場交友會，規則如下所述：
- 一開始全場男性都彼此不認識
- 每一個男性分別喜歡各自的虛擬女友 (可以是同一個)
- 每一個時刻，其中兩個男性會因談論遊戲而成為朋友
- 自己朋友的朋友也會成為朋友
- 如果朋友的虛擬女友的類型不同，他們有可能會因偏好女友類型不同而爭吵，稱為不穩定對。
請問每一個時刻下，有多少穩定對朋友。
Sample Input
|
|
Sample Output
|
|
Solution
IPSC 2015 F 那一題發生於男女雙方都會進行聯集，而這一題只有男方會進行聯集。
合併兩團男時，只有下標 (女友類型) 相同會成為穩定對，可以利用合併排序來完成，能發生合併表示男的彼此之間不認識，只要考慮有多少女方相同即可。每一次將小堆合併到大堆中，由於要計數合併複雜度需要 $O(min(|A|, |B|) \times \log N)$，若搭配 hash 可以降到 $O(min(|A|, |B|)$。一般并查集 joint 複雜度為 $O(1)$，整體操作只需要 $O(N)$，但為了要計數，整體的複雜度為 $O(N \log N)$。
可以選擇合併排序來完成，每一次把兩堆的女方列出來，把兩堆相同類型的次數相乘，列出來可以循序做，或者是串列完成，每一次保證堆裡面的女方順序是由小排到大，合併複雜度就為 $O(|A| + |B|)$，均攤下複雜度為 $O(N \log N)$，當測資不夠隨機複雜度會掉到 $O(N^2)$，情況是每一次只把大小為 1 的堆合併到大小 i-1 的堆。
在測資隨機生成下，第二種作法會來得比第一種快。第一種做法要搭配 ordered_map 或者是 unordered_map，寫起來會比較不方便。
|
|