Problem
現在有 R 個 Pizza 店,同一個時間接收到 N 筆訂單,每一個店負責處理一筆訂單,發送的成本為店家到訂單的曼哈頓距離。
求所有訂單送達的總時間最小值為何?
Sample Input
|
|
Sample Output
|
|
Solution
一開始以為是要求最後一個送達的時間最小化,二分下去才發現連範測都過不了。
建圖之後,用 KM 算法找最大帶權匹配 (費用最小就取負號),用最少費用流解也是可以。
|
|
現在有 R 個 Pizza 店,同一個時間接收到 N 筆訂單,每一個店負責處理一筆訂單,發送的成本為店家到訂單的曼哈頓距離。
求所有訂單送達的總時間最小值為何?
|
|
|
|
一開始以為是要求最後一個送達的時間最小化,二分下去才發現連範測都過不了。
建圖之後,用 KM 算法找最大帶權匹配 (費用最小就取負號),用最少費用流解也是可以。
|
|
給一串整數序列,請問有多少連續的區間,區間不包含重複的數字。
|
|
|
|
窮舉每一個點當作區間左端點,向左延伸的最遠的右端點必然非遞減。
掃描線計算右端點。效率 O(n log n)
。
掛上輸入優化、HASH 會來得更快。
|
|
給平面上 N 個不重複的點,有多少梯形可以由這幾個點構成?
|
|
|
|
先窮舉任兩個點拉起的線段 (let N = n*(n-1)/2
)。
針對線段斜率排序,接著將相同斜率放置在同一個 group。
對於每一個 group 的每一個元素計算有多少可以配對成梯形。
斜率相同,按照交 y 軸的大小由小到大排序。(左側到右側),由左側掃描到右側,依序把非共線的線段丟入,並且紀錄線段長度資訊。每一個能匹配的組合為 當前線段數 - 相同長度線段數
。
|
|
給一個 N 個點的樹圖,在點上放置植物保護所有的邊,每個點上最多放置一個植物,請問最少花費為何?
|
|
|
|
將樹轉換成有根樹,對於每一個 node 當成 tree 去做考慮。
狀態 dp[node][1:protect edge from parent, 0:none]
以 node 以下作為一個 subtree 的最少花費,並且是否已經保護通往父親的邊。
效率 O(n)
。
|
|
有一排樹,每個樹分別有 type
和 height
,現在要將其分團,
type
height
計算總花費最小為何?
|
|
|
|
藉由掃描線的思路,可以得知每一個樹的位置 i
,往左延伸最大多少內不會有重複的 type
。詳見 12890 - Easy Peasy 的技巧。
因此會得到公式$dp([i]) = min(dp[j - 1] + max(height[k])), j \geq f(i), j \le k \le i$
dp[i]
:將前 i 個樹分團的最少費用。
計算這個公式需要 O(n^2)
,由於 n 很大,必須找一個優化將其降下來。
首先知道 f(i)
是非遞減函數 (會一直增加),單純看 i 時,dp[j - 1]
是固定的,但max(height[k])
會逐漸增加,如果能在 O(log n)
時間進行更新、詢問,複雜度將可以降至 O(n log n)
。
每個元素有兩個屬性 (a, b)
query(f(i), i)
: return min(A[k].a + A[k].b), f(i) <= k <= i
update(f(i), i, height[i])
: A[k].b = max(A[k].b, height[i])
左思右想仍然沒有辦法用線段樹完成它,至少是一個很 tricky 的花費計算。
有一個貪心的思路,考慮區間內的計算時,只需要找到嚴格遞減的高度進行更新即可,並非所有的可能進行嘗試。用一個單調隊列,只記錄 [f(i), i]
之間的嚴格遞減的高度資訊,接著每次需要窮舉單調隊列內的所有元素。
複雜度最慘還是 O(n^2)
,隨機測資下速度是快非常多的。
|
|
給平面上 N 個點,找一個最大矩形,使得矩形邊上有最多點個數。
|
|
|
|
先離散化處理,將所有點放置在 grid[100][100]
內。
接著窮舉上下兩條平行線,由左而右開始掃描,邊緣的個數為 V[U1] + V[U2] + H[R] - V[U3] + V[U4] + H[L]
,掃描時維護 V[U3] + V[U4] - H[L]
的最小值。
特別小心矩形的四個頂點的排容,上述的公式仍然不太夠。由於題目沒有特別要求正面積矩形,必須考慮共線上最多的點個數。
效率 O(n^2)
。
|
|
不知何時開始,人們對於暴力行為開始無法容忍,逐漸地喪失對於暴力的經驗。曾經也打過架,恨不得把對方殺了,即使捶得再大力也弄不出傷口來,也許被馴化的怒火無法傷害任何人,只剩下精神上的威嚇。拿刀殺人的場景不是在電視情節中,就只能在夢裡、幻想裡去想這些。
同類相互攻擊在大自然中常見不過的事,為什麼在人類身上卻逐漸消失?沒錯!因為我們有穿越好幾世代的外部記憶體-文化。
曾經的人們為了生活,長久時間的定居,明天在哪都不曉得。只要一戰爭,贏了高興,輸了什麼都沒,生命就是這麼地短暫,中古世紀曾有一段話「看見死亡才能安心、吃得好、睡得好」那是在什麼樣的生存條件下,活著不是殺死對方,又是被殺、被壓迫的日子。面對死亡才能安心,這才是真正的活著!「 未知死,焉知生 」古人說得有道理。
為什麼至今仍有黑道白道之分?當白道無法解決的事情,黑道顯得更有威震力,看看「日本黑道山口組」在許多電影情節中,黑道的存在反而凸顯了到底是傾聽社會聲音做事?還是聽從自己的本能。社會給予的牢籠,促使我們不做暴力的行為,隱藏自己的情感,然而這些情感去哪了?
沒有暴力的行為,如何表示自己的不滿?敵意?產生出的無力感、關係冷漠、義憤,用另外一種方式宣洩自己的攻擊欲,「 如果這些世界不接受我,那就摧毀這個世界吧! 」沒了直來直往的暴力世界,卻產生出兩個極端的世界,被壓抑著暴力的人們何時會爆發呢?
殘暴的必要性-對敵人寬厚,就是壯大對方,未來必有危害,「斬草不除根,春風吹又生」不殺行嗎?用仁慈看那個世界,你就是找死!然而現今的攻擊欲,單純的攻擊欲也傷不了任何人,用武器所需要的技術越來越高,沒有技術也殺不死人,這片高牆越來越高厚呢。
起初所謂的陽剛只得是什麼?不正是那殘暴的事實嗎?現今看看那些陽剛的定義,早已經被陰柔化,受到捧吹的帥哥又是在古時的男人嗎?追求性別平等的代價,造成暴力的消失,如果還要展現自己的暴力,只能迂迴表達自己那一身的肌肉。
既然沒法殺人,公開行刑正是大眾娛樂,一個人被處刑,整座城市的人都在看,這是為什麼?在電影情節中,殺人的血腥畫面是否令人振奮?追求安心才是本能!
現在有很多不殺人的行刑,例如剝奪尊嚴,相當於利用羞恥感、價值觀的攻擊,文化的禁忌-身體的隱蔽性,這還不讓人精神崩潰嗎?讓一個人不成人形的方式很多,精神是如此地脆弱。
過去人們很難活長,活到三、四十歲就算有幸,也因為戰爭死亡相當常見,如果人們對死亡感到悲傷,豈不是沒辦法過生活?整年都要哭天喊地的,你能說他們無情嗎?不行,他們本應該這麼做,否則沒辦法前進。
古人很容易 認命 ,對於前途未卜的不安,明天還能活著嗎?戰爭就在那麼一夕之間開打,生計被土地綁著,想走也走不了。有一夜沒一夜的的恐懼,「 今宵有酒今宵醉 」死了就什麼都沒了,為何不現在享用?總是 盤算未來 ,那是你們現代人的奢侈。
血濃於水,資產階級興起後,家族之間的私鬥相當常見,衝突一來,不少家族因此滅絕。信得過的人只有血緣關係的人,不要說為何當官的都想找自己人,找不同處境的人,不怕在背後被人捅一刀嗎?(不論豬隊友)
活在當下,並非沒有遠見、逃避現實 ,誰知道明天在哪?那等絕望,你還有盤算未來的本錢嗎?
如何表示對別人的不滿?當下只剩下視覺的攻擊,作為一個活在現代的人,動手動腳就已經輸一半,觸覺已被作為侵略他人身體的領域,嗅覺則不能作為認識人的方法 (因為那如野獸一樣)。
視覺已成為唯一攻擊欲的發揮。觀賞球類運動也是如此,作為球迷欣賞支持的隊伍侵略,但自己除了看,什麼事情都不能做,一旦做了就是不文明的舉動。
暴力遊戲會使得人暴力嗎?愚蠢的人們啊,在怎麼轉換情感,也不可能百分百的宣洩。
論吸血鬼、狼人的暴力魅力化,腐女們準備好了嗎?
以下開放暴動。本文 … 略。
即使 Unigram 效果已經相當不錯,基於人類日常對話的模式,絕非單詞相依無關,藉由好幾個連詞表示出不同的意思是常有的事情,探討 n-grams (n > 3) 對於當前的語意分類器的強化、優化。
當 n-grams (n > 3) 時,語意的模糊性質會提高,可能同時把正反兩面的詞放置在一起,如此一來這一組的利用價值並不高,在計算分類上會將精準度稀釋,同時對於記憶體的負荷也會增加 (必須記錄各種組合,例如化學元素與化合物的數量大小關係)。
接著 n-grams 通常是用在英文處理精準度比較好,因為 單詞分明 (藉由空白隔開),對於機器而言中文句子並不存在詞 (token),都是一堆字元 (character)。
研究顯示: 漢字順序並不一定影響閱讀
請看下述文字-研究顯示:漢字序順並不定一影閱響讀。
對於中文自然語言處理,斷詞的重要性、語意處理上有額外的研究領域,在這裡暫時不談論這些。也許可以談談看不考慮順序的 n-grams,型態從 tuple 變成 dag。
分類器分成線上訓練、離線訓練,就已知得到目前 SVM 仍然在實務上的效果是最好的,在這裡不談論 SVM,一部分原因是 SVM 太慢。
下面是在不同領域的分類器構思,線上訓練、線性調整。大多數的分類器都必須定義特徵,對於每一個要分辨的項目是否存有這一個特徵 (boolean),而在部分可允許模糊的模型,可以利用權重 (float) 表示特徵強弱。
對於感知機的內容所知不多,每加入一筆結果,將劃分的依準疊加上預期的法向量,成為新的劃分依準線。大多依靠數學的微積分來完成,並非完全相信新加入的結果,因此會有一個計算的權重,來權衡影響的大小。
訓練流程:
$$\begin{align} & \text{INITIALIZE : } w_{1} = (0 ... 0) \text{ as parameters of the classifier} \\ & \text{For } t = 1, 2, ... \\ & \text{receive instance : } x_{t} \in R^{n} \\ & \text{predict : } \hat{y_{t}} = sign(w_{t}, x_{t}) \\ & \text{receive correct label : } y_{t} \in {-1, +1} \\ & \text{suffer loss : } l_{t} = max\left \{ 0, 1 - y_{t}(w_{t} \cdot x_{t}) \right \} \\ & \text{update-1: set : } \tau_{t} = \frac{l_{t}}{\left \| x_{t} \right \|^{2}} \\ & \text{update-2: update : } w_{t+1} = w_{t} + \tau_{t} y_{t} x_{t} \end{align}$$就如上課內容所講的
$$\begin{align} P(s) = \prod_{i = 1}^{l} P(w_{i}|w_{1}^{i-1}) \end{align}$$用 Good Turing 的方式去 smoothing 那些從未在模型中出現的詞語,它們是有機會的,絕非是機率 0。
設定一個閥值作為是否存在此分類的依據,隨後根據閥值調整相關數據的參數大小。
$h(x) = \sum_{w \in V}^{} f_{w}c_{w}(x)$ $f_{w}$ 是需要調整的參數$c_{w}(x)$ 為資料在每一個特徵的權重向量,運算內積值為$h(x)$。簡單來說,當判斷錯誤時,將相關的 (它有的) 特徵係數權重調整,將其變大使得納入分類中、或者將其變小踢出分類中。
為了加入 n-grams (n > 3) 的機制,必然要學習 忘記 、 無視 的才能,才能將垃圾訊息給捨去掉。同時也是降低記憶體的耗存的方法,這裡無法像人類有辦法根據時間將單詞組合抽象化,等到哪天 HTM 腦皮質學習算法 成功實作,相信在取捨上會更為流暢。
對於每一個特徵給予分數,保留前 K 好的特徵進行訓練,其餘特徵捨去,至於要保留的 K 大小將由實驗結果進行測試。
分數計算:
論文中提到,分別去了 50K、100K、200K 個分數高的 n-grams,又分別在 n = 3, 4, 5, 6 下進行測試,效果有那麼一點點地提升。
接著就是考驗我們期末 Project 要怎麼體現這篇論文的思路、擴充。
給 P 個隊伍、S 個賽區,每隊分別都有可以去的賽區,而每一個賽區最多容納 C 個隊伍。
請問參加的總隊伍數量最大為何?
|
|
|
|
建造 maxflow 模型,source - team - site - sink
即可完成。
不是說好 maxflow 不太會考的嗎?結果還是在泰國賽區出來了,雖然之前也噴過 mincost 最少費用流 …
|
|
盤面上放置許多 +
展開,保證寬高相同並且不會超出格子外部,同時每一個大小不超過 11。而十字中心不會被其他十字覆蓋,每一格會顯示被覆蓋幾次。
找到一種放置方法,復原盤面結果,如果有種放置方法,選擇一種字典順序最小的輸出。
|
|
|
|
論窮舉順序的重要性,將會導致速度的快慢。
原則上先把所有 1
的位置挑出,依序窮舉每一個 1
是否可以進行放置。每一次選擇放置時,先從最大的寬高開始嘗試,先塞掉大多數的盤面結果,否則速度會被拉下。
不確定這一題是否有很正統的作法,求指導。
|
|