柊四千的倉庫

一棵樹有「拔掉任一非葉節點便不連通」的良好性質，可以幫助我們用 DP 和 divide-and-conquer 解決問題，例如 POJ 1741 和 TIOJ 1647 。這篇假定你知道怎麼把 POJ 1741 做到 $O(n(\log n)^2)$ 的時間複雜度 (如果你不知道也沒關係，google "POJ 1741" 就有很多資料了 XD)。我們沿用 先前 的定義，把一張點數和邊數相等的連通近圖 ( pseudograph ) 稱作一隻水母。再次提醒，水母並不是正式名稱 (我找不到正式名稱 orz)。 考慮這個問題：給定一隻大小為 $n$ 的水母 $J = (V, E)$，邊有正權重，請求出 $J$ 的 $K$-近對個數。一個 $K$-近對的定義是距離不超過 $K$ 的 (無序) 點對。觀察到一隻水母其實是由頭部 (環) 和數條觸手 (樹) 組成。設頭部由點 $t_0, t_1, \ldots, t_{m-1}$ 組成，從 $t_i$ 長出的觸手為 $T_i$。我們把 $K$-近對 $(u, v)$ 分成兩種：$u, v$ 屬於同一條觸手 ($\alpha$ 型)、$u, v$ 屬於不同條觸手 ($\beta$ 型)。只要在每條觸手上跑 POJ 1741，就能求出 $\alpha$ 型 $K$-近對個數了。至於 $\beta$ 型，做法是對於每個點 $v$，統計有幾個點 $u$ 滿足 $u$ 和 $v$ 不在同一條觸手上 $u, v$ 的距離 $d(u, v) \leq K$ 我們用上圖來做說明。設邊 $(t_i, t_{i+1})$ 的權重為 $w_{i+1}$，$s_i := w_1 + \ldots + w_i$ 為「從 $t_0$ 開始，順著 $t_0, t_1, t_2, \ldots$ 的方向，走 $i$ 條邊的里程數」(為了方便，不該超過 $m-1$ 的那些索引值，一旦超過 $m-1$ 就自動對 $m$ 取模)。設 \[ \begin{cases} u \in T_j, d_u := d(u, t_j),\\ v \in T_i, d_v := d(v, t_i), \end{cases} \] 則 $d(u, v)$ 就是 $d_u+d_v+(s_i-s_j)$?! 當然我們沒有這麼好的事情，因為 有...

Description 「嗚，不可能，這不可能塞得進去!!! 啊~~~」妤嬌姊姊道。 為了前往外太空解救妁艷，妤嬌決定前往歐洲尋找最先進的航太科技。這個國家是位在白俄羅斯和波蘭的邊境的一個小王國。啵啵啪啪王國，一個世襲君主國家，國民血統為純正的 $1/2$ 白俄羅斯 + $1/2$ 波蘭的完美比例組成。國民擁有驚人的平均 $514$ 的智商，能發展出遠遠超越 SERN 的核物裡和遠遠超越地球聯合、吉翁、紮夫特的航太科技，並不意外。身為潮能力者，LEVEL-5，像是穿越電腦螢幕網路王國傳送 (Network Transfer to Realms, NTR) 這種事情妤嬌當然做過很多次。 「啊~ 好激烈，妤嬌，姊姊快不行了~ 在這樣下去姊姊會~~ 姊姊會壞掉~~」 「姊姊，我也…我也快不行了~~~」 由於妤嬌隨身攜帶的 laptop 螢幕太小了，要把人塞進去有點困難。妤嬌研判，照這樣的情況下去，再把兩個人 (妤嬌自己則可以穿越隧道過去) 都傳送過去之前電腦螢幕有可能會壞掉！ 妤嬌說：「沒辦法，妳們兩個一起來吧！」 「嗚!! 兩邊!? 兩邊一起絕對不行的!!」兩位美少女同聲道。 (十分鐘過後) 「啊~ 妤嬌~~」 「妤嬌葛格~~ 啊~~」 三人都因為使力而身體微微泛紅，身上沾著彼此的汗珠。 「要去了!!!!!!」妤嬌喘著氣大喊。 「在裡面!?!?!?!?」 「妤嬌!!!!~~~~~~~~~」 周圍閃了幾下白光，費盡工夫，總算把兩人塞進螢幕裡面了。剩下的工作就有開啓「人工少女 3」把電腦中的兩人送到啵啵啪啪王國了。 「要產品序號!?」 點開遊戲後才發現事情不妙！ 在妤嬌的記憶中，序號是由下列方法所生成的： 給定質數 $p$ 和正整數 $b, c, n$，定義序列 \[ \begin{cases} a_0 = 1,\\ a_i(a_{i+1}-c)=b,&\text{for }i = 0, 1, \ldots \end{cases} \] 序號為最小的正整數 $m$，使得 $p|ma_n-1$。由於妤嬌是個天才，你只需要幫他驗算就可以了，輸出序號 $\operatorname{mod}q$。 Input Format 第一行有五個正整數 $b, c, n, p, q$，其中 $p, q$ 為質數，意義如上...

Description 你有 $n$ 張眼皮和三隻向姊，每張眼皮有他的角動量。 你希望把這些眼皮全部分給三隻向姊，為了避免眼皮爆走，所以需要讓向姊間的角動量差最小，否則向姊們就會吵架！ (假設所有眼皮轉動方向都是逆時針方向，且對於每隻向姊，她的所有眼皮的旋轉中心都相同) Input Format 第 $1$ 行有一個數字 $n\ (3\leq n\leq24)$，代表眼皮的個數。 第 $2$ 行有 $n$ 個數字 $a_1, \ldots, a_n$，$1\leq a_i\leq10^9$，代表每張眼皮的角動量。 Output Format 輸出一個數字，代表角動量最大的向姊和角動量最小的向姊間的角動量差的最小值。 Sample Input 4 5 4 7 6 Sample Output 3 Solution 如果今天只有兩隻向姊，怎麼做呢？利用  meet-in-the-middle algorithm ，可以做到 $O(n2^{n/2})$ 的時間複雜度，比 naïve 演算法的 $O(2^n)$ 快。以下將介紹怎麼在有三隻向姊的情況下，同樣利用 meet-in-the-middle 的精神，在 $O(n3^{n/2})$ 時間內求出答案。為了後續的討論方便，我們允許某個 $a_i \leq 0$，且允許某隻向姊沒分到任何眼皮。 假定三隻向姊拿到的眼皮角動量總和分別為 $p, q, r$，不失一般性令 $p \leq q \leq r$，目標最小化 $r-p$。設 $s := a_1 + \ldots + a_n$，則以下的兩個敘述至少一個會成立： $p \leq q \leq s/3 \leq r$ $p \leq s/3 \leq q \leq r$ 如果我們知道怎麼算出第一種情況 $r-p$ 的最小值，只要把每個 $a_i$ 變號，第一種情況 $r-p$ 的最小值就變成「變號前的第二種情況 $r-p$ 的最小值」了。接下來我們專注在「在限制 $p \leq q \leq s/3 \leq r$ 下最小化 $r-p$」上。 將 $a_1, \ldots, a_n$ 分成兩堆，$A = \{a_1, \ldots, a_{\lfloor n/2\rfloor}\}$ 和 $B...

Description hellogameboy 正在進行一個神秘的計畫 他打算以 H 的力量來征服全世界，讓世界都屈服在他的 H 勢力之下 這時候正義的 hallogameboy 挺身而出，決心鼎力維持這個世界的正直 想像這世界是一個 $n\times n$ 的格子棋盤，每個格子都是一個城市 而時事潮流總有固定的流向，因此對於每個格子都有一個"潮流傳播方向" (上、下、左、右之一) 若某個城市的潮流是流向棋盤邊界外，當然，這個城市的潮流就不會傳播給任何人 hellogameboy 和 hallogameboy 將輪流展開行動， 由 hellogameboy 先展開 H 的攻勢，再換 hallogameboy 進行正直防守...... 攻防不斷交替地進行，直到所有城市都被佔領 一開始所有城市都是純潔的，沒有受到任何佔領 而 he(a)llohameboy 將選擇一個"源流城市"佔領 H (正直) 的力量就會從這個源流城市開始沿著每個格子的潮流傳播方向傳播 路上的城市都被佔領，直到某個潮流傳出邊界，或是遇到某個已被佔領的城市才停止。 以上圖為例（佔領攻防還沒結束，也不是最佳佔領策略） hellogameboy 先選擇 $(2,2)$，並佔領紅色的 $12$ 格 再來換 hallogameboy，選擇 $(5,7)$，佔領藍色的 $8$ 格 再來又輪到 hellogameboy，選擇 $(5,6)$，佔領綠色 $2$ 格 hallogameboy 再選擇 $(2,4)$，佔領黃色等 $5$ 格…… 給定一個地圖，假設 hallogameboy 和 hellogameboy 都是絕頂聰明的人物 那麼請問，最後 hellogameboy 將以 H 勢力會統領多少土地呢? Input Format 第一行為一個整數 $n$，代表地圖邊長。 再來為 $n$ 行，每行是一個不含空白的字串，由 l、r、u、d 構成，依序代表左、右、上、下的箭頭。 $1\leq n\leq 2000$ Output Format 一個整數，代表先者 (hellogameboy) 可以佔領多少格。 Sample Input 6 drludl rudlru dldldl r...

前言 要計算兩個大數的乘積，可以先把這兩個大數轉成兩個多項式，計算它們的乘積，再轉回大數，時間複雜度 $O(n\log n)$；然而，大數除法和多項式除法可說是完全不一樣的問題。以下要介紹如何利用 牛頓法 把除法問題轉化成乘法問題，並利用倍增 (doubling) 來得到 $O(n\log n)$ 的除法演算法。 本文內容大致上只是把之前我寫的 這篇 document 換成中文，但一些證明以及虛擬碼 (pseudocode) 則省略。另，實作部分可以參考我在 github 上的 大數模板 ，讀者也可以在 ZJ b960 測試自己的程式。 動機 以下設 $\xi$ 和 $\eta$ 都是 $A$ 進位正整數，其中 $A \geq 9$，$\xi \geq \eta$，且 $\xi$ 和 $\eta$ 的長度分別為 $m$ 和 $n$，目標求出 $\lfloor\xi/\eta\rfloor$ 的 $A$ 進位表示。因為 \[\xi/\eta = \xi\times 1/\eta\] 如果我們能把 $1/\eta$ 算得夠精確，就能把除法問題轉換成乘法問題。我們希望能找到某個 $x \leq 1/\eta$ 使得 \begin{equation}\label{goal}\lfloor\xi/\eta\rfloor-1 \leq \lfloor\xi x\rfloor \leq \lfloor\xi/\eta\rfloor\end{equation} 不難發現只要 $x$ 滿足 \begin{equation}\label{tol1}0 \leq 1/\eta-x \leq A^{-m}\end{equation} 就有 \[\xi/\eta-\xi x = \xi(1/\eta-x) \leq A^m\cdot A^{-m} = 1\] 也就是 $(\ref{goal})$ 會成立。接下來我們把目標放在找到 $x$ 滿足 $(\ref{tol1})$。 牛頓法 考慮函數 $f(x) := \frac{1}{x} - \eta$。我們找一個 $x_0 \in (0, \frac{1}{\eta}]$，並對於所有的 $k \geq 0$，令 \[x_{k+1}\gets x_k - \frac{f(x_k)}{f'(x_k)} = x_k(2...

整數的加減乘除四種運算，無論是在國小算術或是在程式設計中，除法都比其他三種運算來得麻煩。舉例來說，假定我們想動手算 $1650794238\div 26451$，長除法的第一步是 我們必須猜出 $\Box$ 內要填的數字，而這正是除法計算痛苦的來源。因為我們沒有表可以查，只能猜一個數字 $\alpha$，放入 $\Box$ 中，看看 $165079 - 26451\alpha$ 是否介於 $0$ 到 $26450$ 之間，而如果不幸猜錯，還得重猜並重新計算一次乘法和減法。 我們把這個猜商問題寫得再清楚一點：給定兩個 $b$ 進位的整數 \[\begin{cases}\xi = x_{n-1}\ldots x_1x_0= x_{n-1} b^{n-1} + \ldots + x_1b + x_0,\\\eta = y_{n-1}\ldots y_1y_0= y_{n-1} b^{n-1} + \ldots + y_1 b + y_0,\end{cases}\] 其中 $0 \leq x_i \leq b-1$ 對於所有的 $0 \leq i \leq n-2$，而 $x_{n-1} \geq 0$ (可以超過 $b-1$，如上面的例子 $b=10, n=5$ 而 $a_4 = 16$)。 $0 \leq y_i \leq b-1$ 對於所有的 $0 \leq i \leq n-1$，且 $y_{n-1} \neq 0$。 $\lfloor\xi/\eta\rfloor \leq b-1$。 目標找出 $a := \lfloor\xi/\eta\rfloor$。有鑑於網路上多數的大數長除法 code，猜商步驟亂寫 (無誤)，我決定在這篇導正視聽 (?)，介紹一個保證在 $O(1)$ 次內猜到 $a$ 的策略。 策略一：枚舉 $a = 0, 1, \ldots, b-1$ 最糟情況猜商次數 $\Theta(b)$，不解釋。 策略二：在 $0, 1, \ldots, b-1$ 之間做二分搜找出 $a$ 這是策略一的簡單改良，猜商次數 $\Theta(\log b)$，一樣不解釋。 策略三：利用 $x_{n-1}$ 和 $y_{n-1}$，縮小策略二的二分搜範圍 想法是這樣的：因為 \[\begin{cases}x_{n-1}b...

Description 「我與小明不相見已有二年餘了，我最不能忘記的是他的雙腿。（雖然他根本沒有）」 光陰荏苒，你如今是一位御用新聞記者，專門替國王烏龜的電視台採訪各式各樣的新聞。還記得 TIOJ 1623--國王烏龜的接駁車 嗎？大意就是國王烏龜開放死老百姓烏龜們去覲見國王，舉國上下無不歡聲雷動，一時之間各個直達皇宮接駁車的站牌前都排滿了烏龜，好不盛大！你自然被派遣過去負責採訪這場盛宴。並且他們看在你的才能，決定要讓你Live連線報導，你知道如果把這個難得的機會搞砸了你可能會變成小明第二。 因此，在開始報導之前你決定先去向前輩烏龜瞭解你的報導方式。 「 你待會要進行的報導方式呢，你看那邊有一條大排長龍的隊伍，共有 $n$ 隻烏龜排成一列，你需要選擇一個區間 $[A, B]$（包含$A, B$）進行採訪，採訪的方式是依序遞麥克風給這個區間每一隻烏龜，讓他們自由發言。必須注意的是因為要弄得看起來很有公信力，你採訪的 總人數不能小於 $L$ 個人 。 當然自由發言是有危險成份在的，有些反國王份子可能會講出危言聳聽的話，危害國王聲譽，所以我們會依序把烏龜標號 $0$ 或 $1$，$0$ 表示危險份子、$1$ 則是很安全。 所以，我們希望你能讓這個區間內 $\mathbf{1}$ 佔的比例越大越好 ，如果有很多個一樣好的區間，那就是總人數越少越好（但還是得 $\geq L$），如果還是有很多個，那就 $A$ 越小越好。 你選好你要採訪的區間了嗎？告訴我吧。 」 Input Format 輸入第一行含一個正整數 $T$，表示接下來有幾條隊伍要採訪（幾組詢問） 每組詢問第一行含兩個正整數 $n, L$（$L \leq n$），分別表示隊伍長度跟採訪總人數下限。 第二行會是一個長度為 $n$ 的 $01$ 序列，依序表現出每隻烏龜危不危險。 $T \leq 400$ $1 \leq n \leq 100,000$ Output Format 對每組詢問輸出兩個正整數數字 $A$ 和 $B$，表示 $[A,B]$ 是你的最佳選擇。 ※這個序列編號由 $1$ 開始，到 $n$ 為止。 Sample Input 2 17 5 00101011011011010 20 4 1...