NTUJ 1021 Highway Patrol

36916    1021 - Highway Patrol    poao899    Accepted    C++    0.030    2010-09-05 19:41:21                            .



好題欸@@



題意：

一個大都會內有N座城市(<=100)，有M條單行道(<=1,000)

每個單行道可以用一個數組(u, v, p, s, x)表示，表示有一條道路從u往v，

如果要派軍隊巡邏要花費p的代價、裝監視器要s的代價 (0 <= p,s <= 1,000,000)

x代表這條道路的重要性，1表示極為重要，不可以用監視器。


因為這個大都會治安很差，每條道路都必須選擇上述兩種方式之一維持治安品質。

但是，每個軍隊巡邏完了要能回到自己的城市休息，所以我們希望每個城市出分枝度 == 入分枝度。

而且，市民們也不希望看到一個全部僅由監視器戍守的城市，所以至少得有一條路是巡邏。


問最少需要花多少錢滿足以上要求。





Input:

第一行有一個數字T表示測資筆數(T <= 70)

每筆測資第一行是N, M，接下來M行每行有五個數字u, v, p, s, x。


Output:

第i筆測資輸出Case [i]: [cost]

[i]表示測資筆數，[cost]表示你所花的錢，無解請用"impossible取代"。



Sample input:

3
4 5
1 2 10 25 0
2 3 10 5 0
3 1 10 5 0
2 4 10 5 0
4 3 30 5 0
4 5
1 2 10 25 0
2 3 10 5 0
3 1 10 5 0
2 4 10 5 0
4 3 30 5 1
2 1
1 2 10 25 1

Sample output:
Case 1: 40
Case 2: 65
Case 3: impossible























=================Solution================





簡單的先捏一下，flow。





因為把這個問題轉化一下可以想到，你可以假設一開始全部監視，那這樣總cost是Σ(si)。

然後每把一個邊變成巡邏的cost會是(pi-si)。

而且最後答案一定巡邏的邊會形成好幾個環。

所以就一直找全局最小環加上去，加到那個環是正的為止。

進一步會發現，變成有負圈的圖形每次尋找全局最小簡單環。不過很可惜這個題目沒多項式作法。



所以要換一個想法。


可以先把p便宜的邊先巡邏、s便宜的邊先監視。

然後建起來可替換邊以及他的替換代價，容量都是1

然後對每個點，檢查有幾個巡邏出發/幾個巡邏回來   其中的相差就建到S/E，cost=0，容量是差。

作一次帶權flow，算出答案...



然後還要檢查答案是否合法：如果==Σ(si)那就表示你一個邊都沒取

所以Warshall一次，找出最小圈輸出

PKU 2540 Hotter Colder [CG]

7564334    poao899    2540    Accepted    424K    0MS    G++    3998B    2010-09-02 22:09:01                         .



CG題好硬QQ不過應該是打定了XD寫起來頗有成就感(?)

看那精美的code length(望

不過   看到這題還是會想到IOI那個吧XD





題目大意：

有個房間，大小10*10

你一開始站在(0,0)，某個位置有一個熱源。

接下來每次你會移動到任意一個座標，然後會告訴你感覺Hotter還是Colder還是Same

每次移動輸出一個數字表示  "熱源可能位置"  的面積。

保證不會移動超過50次。





Sample Input：

10.0 10.0 Colder
10.0 0.0 Hotter
0.0 0.0 Colder
10.0 10.0 Hotter

Sample Output：

50.00
37.50
12.50
0.00



















===============解題報告===============


等於每次對多邊形切一條線，問面積。

測資很小所以可以每次把所有點掃過一遍。


幾個要注意的地方：

1.  判斷交點要注意等於0的狀況= =
2. 把兩個交點去修正多邊形時要注意加入的順序。
3. 注意如果重複點加入多邊形，會爆炸。




大概差不多這樣吧xD

POI - PA 2010 Round 2 Coins

翻譯:

給你n, k還有一個由R, O組成的長度n的序列。

找出區間[i, j]使得這個區間內O的個數是R的k倍，這個區間最長能多長

n, k <= 1,000,000


Sample Input:
15 3
RORROOROOROOORO



Sample Output:
8





solution:

這題跟之前USACO一題有異曲同工之感。

http://acm.pku.edu.cn/JudgeOnline/problem?id=3274

定義f(i) = 1~i出現多少個R - (i/(k+1))

那麼會發現，若f(a) == f(b)則 [a+1, b]必為合法區間

排序 O(n lg n)或Hash O(n)就結束了。

蝴蝶作法雖然核心一樣不過細節完全不同，雖然一樣O(n lg n)

POI 11th Spies

題外話：

這題是POI XI Stage I當年第二多人寫出來的題目


最多那題沒有放在main上面QQ


當年這題 190/334 個滿分，不過我覺得這題明明沒有簡單到這種程度= =


// 好罩電波一定覺得是秒殺題


噢然後，Example裡面有一個1打成小寫L，我在想怎麼一直RE





翻譯：

BIA僱用了很多間諜，每個間諜都被下令要監視其他另一個間諜。

KB想要選一些間諜去進行絕密任務，而且他希望能委任越多間諜越好。

然而這個任務太重要了，所以他希望每個被委任的間諜都至少被一個沒有參與任務的間諜
監視。（而且目前的跟監關係不能變動。）


輸入第一行含一個數字n <= 1,000,000，表示共有n個間諜，接下來會有n行

第i+1行會有一個數字Ai，表示間諜i的跟監對象是Ai。

輸出包涵一個數字K，表示最多可以委任K個間諜並符合題目要求。



Example:
6
2
3
1
3
6
5

the correct result is:
3

===================================題解========================





保證每個點都只會有一條連出去的邊，所以每個連通塊一定是一些鍊，

然後有可能在末尾出現一個環。


對於那些鍊，有一個很明顯而且好證的貪心法就是：


1. 如果那個點入分枝度為零，不能取
2. 如果進入那個點的所有點中有任何一個沒有被取的，那麼他就可以取

然後再來處理每個環：

1. 如果那個環所有點入分枝度都是1 -> 可以取  環長/2 取高斯個點
2. 如果那個環有些點入分枝度 > 1 且有至少一個進入他的點沒被取  那他也可以取
   然後剩下的點依照跟鍊一樣的邏輯取完。


總複雜度 O(V)

COCI 2009/2010 #3 p5

標題好長XD


簡單的說

第一行有兩個數字N, C

接下來給你一條數列S  ，長度是N(<=300,000)，裡面的數字範圍是1~C(<=10,000)

第三行是一個數字M(<=10,000)表示有幾組詢問

接下來M組詢問，每組有L, R(1<=L<=R<=N)

問你閉區間[L, R]中有沒有哪個數字出現超過一半？有的話問是哪個數字？

Sample input:
10 3
1 2 1 2 1 2 3 2 3 3
8
1 2
1 3
1 4
1 5
2 5
2 6
6 9
7 10

Sample output:
no
yes 1
no
yes 1
no
yes 2
no
yes 3


全國賽那天晚上戰的COCI的題目(轉

小鬼當時說他會做了不知道跟官方solution一不一樣(欸

shik表示：蒙地卡羅應該會過


不過官方solution好好玩(打滾











========================solution===================


先不要考慮原題目，來想另一個遊戲：

給你一個序列S，每次可以把S裡面相異兩個數字抹掉。

直到全部都剩下同一個數字時遊戲結束

例如 12312323->312323->1323->33m 時結束。

這時紀錄兩個數 candi表示剩下的數字是什麼  count表示結束狀態多長

例如上述例子   candi=3 count=2




引理：如果有個數字出現超過length/2次，那他一定會是candi，無論過程

那麼，我們只要維護一棵seg tree就可以作到區間查詢candi了ˇ

就是分L.candi==R.candi以及L.candi!=R.candi時比兩個count大小

然後求出這個區間的candi，再去用另一棵seg tree計算他出現幾次

如果出現>length/2次就是yes  否則則是no

IOI &#39;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/