TLX Open Contest Beta Round #1

昨天心血來潮就寫了一下這個據說是APIO熱身賽的東西 (Invitation from Codeforces)

題目感覺上都蠻普通的，APIO 應該會比這些題目難很多吧？題目品質也有點問題，pB、pC都有嚴重的 issue ，賽中才被更正。

是說 SRM656 的解題報告寫了一半覺得好難寫，先跑來寫這個簡單的東西 wwwwww

題目連結(必須登入)

Problem --- Social Inequality

題意：給 $N$ 個點，問有多少任兩個點所圍出的矩形的面積總合。

數據範圍：$1 \leq N \leq 10^5$，所有點座標介於 $0 \sim 10^4$

關鍵字：[ D&C ]

tag：分治法

= = = = = = = = = = = = = = =
這題正好可以看出我在解題時會怎樣去聯想以做過的題目。它給了平面上好多點，又問了關於所有矩形的某些資訊，於是我就聯想到了  ZeptoLab Code Rush 2015 pF，是我過去寫過題解的東西！(我每次列的關鍵字終於用到了 XD 輕鬆搜到這題 )，於是我就開始思考要怎樣用Divide and Conquer 來解這題。

使用的 D&C 來解這題的話，大制概念就是每次把點群都分兩半，把兩對角恰在兩半各一個的矩行面積總和先算出來，再遞回下去。

這題時限只有 0.3 秒，看來一定得用 $O(n log n)$ 的解法才能 AC，所以在每次解一個 subproblem 時，只能用 O(n) 去解決 (這裡的 $n$ 是該 subproblem 的點數)。

仔細描述一下我們要解的 subproblem：
　　平面上有很多點，以及一條水平線，請把所有水平線上及水平線下各曲一點的所有組合，每個組合所圍成的矩行面積總合計算出來。

不防假設我們已經把所有點由左到右排序好了。接著我們由左到右一個點一個點依序加入，每加入一個點時，我們希望能以 $O(1)$ 的時間，把該點與所有在另外一半的已加入點所圍成的矩形面積總合算出來。

如下圖所示，假設現在加入的是在下半部的藍點，而在上半部已存在的點是三個紅點。要一次行算出所有的面積似乎有點困難，但我們若再把每個舉行細分為上半部和下半部，就會發現要一次把所有矩行的下半部面積總合算出來(或是上半部)，都沒有很困難。

例如說我要算下半部的部分，我們可以發現所有下半部的矩形高都一樣，在新增藍點時才會決定(令其為 $h$)。所以我們若能知道所有矩行寬的總和($\sum w_i$)，就可以算出所有下半部的矩形面積總合($\sum{w_i*h}$)，以下圖為例，令藍點 $x$ 座標為 $x_b$，紅點座標為 $x_1, x_2, x_3$，則 $\sum{w_i} = \sum{(x_b - x_i)} = 3*x_b - \sum{x_i}$。所以實際上我們只要記錄每一半部已經加入多少點，加進去的點的 $x$ 座標和，就可以快速算出加入的點所在的那半部矩形面積總合。

而另外一半部也能使用某些累加的概念去算出面積總和，詳情請參考我所付的程式碼 >_<

若要認真考慮 Divide and Conquer 中的 Conquer 到底有沒有在這個解法起作用...其實我覺得並沒有 ... 所以還是稱它為分治法好了 Orz

我的程式碼如下：

Problem --- Jump!

題意：有無窮多的個石頭，並把它們用正整數編號。每個石頭都有個對應的值 $a_i$。有多個詢問。詢問過程中要維護一個數 $N$。第一種詢問：給定 $N$ 的新的值。第二種詢問：更新給定編號的石頭的值。第三種詢問：你可以選擇一個數 $P$ ($2 \leq P \leq N-2$ 或 $P = 0$)，最初會先把石頭 $1$ 標記，接著會把石頭 $(P$ mod $N) + 1$,  $(P*2$ mod $N) + 1$, $\dots$ 也標記，直到再遇到石頭 $1$ 為止，請問選哪個 $P$ 值，能使得被標記的石頭所對應到的值總和最大($P$ 若選 $0$ 代表指標記邊號 $1$ 的石頭)？請輸出最大的總和值。

數據範圍：$1 \leq N \leq 2000$，詢問數 $\leq 50,000$。

關鍵字：[ 資料結構 ]

= = = = = = = = = = = = = = =
這題題目敘述很複雜... 而且一剛開始 $P$ 的範圍還給錯使我 WA 了好多次。

首先要注意到雖然我們選的 $P$ 值可能不同，但若 $gcd (P, N)$ 相同的話，標記到的石頭們會是同一群，也就是所有邊號為 $gcd(P, N)$ 的倍數加 $1$ 的石頭。方便起見，值接把所有石頭邊號減一會比較好寫 code。

注意到這件事後，我們就知道對於每個第二種詢問，只需要考慮是 $N$ 的因數的 $P$ 值 (當 $N \leq 6$ 時，有可能不存在合法的 $P$ 使得 $gcd(P,N) = 1$，要特別處理)。並且在枚舉這些值時，可以用一些資料結構如樹狀數組(Binary Index Tree, BIT)去算加總。

詳情參考我的程式碼：

Problem --- Fowl Scupltures

題意：平面上有好多個點，以及一條通過原點的直線，這些點是兩兩成對的，也就是說所有點對於該直線的隊稱位置也會有一個點。但現在某些點消失了，並且我們也不知道直線在哪(只知道它通過原點)，問至少消失幾個點，以及直線可能的位置(若有多種可能位置請選取最離 $x$ 軸政像逆時針角度最大的位置)

數據範圍：點數 $\leq 2000$，所有座標絕對值 $\leq 10^9$。

關鍵字：[ 計算幾何 ] [ 枚舉 ]

= = = = = = = = = = = = = = =
這題其實有個很大的癥結點：題目沒說明點若恰好在那條直線上會發生什麼事，若造測資條件所述："No two or more sculptures are located on the same coordinate." 那麼點應該不能出現在直線上，可是沒有判這件事也會 AC (判了說不定會變成 WA？)，總之先無視這個問題...

要使得消失的點最少，也就是要使得配對到的點對最多。並且每個點對若能配對，也都會有個配對時會對應到的角度。於是我們枚舉任兩點能夠配對時的角度，只留下角度的資訊，可哪個角度出現最多次，那個角度就是答案了。至於對稱軸的角度，在這題裡可以使用向量取代，於是不會有浮點數誤差。細節請看程式碼註解。

我的程式碼：