全國賽2008年浙江省省選第二試

1、2008 年浙江省省選第二試競賽時間：2008 年 6 月 13 日上午 8:00 12:00提交源程序須加后綴：對于Pascal 語言party.pastowasmovement.pasknight.pas對于C語言party.ctower.cmovement.cknight.c對于C+語言party.cpptower.cppmovement.cppknight.cpp題目名稱生日聚會瞭望塔無序運動騎士程序文件名partytowermovementknight輸入文件名party.ower.ovement.inknight.in輸出文件名party.outtower.outmovement.

2、outknight.out每個測試點時限1 sec2 sec3 sec2 sec測試點數(shù)目10101010每個測試點分值10101010生日聚會【問題描述】是 hidadz 小朋友的生日，她邀請了許多朋友來參加生日 party。不至于無聊，就hidadz 帶著朋友們來到花園中，打算坐成一排玩座的方案應(yīng)滿足如下條件：。為了對于任意連續(xù)的一段，男孩與的數(shù)目之差不超過 k。很快，小朋友便找到了案坐了下來開始。hidadz 的好朋友 Susie發(fā)現(xiàn)，這樣的就座方案其實是很多的，所以大家很快就找到了一種，那么到底有多少種呢？熱愛數(shù)學(xué)的hidadz 和朋友們開始思考這個問題假設(shè)參加party 的人有n 個

3、男孩與m 個，你是否能解答Susie 和hidadz的疑問呢？由于這個數(shù)目可能很多，他們只想知道這個數(shù)目除以 12345678 的余數(shù)。【輸入文件】輸入文件 party.in 僅包含一行共 3 個整數(shù)，分別為男孩數(shù)目 n,常數(shù) k。數(shù)目 m,【輸出文件】輸出文件party.out 應(yīng)包含一行，為題中要求的?！据斎霕永? 2 1【輸出樣例】1【數(shù)據(jù)規(guī)模】對于 30%的數(shù)據(jù)，n , m 20；對于 100%的數(shù)據(jù), n , m 150，k 20。瞭望塔【問題描述】致力于建設(shè)示范和諧小村莊的H 村村長dadzhi，決定在村中建立一個瞭望塔，以此加強村中的治安。H 村抽象為一維的輪廓。如下圖所示可以

4、用一條山的上方輪廓折線(x1, y1), (x2, y2), . (xn, yn)來描述H 村的形狀，這里 x1 x2 xn。瞭望塔可以建造在x1, xn間的任意位置,但必須滿足從瞭望塔的頂端可以看到 H 村的任意位置?？梢娫诓煌奈恢媒ㄔ觳t望塔，所需要建造的高度是不同的。為了節(jié)省開支，dadzhi 村長希望建造的塔高度盡可能小。請你寫一個程序，幫助dadzhi 村長計算塔的最小高度?！据斎胛募枯斎胛募?tower.in 第一行包含一個整數(shù) n，表示輪廓折線的節(jié)點數(shù)目。接下來第一行 n 個整數(shù),為 x1 xn. 第三行 n 個整數(shù)，為 y1 yn。【輸出文件】輸出文件tower.out 僅包

5、含一個實數(shù)，為塔的最小高度，精確到小數(shù)點后三位。【輸入樣例一】61 2 4 5 6 71 2 2 4 2 1【輸出樣例一】1.000【輸入樣例二】410 20 49 590 10 10 0【輸出樣例二】14.500【數(shù)據(jù)規(guī)?！繉τ?60%的數(shù)據(jù)， N 60；對于 100%的數(shù)據(jù)， N 300，輸入坐標(biāo)絕對值不超過 106，注意考慮實數(shù)誤差帶來的問題。無序運動【問題描述】D 博士對物理有著深入的，經(jīng)典物理、天體物理、量子物理都有著以他的名字命名的定理。最近 D 博士著迷于粒子運動的無規(guī)則性。對深信不疑的他相信，上帝創(chuàng)造的任何事物必然是有序的、有理可循的，而不是無規(guī)則的、混沌的。經(jīng)過長時間的，D

6、博士找到了很多出現(xiàn)相當(dāng)頻繁的軌跡片斷，他把這些軌跡片斷在一個很大的數(shù)據(jù)庫內(nèi)。他需要你幫助他寫一個程序，對于一個給出的粒子運動軌跡，統(tǒng)計數(shù)據(jù)庫中每個軌跡片斷的出現(xiàn)的次數(shù)。定義一個粒子的軌跡為二維平面上的一個點列（P1, P2, 為清楚起見，PN）。點列 P 的一個子列i, j定義為P 中一段連續(xù)的子序列（Pi, Pi+1, Pj）。點列 P 的一個子列u, v被稱為點列Q = (Q1, Q2 Qv-u+1)在P 中的一次出現(xiàn)，當(dāng)且僅當(dāng)Q 經(jīng)過有限次的平移、旋轉(zhuǎn)、翻轉(zhuǎn)、放縮之后得到 Q滿足Qk = Pu+k-1（k = 1 u v + 1）。對平面X-Y 進(jìn)行四種操作的解釋平移設(shè)平移向量為(dx,

7、 dy)，則任意點(x,y)平移后的結(jié)果為(x+dx, y+dy)旋轉(zhuǎn)設(shè)旋轉(zhuǎn)角為t，則任意點(x,y)旋轉(zhuǎn)后的結(jié)果為 (x cos t y s, x s+ y cos t)翻轉(zhuǎn)任意點(x,y) 翻轉(zhuǎn)后的結(jié)果為(x, -y)放縮設(shè)放縮比例為p (p 0)，則任意點(x,y)放縮后的結(jié)果為(px, py)【輸入文件】輸入文件 movement.in 第一行兩個整數(shù) N、M，分別描述待處理的粒子運動軌跡的點列大小與數(shù)據(jù)庫內(nèi)的軌跡片斷個數(shù)。接下來 M 行依次給出每個軌跡片斷。每行先是一個正整數(shù) K，表示該軌跡片斷點列的長度。然后 2K 個整數(shù)，依次描述點列中的 K 個點的橫坐標(biāo)與縱坐標(biāo)。接下來一行 2

8、N 個整數(shù)，依次描述待處理的粒子運動軌跡的點列中 N 個點的橫坐標(biāo)與縱坐標(biāo)。注：輸入中的每條軌跡中任意相鄰兩點不會相同?！据敵鑫募枯敵鑫募?movement.out 應(yīng)包含 M 行，依次給出每個片段在待處理運動軌跡中的出現(xiàn)次數(shù)?！据斎霕永? 221 -10 0 1 0 1 1【輸出樣例】21【數(shù)據(jù)規(guī)?！繉τ?30%的測試數(shù)據(jù)，N, M, K 100，片段總長度 500;對于 50%的測試數(shù)據(jù)，N, M, K 1 000，片段總長度 5 000;對于 100%的測試數(shù)據(jù)，滿足 N, K 200 000，片段總長度 200 000，輸入中給出所有點坐標(biāo)絕對值均不大于 10 000。騎士【問題描

9、述】Z 國的騎士團是一個很有的組織，幫會中匯聚了來自各地的精英。他們劫富濟貧，懲惡揚善，受到社會各界的贊揚。最近發(fā)生了一件可怕的事情，邪惡的Y 國發(fā)動了一場針對Z 國的。戰(zhàn)火綿延五百里，在和平環(huán)境中安逸了數(shù)百年的 Z 國又怎能抵擋的住 Y 國的軍隊。于是人們把所有的希望都寄托在了騎士團的身上，就像期待有一個真龍?zhí)熳拥慕瞪?，帶領(lǐng)正義打敗邪惡。騎士團是肯定具有打敗邪惡的能力的，但是騎士們互相之間往往有一些。每個騎士都有且僅有一個自己最厭惡的騎士（當(dāng)然不是他自己），他是絕對不會與自己最厭惡的人一同出征的。戰(zhàn)火綿延，人民生靈涂炭，組織起一個騎士軍團加入戰(zhàn)斗刻不容緩！國王交給了你一個艱巨的任務(wù)，從所有的騎士中選出一個騎士軍團，使得軍團內(nèi)沒有矛 盾的兩人（不存在一個騎士與他最痛恨的人一同被選入騎士軍團的情況），并且，使得這支騎士軍團最具有戰(zhàn)斗力。騎士按照 1 至 N為了描述戰(zhàn)斗力，給每名騎士一個戰(zhàn)斗力的估計，一個軍團的戰(zhàn)斗力為所有騎士的戰(zhàn)斗力總和?！据斎胛募枯斎胛募night.in 第一行包含一個正整數(shù) N，描述騎士團的人數(shù)。接下來 N 行，每行兩個正整數(shù)，按順序描述每一名騎士的戰(zhàn)斗力和他最痛恨的騎士。【輸出文件】輸出文件 knight.out 應(yīng)包含一行，包含一個整數(shù)，表示你所選出的騎士軍團的戰(zhàn)斗力。