師大附中集訓(xùn)

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

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

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

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

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

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