師大附中集訓(xùn)

1、中山市市隊(duì) NOI2011 模擬賽第一試命題人競(jìng)賽時(shí)間：2011 年 7 月 xx 日上午 8:00-13:00提交源程序須加后綴注意：最終測(cè)試時(shí)，所有編譯命令均不打開(kāi)任何優(yōu)化開(kāi)關(guān)對(duì)于 Pascal 語(yǔ)言killassequence.passquares.pas對(duì)于 C語(yǔ)言killer.csequence.csquares.c對(duì)于 C+語(yǔ)言killer.cppsequence.cppsquares.cpp題目名稱(chēng)序列完全平方數(shù)目錄killersequenquares可執(zhí)行文件名killersequenquares輸入文件名killer.insequence.insquares.in輸出文件名k

2、iller.outsequence.outsquares.out每個(gè)測(cè)試點(diǎn)時(shí)限1 秒1 秒1 秒內(nèi)存限制512 兆512 兆512 兆測(cè)試點(diǎn)數(shù)目101010每個(gè)測(cè)試點(diǎn)分值101010是否有部分分無(wú)無(wú)無(wú)題目類(lèi)型傳統(tǒng)傳統(tǒng)傳統(tǒng)第一題【問(wèn)題描述】一位冷血的潛入 Na-wiat，并假裝成平民。希望能在 N 個(gè)人里面，查出誰(shuí)是。能夠?qū)γ恳粋€(gè)人進(jìn)行查證，假如查證的對(duì)象是平民，他會(huì)告訴，他認(rèn)識(shí)的人，誰(shuí)是，誰(shuí)是平民。假如查證的對(duì)象是將會(huì)把干掉?，F(xiàn)在掌握了每一個(gè)人認(rèn)識(shí)誰(shuí)。每一個(gè)人都有可能是，可看作他們是的概率是相同的。問(wèn)：根據(jù)最優(yōu)的情況，保證少？自身安全并知道誰(shuí)是的概率最大是多【輸入文件】輸入文件 killer.

3、in，第一行有兩個(gè)整數(shù) N,M。接下來(lái)有 M 行，每行兩個(gè)整數(shù) x,y，表示 x 認(rèn)識(shí) y（y 不一定認(rèn)識(shí) x,例如胡）?！据敵鑫募枯敵鑫募?killer.out 僅包含一行一個(gè)實(shí)數(shù)，保留小數(shù)點(diǎn)后面 6 位，表示最大概率。【輸入樣例】5111142345【輸出樣例】0.800000第 2 頁(yè) 共 6 頁(yè)第一題【樣例解釋】只需要查證 1。假如 1 是，就會(huì)被殺。假如 1 不是，他會(huì)告訴警但沒(méi)被殺的概察 2,3,4,5 誰(shuí)是率是 0.8。而 1 是的概率是 0.2,所以能知道誰(shuí)是【數(shù)據(jù)規(guī)?！繉?duì)于 30%的數(shù)據(jù)有 1N 10,0M 10對(duì)于 100%的數(shù)據(jù)有 1N 10 0000,0M30 000

4、0第 3 頁(yè) 共 6 頁(yè)第二題 序列序列【問(wèn)題描述】小 W 很喜歡序列，尤其喜歡“W”形的和“M”形的序列。定義“M”形的序列為一個(gè)長(zhǎng)度為 T 的序列Si，滿(mǎn)足：存在 1 x y z N，使得 S1 . . Sy . . ST。一天他看到了一個(gè)長(zhǎng)度為 N 的整數(shù)序列Ai，他想通過(guò)一些修改把序列變成 “M”形的。但這時(shí)小 X 過(guò)來(lái)了，說(shuō)這個(gè)序列是他的，小 W 如果想要修改就要支付一定的費(fèi)用。每支付一 的費(fèi)用，小 W 都可以進(jìn)行這樣的操作：將一段連續(xù)的數(shù)同時(shí)加上 1，即選定 i, j 滿(mǎn)足 1 i j N 并令 Ai, Ai+1, ., Aj 均加上 1。小 W 想用最小的費(fèi)用將序列變成“M”形的

5、。但是有個(gè)條件：如果他修改成的目標(biāo)是序列Bi滿(mǎn)足 B1 . . By . . BN，那么必須有 Ay=By?，F(xiàn)在，他希望你來(lái)幫他計(jì)算最小費(fèi)用?！据斎胛募枯斎胛募?sequence.in 第一行包含一個(gè)整數(shù) N，表示序列 A 的長(zhǎng)度。第二行有 N 個(gè)整數(shù)給出初始的序列Ai。【輸出文件】輸出文件 sequence.out 僅包含一行，為最小的花費(fèi)。【輸入樣例】52 1 2 2 3【輸出樣例】4【數(shù)據(jù)規(guī)?！繉?duì)于 30%的數(shù)據(jù)滿(mǎn)足 N 1 000；對(duì)于 100%的數(shù)據(jù)滿(mǎn)足 5 N 100 000，0 Ai 109。第 4 頁(yè) 共 6 頁(yè)第三題 完全平方數(shù)完全平方數(shù)【問(wèn)題描述】小 X 自幼就很喜歡數(shù)。

6、但奇怪的是，他十分討厭完全平方數(shù)。他覺(jué)得這些數(shù)看起來(lái)很令人難受。由此，他也討厭所有是完全平方數(shù)的正整數(shù)倍的數(shù)。然而這絲毫不影響他對(duì)其他數(shù)的熱愛(ài)。這天是小 X 的生日，小 W 想送一個(gè)數(shù)給他作為生日。當(dāng)然他不能送一個(gè)小 X 討厭的數(shù)。他列出了所有小 X 不討厭的數(shù)，然后選取了第 K 個(gè)數(shù)送給了小 X。小 X 很開(kāi)心地收下了。然而現(xiàn)在小 W 卻記不起送給小 X 的是哪個(gè)數(shù)了。你能幫他一下嗎？【輸入文件】輸入文件 squares.in 包含多組測(cè)試數(shù)據(jù)。文件第一行有一個(gè)整數(shù) T，表示測(cè)試數(shù)據(jù)的組數(shù)。第 2 至第 T+1 行每行有一個(gè)整數(shù) Ki，描述一組數(shù)據(jù)，含義如題目中所描述?！据敵鑫募枯敵鑫募?squares.out 含 T 行，分別對(duì)每組數(shù)據(jù)作出回答。第 i 行輸出相應(yīng)的第 Ki 個(gè)不是完全平方數(shù)的正整數(shù)倍的數(shù)?！据斎霕永?1131001234567【輸出樣例】1