全國(guó)賽2008年浙江省省選第二試

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

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

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

4、用一條山的上方輪廓折線(x1, y1), (x2, y2), . (xn, yn)來(lái)描述H 村的形狀，這里 x1 x2 xn。瞭望塔可以建造在x1, xn間的任意位置,但必須滿足從瞭望塔的頂端可以看到 H 村的任意位置?？梢?jiàn)在不同的位置建造瞭望塔，所需要建造的高度是不同的。為了節(jié)省開(kāi)支，dadzhi 村長(zhǎng)希望建造的塔高度盡可能小。請(qǐng)你寫一個(gè)程序，幫助dadzhi 村長(zhǎng)計(jì)算塔的最小高度?！据斎胛募枯斎胛募?tower.in 第一行包含一個(gè)整數(shù) n，表示輪廓折線的節(jié)點(diǎn)數(shù)目。接下來(lái)第一行 n 個(gè)整數(shù),為 x1 xn. 第三行 n 個(gè)整數(shù)，為 y1 yn?！据敵鑫募枯敵鑫募ower.out 僅包

5、含一個(gè)實(shí)數(shù)，為塔的最小高度，精確到小數(shù)點(diǎn)后三位。【輸入樣例一】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ī)?！繉?duì)于 60%的數(shù)據(jù)， N 60；對(duì)于 100%的數(shù)據(jù)， N 300，輸入坐標(biāo)絕對(duì)值不超過(guò) 106，注意考慮實(shí)數(shù)誤差帶來(lái)的問(wèn)題。無(wú)序運(yùn)動(dòng)【問(wèn)題描述】D 博士對(duì)物理有著深入的，經(jīng)典物理、天體物理、量子物理都有著以他的名字命名的定理。最近 D 博士著迷于粒子運(yùn)動(dòng)的無(wú)規(guī)則性。對(duì)深信不疑的他相信，上帝創(chuàng)造的任何事物必然是有序的、有理可循的，而不是無(wú)規(guī)則的、混沌的。經(jīng)過(guò)長(zhǎng)時(shí)間的，D

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

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

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

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