某島

… : "…アッカリ~ン . .. . " .. .
July 11, 2012

CodeChef July Challenge 2012

(進度: 9 / 10

Brief description:

Problem A. Addition chains:
[加法鏈][大數][構造]
構造 n 的加法鏈、長度越短得分越高、長度不得超過 500。
(n ≤ 10^100 )

Problem B. My Fair Coins:
[線性遞推數列][類斐波那契數列][矩陣乘法]
略)

Problem C. Dynamic GCD:
[輕重邊樹鏈剖分][線段樹]
給定一顆樹,動態維護以下操作:

  • C u v d: 每次一條路徑上的數 + d。(d 為正數)
  • F u v: 求一條路徑上所有數的 gcd。

Problem D. Chef’s Dream:
略.. O(nlogn) 貪心)

Problem E. Equivalent Suffix Tries:
給定一個串 S、問有多少串的 Suffix Tries 與其同構。

Problem F. Favourite Numbers:
[自動機DP][數位DP]
給定一組病毒串,問 [l, r] 區間內,第 kth 個包含有病毒串的數是多少。

Problem G. The Gray-Similar Code:
[nice][adhoc]
給定一個長度為 n 的序列 {ai},相鄰兩個數之間的 xor 相差一位。
問數組中是否存在一組 1 ≤ i1 < i2 < i3 < i4 ≤ n, 使得 a_i1 xor a_i2 xor a_i3 xor a_i4 = 0。 Problem H. Little Elephant and Bubble Sort: [概率][樹狀數組] 一個數組,對於每一位有 pi 的概率為 ai, 1-pi 的概率為 bi。。 問該數組執行冒泡排序的期望交換次數。 Problem I. Restaurant Rating: [動態維護第 k 大數][大根堆 + 小根堆][平衡樹 TLE?] 動態維護一個序列,要求支持以下操作: 1 x: 插入一個數 x。 2: 詢問第 kth 大的數,k 為 \floor{n/3}。。。 Problem J. Gift Rift: [簽到題][鞍點] 略) ...

Analysis:

Addition chains:
有待補完)

Dynamic GCD:
目測不能上動態樹(?。。。

。。。那麼樹鏈剖分是常規了。。集中分析單鏈的情況怎麼維護。。
分析修改操作。。那麼一段數 +d 的話。。。相對之間的差是不變的。。

然後注意 gcd 的性質。。 gcd(a, b) = gcd(a – b, b);
那麼一串數的 gcd 可以轉換為。。gcd(a, b-a, c-a, d-a … )
參見 GCJ Qualification Round 2010 Problem B. Fair Warning

這樣就可以用塊狀鏈表來維護。。。對於塊狀鏈表的大小。。

這裡有兩種選擇。。一種是對所有鏈用一個統一的值 (例如 整顆樹的 sqrt(n) 。。
另一種是對每條鏈用不同的值。。(每條鏈的 sqrt(n)。。。
這裡有待分析。。。

但是以上兩種方法都 TLE 了。。。
下面退回前面一個步驟。。。
仍然是利用那個興緻。。。注意到一串數的 gcd 可以轉換為

gcd(a, b-a, c-b, d-a) 。。。。。
這樣再對原數列差分得到數列 b。。。修改操作的話。。至多只會影響到 b 數組的兩項。。。

於是成段修改(+d)成段詢問的 gcd 。。。就等價於求以下兩個子問題的 gcd。。。。。
成段修改 (+d),單點詢問。。。
單點修改,成段 gcd。。。。

以上兩個問題分別用線段樹維護即可。。

Equivalent Suffix Tries:
。。。

Favourite Numbers:
dp[i][u] 表示當前長度為 i,在自動機的 u 位置時有串是存活的。。
因為串都是反著 Input 的,所以狀態轉移的時候注意向相反方向轉移。
數位DP好像也可以但是好像不怎麼好寫。。)

The Gray-Similar Code:
假設存在一組解,i1, i2, i3, i4。
則設 Ai1 ^ Ai2 = Ai3 ^ Ai4 = mask;
。。若 mask != 0 ,則必存在相鄰兩項屬於 [i1, i2] 和 [i3, i4] 區間,使得它們的 ^ 等於 mask 中的一個二進位位。
(從路徑的角度考慮即可。。)
這樣整個演算法就分成了兩個步驟,首先先判斷 mask = 0 的情況,這種情況有兩類。(4個一樣的數,或者2組2個一樣的數。)
之後處理 mask != 0 的情況,做差分預處理出一個 int S[64]; 的數組掃描即可。注意使用 unsigned long long;

External link:

http://www.codechef.com/JULY12/