CEOI

2012試題分析與方法討論1清華大學王宏CEOI

2012基本情況2英文題目中文題目類型主要方法day1jobs工作安排傳統二分circuit印刷電路板傳統計算幾何race帆船比賽傳統動態規劃day2highway公路設計交互分類討論wagon垃圾回收傳統枚舉network網絡傳統強連通分量試題概覽CEOI

2012基本情況3得分情況試題名稱平均分最高分最低分滿分人數Day1jobs68（77）100026（124）circuit30（20）10000（2）race22（11）95（100）04（12）Day2highway60（25）100（80）021（0）wagon25（14）10005（13）network52（36）100013（40）說明：括號內是網絡同步賽數據，平均分針對得分的選手統計CEOI

2012基本情況4金牌分數線520（5人），銀牌分數線280（10人），銅牌分數線199（14人）。網絡同步賽吸引了400名選手報名參加，其中得分的有

209人，最高分580（俄羅斯EgorSuvorov），第5名到第15名之間，除了第12名以外全是我國選手，最好成績第5名（陳立杰485）。從整個成績來看，除了highway因為區分度不好造成較大的差距以外，其他題目的成績分布，網絡同步賽與正式比賽基本一致。這里選擇兩試得分相對偏低的3道試題（circuit、race

、wagon）進行討論。Day

1Printed

Circuit

Board5問題描述6根據維基百科，印刷電路板(PCB)，主要用于機械支撐并通過蝕刻銅層壓板上的絕緣基板形成導電通路以連接電子元件。某公司準備生產一種用印刷電路板組裝的新型電子設備。設計要求的印刷電路板外形是一個封閉的多邊形，由編號1到N的N個結點組成，結點u和結點u+1、結點N和結點1用直線導線線段連接。導線線段之間沒有交叉，有共同點的任何一對導線線段，其共同點只能是兩者的一個端點，并且每個結點都是兩個線段的端點。每個結點的位置用x坐標和y坐標表示，原點(0,0)位于板的左下角。編程計算電路的所有結點中，用一條直線導線線段連接原點，除了本身以外與多邊形沒有其它共同點的結點。輸入輸出與問題規模7輸入第一行一個整數N(1≤N≤100000)，表示多邊形結點個數。接下來N行，每行包含兩個整數x、y(0<x,

y≤1000000)，分別表示結點的x坐標和y坐標。結點從1到N編號，第i+1行表示結點i的坐標。10%的測試數據，N不超過1000。輸出第一行包含一個M，表示用直線導線線段連接到原點，與多邊形的任何線段除了本身外沒有任何共同點的結點數目。第二行用升序輸出這些結點，用空格隔開。如果第一行輸出正確，可得40%的分數。題目簡述8一個由結點P序列組成的封閉多邊形，每個點的位置用x坐標和y坐標表示。多邊形的邊是P[i],P[i

+1](i<n)和P[n],P[1]。要求計算從原點能夠看到的多邊形結點。時限0.1s,

內存32M這是CEOI2012得分最低的一道題目，網絡賽前50名的平均分不到40分。只有兩位選手獲得滿分（俄羅斯的EgorSuvorov和我國的劉定峰），40分以上的選手19人。樣例輸入117

64

43

21

39

913

48

16

49

58

311

5輸出33

4

79分析10按照順時針方向，結點7、4分別是從原點能夠看到的第一個(first)和最后一個(last)結點。這兩個結點將多邊形分成了上、下兩部分從原點只可能看到下部結點，而上部結點在原點是無法看到的（如結點5、6）。因此，需要處理的只是從first到last之間的下部結點。查找first、last結點基本思路根據線段的旋轉方向旋轉方向Turn(a,b,c)的定義如果結點P[a]、P[b]、P[c]在一條直線上，返回0。若P[b],P[c]在點P[b]處左轉則返回1；右轉返回-1。判斷公式(P[b].x

-

P[a].x

)

*

(P[c].y

-

P[a].y)

-

(P[c].x

-

P[a]

.

x

)

*

(P[b].y

-P[a].y)用0表示原點，Turn0(a,

b)表示Turn(0,a,b)判斷公式P[a].x

*

P[b].y

-

P[b].x

*

P[a].y11查找first、last結點first結點定義Turn0(first,u)>0Turn0(first,u)=0，且

P[first].x<P[u].x（在同一直線上，選擇靠近原點的結點）last結點定義Turn0(last,u)<0Turn0(last,u)=0，且

P[last].x<P[u].xnext(i)、prev

(i)分別表示結點i的下一個結點和前一個結點12查找first、last結點13實現方法fab

=

Turn0(first,i);if(fab

<

0

||

fab

==

0

&&

P[i].x

<

P[first].x)first

=

i;fab

=

Turn0(last,i);if(fab

>

0

||

fab

==

0

&&

P[i].x

<

P[last].x)last

=

i;特殊數據的處理14如果next(first)==last，說明first和last之間沒有其他結點，能夠看到的結點只有兩個（答案輸出的第一行就是2），不需要進行后續處理。需要注意的是輸出具體結點時，要按結點編號的升序輸出。相鄰結點的旋轉關系prev(a)如果線段

P[a],

P[next

(a)]

不滿足Turn0(a,

next(a))

≥

0（右轉），那么結點a可能不可見；如果結點a可見，那么

Turn0(prev(a),

a)>0（左轉）。即，只有左轉的線段端點才可見。因此，可以只考慮左轉的線段（Turn0(a,

next(a))>0）。15結點之間的遮擋關系對每一個結點i

考慮集合Q(i)Q(i)

=

{

j:

Turn0(i,

j)

≤

0 and

Turn0(i,

next(j))

≥

0}遮擋關系判斷方法（在多邊形線段中找與0i直線有交叉if

(Turn0(i,

j)>=0)

的線段的端點）return

Turn(i,

next(i),

j)<=0;elsereturn

Turn(j,

next(j),

i)>0;在Q(i)中，結點u在v的前面（v被u遮擋），當且僅當直線l(0,i)與線段P[u

],P[next

(u

)]的交點離原點的距離比l(0,i)與線段P[v],P[next

(v)]的交點更近。16結點i是否可見的情況分析next(i)i①結點i可能可見②結點i不可能可見③結點i可能可見④結點i可能可見inext(i)inext(i)next(i)prev(i)prev(i)iprev(i)prev(i)②中結點i不可見的原因是必然被prev(i)與first或者next(i)與last之間的多邊形遮擋;①③④中i的共同點是以i為端點的線段至少有一條是左轉的17結點之間的遮擋關系從圖中可以看出，Q(i)中結點之間的遮擋關系是一個有序序列根據遮擋關系，如果結點a滿足Turn0(a,next(a))>0或者Turn0(prev(a),a)>0，當且僅當a是Q(a)中的最小元素（即位于最前面）時，a是可見的（左轉線段的端點）。18實現方法19首先對first與last之間的結點按照極角進行快速排序排序依據int

ord_rel(const

void* a,

const

void*

b){int

i

=

*(int*)

a

;

int

j

=

*(int*)b;int

tij

=

Turn0(i,

j);if(tij

>

0

||

tij

==

0

&&

P[i].x

<

P[j].x)return

-1;elsereturn

1;}實現方法20用二叉堆（優先隊列）實現集合Q(i)對每一個待處理的結點a如果prev(a)是堆頂元素，且Turn0(a,Ps[i

-

1])

!=0，（未被遮擋）那么結點a滿足題目要求，刪除結點prev(a)Ps[]表示排序后的結點如果Turn0(a,next(a))>0，在集合中插入結點a，如果a是堆頂元素，且Turn0(a,Ps[i-1])!=0，那么a滿足題目要求（注意避免重復記錄）復雜度分析21如果first與last之間有k個元素，則插入和刪除結點的時間復雜度是O(log

k)。查找堆中的最小元素是O(1)。按極角快速排序的復雜度是O(n

log

n)因此，整體時間復雜度是O(n

log

n), n

是結點的數目。Day

1Sailing

Race22問題描述23一年一度的帆船比賽在一個圓形湖面上舉行。環湖有N個碼頭，按逆時針方向從1到N編號。比賽由若干個階段組成，每個階段從一個港口沿直線到達另一個港口，賽道經過某個碼頭的次數不能多于1次。組織者想讓賽道包含的階段數目最大化。必須注意的是在某個碼頭，帆船只能沿直線路徑到達指定的碼頭。每個碼頭A都有一個能夠直接到達的目的地列表。通常情況下，為了避免帆船沖突，賽道各個階段不能交叉。然而，今年采用了一種新技術，允許在第一階段上出現一個交叉。因此，如果賽道從港口S開始，賽道的下一港口是T，那么最多有一個階段能夠與第一個階段S-T交叉。組織者決定允許這樣的1個交叉，或者選擇沒有交叉的經典設計。編程計算包含最大可能階段數目的賽道。輸入輸出與問題規模24輸入第一行2個整數，第一個數N(1≤N≤500)表示港口數目，第二個數k表示賽道的類型。如果k=0，表示要求傳統賽道（沒有交叉）；k=1表示賽道最多包含1個前面所述的交叉。40%的數據k=0，50%的數據N≤100

。接下來的N行是各個港口能夠直接到達的目的地列表，第i+1行包含港口i

的列表，整數之間用空格隔開，每行以0結束。輸出第一行包含1個整數M，表示指定類型賽道包含階段的最大數目。第二行包含1個整數，表示這個賽道起點港口的編號。如果有多個答案，你可以輸出其中任意一個。第一行答案正確沒有部分成績。時限3s,內存32M樣例輸入7

15

05

07

03

04

04

3

02

1

0輸出5225沒有交叉的情況如果沒有交叉(k=0)，階段和狀態(從起點港口到當前港口的賽道包含的最大階段數)非常明顯，很容易想到動態規劃的方法。沿著賽道不難發現，到過的港口把湖岸分割成港口之間的若干間隔。因此，進入某個間隔之后就不能離開，否則就會出現交叉。如圖所示，在賽道的尾部就不能離開間隔B-D。26沒有交叉的情況27對港口A、B用ed(A,B)表示在間隔[A,B)內從A開始的最長賽道，即從A開始沿逆時針方向經過的港口集合（不包含B）用edc(A,B)表示在間隔[A,B)c

內沿順時針方向得到的最大值狀態轉移方程ed(

A,

B)

=

max

{1+

max{ed(C,

B),

edc(C,

A)}}C?[

A,B)$A-C

route如果C不存在，定義最大值為0沒有交叉的情況28計算edc(A,B)的方法類似港口A到B之間的最長路徑maxlength(A,

B)

=

max{ed(A,

B),

edc(A,

B)}時間復雜度O(N(N+E))，E表示當前港口能夠直接到達的目的地數目得分40分（僅考慮不交叉的情形，k=0

）。允許交叉的情況一個錯誤的觀察或推理有交叉的情況，如果把第一個階段去掉，剩下的部分就沒有交叉，很直接的就會想到允許交叉的最大值比沒有交叉的最大值多

1但是這個推理并不正確——剩下的部分不一定是沒有交叉的最大值。而且，有交叉的最大值也不一定比沒有交叉的最大值大因此，需要另外計算有交叉的最大值，并且比較二者的大小以確定最終的答案。K=1允許有一個交叉或沒有交叉29有交叉的情況分析假設賽道從港口A開始，下一個港口是B，然后從港口C到港口D的階段與階段A-B交叉。對指定的A、B、C、D有兩種情況：A、C、B、D的順序是順時針方向或逆時針方向。假設是順時針方向（逆時針方向處理方法類似）。30有交叉的賽道產生過程第一階段肯定是A-B在間隔[B,

C]內賽道只能沿逆時針方向“單調”前進不難看出，如果在間隔[B,C]內順時針前進除了允許的交叉外至少會增加一個額外的交叉然后是階段C-D賽道最后在間隔[D,

A)c或者[D,B)中結束31有交叉最長賽道的計算32用md(B,C)表示從港口B到C沿逆時針方向“單調”前進的最長路徑，同樣用動態規劃方法（在前面的方法基礎上限定下一個港口只能按逆時針方向尋找）計算，時間復雜度O(N(N+E))對指定的港口A、B、C、D，maxlength(A,B)的狀態轉移方程maxlength(A,

B)=1+md(B,C)+1+max{edc(D,A),ed(D,B)}}加的兩個1分別是A-B、C-D枚舉所有的A-B、C-D，時間復雜度為O(N2+E2)得分70-75分優化33假設只指定B、C、D，在間隔(C,D)中優化選擇A如果賽道在間隔[D,B)中結束，A的選擇沒有影響；在間隔[D,

A)c中結束，需要最大化edc(D,A)，顯然，如果A離D越遠，edc(D,A)值可能越大，那么盡量選擇靠近C的存在A-B路徑的港口為了找到A，甚至可以不指定D。從指定B、C開始，找到唯一的A，然后查找可能的D。總的時間復雜度

O(N2)。得分100。Day

2Waste

Recycling（垃圾回收）34問題描述35物資回收公司需處理鐵路貨車運來的垃圾。在進站的鐵路軌道上有N輛鐵路貨車，每輛貨車只包含一種垃圾。并將根據固定數目設置中的一種進行垃圾處理。對每一種設置給出能夠處理的垃圾種類的集合。由于改變設置非常耗時，因此公司一天只采用一種設置。垃圾將按照到達進站軌道的順序處理。為加快回收速度，公司已經建成如圖所示的輔助軌道。如果到達貨車的垃圾種類當前設置無法處理，可以把它移到輔助軌道。進站軌道或者輔助軌道中的第一輛貨車是下一個將要處理的對象。注意貨車不能從輔助軌道回到進站軌道。公司想在接下來的3天中回收盡可能多的垃圾。在第三天結束時，輔助軌道必須為空。問題描述編寫一個程序計算3天的設置安排，求出滿足輔助軌道最終為空時能夠處理的貨車最大數目。如果處理完所有貨車的時間少于3天，必須給出最少天數的解決方案。36輸入輸出與問題規模37輸入第一行3個整數N(1≤N≤20000)、K(1≤K≤1000)、S(1≤S≤1000)，分別表示貨車、垃圾種類、設置的數目。即，貨車從1到N編號、垃圾種類從1到K編號、設置從1到S編號。50%的數據，N

≤10000，S

≤300。接下來S行對設置進行描述，第i+1行的整數表示設置i能夠處理的垃圾種類，整數之間用空格隔開，每行以0結束。最后一行包含描述貨車的N個整數，第i個數表示第i輛貨車的垃圾種類。對于每種垃圾，將有至少1種、最多10種設置會包含它（能夠處理）。輸出第一行包含1個整數，表示能夠處理的貨車最大數目。第二行包含3個用空格隔開的整數，分別表示第一、二、三天的設置。如果兩天能夠處理完所有的貨車，第3個數字必須是0。如果1天能夠處理完，后兩個數字必須是0。如果有多個答案，僅需輸出其中任意一個。如果第一行答案正確，可得40%的分值限制：時限1s，內存32M38樣例39輸入13

5

41

04

5

05

3

02

5

04

5

2

5

5

4

1

1

5

4

5

3

3輸出112

1

4分析40樣例處理過程：設置2：處理4 5，2進入輔助軌道，處理5

5

4，1

1進入輔助軌道，處理5

4

5設置1：處理1

1設置4：處理233無法處理，最多處理11輛（如果要處理33，必須要第4種設置）第幾天設置處理垃圾種類124

5211342

5思考41選3種設置的排列，使能夠處理的貨車數目最大→直接枚舉？時間復雜度O(n*s3)注意到題目描述中，“每種垃圾都有至少1種、最多10種設置能夠處理”，因此只需要對包含這種垃圾的設置進行處理即可。時間復雜度O(n*103)但是，對每一個序列都必須找出能夠處理的最大長度，時間復雜度O(n2*103)，可以優化簡化42為了便于理解，我們可以把問題簡化為考慮一個設置只能處理一種垃圾的情況，那么可以用垃圾種類代替設置。輸入的垃圾類型

x1,...,xi,...,xn。3天的設置方案可用一個三元組(a,b,c)表示，

a、b、c分別表示第一、二、三天的設置（垃圾種類）。從第一輛貨車開始，依次對各種可能的狀態(a,b,c)進行處理。處理過程中可能出現的狀態①43②③④⑤處理過程中可能出現的狀態44(0,

0,0)：初始狀態

(a,

0,0)：第一天處理a類垃圾

(0,

0,c)：c類垃圾移到輔助軌道第三天處理

(a,0,c)：第一天處理a類垃圾；c類垃圾移到輔助軌道第三天處理

(a,b,c)：第一天處理a類垃圾；b類、c類垃圾移到輔助軌道，c類先進輔助軌道(-a,b,c)：第二天處理b類，c類在輔助軌道（a已經處理）狀態的數據結構定義45typedef

struct

triple

{int

a,b,c;}triple;triple

Q[maxQ];/*數組Q用來保存處理到當前貨車可能出現的各種狀態*/int

qfirst=0,qnext=0;void

put(int

x,int

y,int

z){triple

t;t.a=x;

t.b=y;

t.c=z;Q[qnext]=t;qnext=(++qnext)%maxQ;}triple

get(

){triple