IOI '05 Mean Sequence

這題被小乃瞬秒XD    不過其實還頗有趣的                                                                                                         .


Description:

定義一個數列S的Mean序列M:

Mi = (Si + S(i+1))/2

例如   序列1, 1, 3, 5, 15的M為: 1, 2, 4, 10



給你一個有n項的序列M，請問有多少S使得

1. S的Mean序列為M

2. S1 <= S2 <= S3 <= ... <= S(n+1)


n<= 5,000,000







Solution:

M2-M1 = (S3-S1)/2

依此，可以把奇數項和偶數項分開討論，例如範例就變成

(a), (b), (a+2), (b+4), (a+14)

再由條件2.

(a)<= (b)<= (a+2)<= (b+4)<= (a+14)

解不等式  加上a+b = 2(M1)驗證


總複雜度O(n)

IOI &#39;06 Joining Points

這題沒有Judge，所以自己寫了一個應該是可以AC的啦XD                                                                           .




很棒的題目。


Description:


Joining Points是一個獨人遊戲。

平面上有g個綠點  r個紅點   (2 <= g,r <= 50 000)

所有點都是整數座標   座標範圍是0~s (s <= 200 000 000)


保證(0,s)和(s,s)有綠點  (s,0)和(0,0)有紅點 並且任三點不共線

遊戲勝利的條件是  用g-1條線段把所有綠點連起來  用r-1條線段把所有紅點連起來

並且所有線段不交叉(共端點不算交叉)

保證一定有解  請輸出任意一種連線方案


Input

第一行: 整數g。接下來g行: 從綠點的編號1開始到g，每一行有二個以空白隔開的整數，
代表一個綠點的xi與yi 座標。第g+2行: 整數 r。接下來r行: 從紅點的編號1開始到r，
每一行有二個以空白隔開的整數，代表一個紅點的xi與yi 座標。

Output

共應輸出g-1+r-1行
每行包含兩個整數一個字元   前兩個整數代表這條線段所連接兩點編號
字元表示所連接兩點顏色


Sample Input
6
0 1000
1000 1000
203 601
449 212
620 837
708 537
8
0 0
1000 0
185 300
314 888
416 458
614 622
683 95
838 400


Sample Output
1 3 g
3 1 r
3 5 r
4 6 r
6 5 r
4 6 g
1 2 g
1 2 r
5 2 g
2 6 g
7 8 r
8 2 r



Solution:






這題目是很棒的D&C。時間複雜度：O(n lg n)


核心思想：

考慮一個三角形  v1 v2 v3 ，其中 v1,v2同色   v3異色

(1)如果中間沒有其他點    結束
(2)如果中間全部剩下的點同色    把那些點全部連到同一個頂點    結束
(3)其他：
選出一個跟v3同色的內部點vp，連v3-vp
然後對v1,v2,vp    v2,v3,vp   v3,v1,vp遞迴



很顯而易見遞迴三角形個數是和(g+r)同數量級，

如果對每個三角形O(g+r)檢查，就有了一個O((g+r)^2)算法   值55分


但是可以發現，其實對同一層    只需要合計O(g+r)的複雜度就可以
總共不會超過lg級別層，所以複雜度O(n lg n)ˇ



至於實做，我是以串列實做。










code(Judge程式，會告訴你是哪裡出錯)

http://codepad.org/rwc0RnZq

對了提一下，檢查是用Disjoint Set確定連通性，Sweep Line Algorithm檢查是否有交點




code(AC code)

http://codepad.org/q6v18QD5




testdata / solution (official)

http://olympiads.win.tue.nl/ioi/ioi2006/contest/day2/points/