2015年4月26日 星期日

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?),總之先無視這個問題...

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

我的程式碼: