某島

… : "…アッカリ~ン . .. . " .. .
December 14, 2012

CodeChef December Challenge 2012

。水題略。。)

Sereja and Data Structures

Brief description:

。。給定長度為 n 的數列 {an}。。記 s(l, r) 為 [l, r] 區間里最大數與最小數的差。。。
。。。詢問所有 s(l, r) 的的積。。(。。數據保證是隨機生成的。。。

Analysis:

。。分治。。每次找到當前區間的最大值記作 m(。。或最小值。。可以比較哪一個更接近中點。。
。則按從小到大的順序插入其他數字。。(。這一步暴力排序。。
。。。。左右各維護當前最遠的可用距離。。。複雜度 O(nlog^2n)
。(Remark:和 N 年前我出的一個題 一樣。。依賴於數據的隨機性。。不過這個題的 Killer 似乎很好構造?。。給個遞增的數列就行了。。

Arigeom Beats

Brief description:

。給定 n 個正整數 {An},將這些數分解成一個 AP(算數序列) 和一個 GP (幾何數列)。。。
允許一個數同時出現在 AP 和 GP 中。。。 p 可以是有理數。。(記 d 為 該 AP 的公差。。p 為該 GP 數列的公比。。下同。。
(。。{An} 遞增給出且互不相同。。。。n <= 1e4, Ai <= 1e5 ... 。。)

Analysis:

(。。。做法類似 CF 這題。。
。。

由於每項至少存在在 AP 和 GP 中的一個。。。
。。考察前 3 個數。。必然有 2 個會落在 AP 或者 GP 中。。且是該數列中最小的兩項(外層共需枚舉 6 種情況。。
。。。。。那麼 Sub Task 是驗證是否存在一個 AP (或者 GP 數列)。。使得。。某些數字必須出現。。某些數字可以出現。。

  • 對於 AP。。。
  • 。。如果存在,則對所有必須出現的數字排序。。d 一定是所有相鄰數字的差的 gcd 。。。

  • 對於 GP。。。
  • 。。如果存在,則對所有必須出現的數字排序。。則 最小數 和 最大數 必然可以是 GP 數列的第一項和最後一項。。
    設最大數 / 最小數的最簡分數為 A / B 。。GP 數列有 m+1 項。。那麼 a 和 b 的 m 次方根都必須是有理數。。。
    。。即合法的 m 為 。。。 A 和 B 的所有質因子的冪的 gcd 的約數。。。。

Different Trips

Brief description:

。。給定一顆有根樹。。問所有根到葉子結點所構成的字元串集合。有多少不同的子串。。。
。結點所表示字元等於這個結點的度數。。

Analysis:

。。開始一直從動態添加字元的角度考察這個問題。。(。。呵呵呵。。
。後來在著名圖論巔峰人物 Daizhenyang 的注視下終於認識到了我的弱菜本質。。。

。其實把根到每個結點的路徑。。組織成一顆靜態的後綴數組就行了。。。
。。要對倍增演算法進行少量的 Modification。。。(。。使用倍增祖先。。其他全部類比原演算法即可。艹?。。這似乎是個經典的題啊?

。。按照葉子到根結點的順序計算 height 數組的。。以保證線性複雜度。。
1. 遇到已經計算過的。。則直接 break 掉;
2. 若某時刻 u, v 相同。。則直接 height += dep[u]; break 掉。。

(Remark: http://www.lydsy.com/JudgeOnline/problem.php?id=1921

Quasi-Polynomial Sum:

.. 這個題需要用到。二項式定理 (Binomial theorem)。。霍納規則(Horner’s method)。擴展歐幾里德演算法(Extended Euclid’s algorithm)。。數論變換(Number-theoretic transform)。。快速傅里葉變換(Fast Fourier transform)。和中國剩餘定理(Chinese remainder theorem)
。。。這個題超出了本菜的能力範圍。。。(呵呵呵呵。。。
。。。(題解 看都看不懂我會亂說?。。 。。

WordNinjas:

。。。考慮到最後附加題本菜的演算法非常弱智。。就不和大家分享了。!!。。
由於我沒能把擬多項式和給擼出來。。最終還是傻逼的滾出了第一版主要還是自己弱也沒什麼好難過的。
。。(。。啥時候我才能像戴牛那樣虐爆全世界呢?。。。 )。。。

External link:

http://www.codechef.com/DEC12