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

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

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

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

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

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