國家集訓(xùn)隊作業(yè)出題互測解題報告apex

1、x解題福州一中April 30, 2012Contents1題意簡述22命題思路23考查點24問題分析25數(shù)據(jù)生成方法46選手得分統(tǒng)計47后記5Appendi7x完整題面A7嬱1題意簡述Pn i=1定義數(shù)列x1 嬽 嬱, x2k 嬽下嬳種詢問。嬽 嬨嬱嬩k+1xk嬨k 嬱嬩，設(shè)Sn 嬽xi。有以xk, x2k1嬱嬮 求xn；嬲嬮 判斷Sn的符號；嬳嬮 求Sn。2命題思路本題是本人在做一道數(shù)學(xué)題時想出的。一開始打算利用程序來找規(guī)律，后來靈機一動，弄出了一個重要的等式。雖然那道數(shù)學(xué)題沒有完整解出來，不過本人想到可以利用這個等式編一道有意思的題目。這嬳問設(shè)計得很有層次性，即使某一問不會做，也很有可能

2、做出其他的詢問。而這嬳問又具有聯(lián)系。3考查點本題主要了選手代數(shù)方面的能力，以及分析問題，尋找規(guī)律的能力。4問題分析這類問題通常有兩種思路。一種是預(yù)處理出所有，然后碰到詢問直接回答；另一種是對每個詢問單獨處理。如果采用第一種思路，可以考慮預(yù)處理出x1, x2, . . . , xn，以及S1, S2, . . . , Sn，然后就可以以O(shè)嬨嬱嬩的時間復(fù)雜度回答每個詢問。預(yù)處理出x1, x2, . . . , xn，可以直接利用數(shù)列定義式來完成，時間復(fù)雜度是O嬨n嬩。而預(yù)處理出前n項和Sn的時間復(fù)雜度也是O嬨n嬩的。這個算法的期望得分是嬵嬰分。由于預(yù)處理出n以內(nèi)的所有的時間復(fù)雜度下限就是嬊嬨n嬩，

3、這種思路在n很大時無法勝任。因而考慮第二種思路。嬲第一問十分簡單。我們直接利用題目所給的數(shù)列定義式，就可以求出xn的值了。這一問的時間復(fù)雜度是O嬨孬孯孧 n嬩。再看第二問，容易發(fā)現(xiàn)，如果解決了第三問，那么第二問也解決了。因而先嘗試解決第三問。考慮S4n嬨n 嬱嬩。根據(jù)x2k 嬽 xk, x2k1 嬽 嬨嬱嬩k+1xk嬨k 嬱嬩，4nXS4n嬽xii=12n2nXX嬽x嬫x2i12ii=1i=12n2nXXi+1嬽嬨嬱嬩x xiii=1i=12nXi+1嬽嬨嬨嬱嬩x x 嬩iii=1nX嬽嬲x2ii=1nX嬽 嬲xii=1嬽 嬲Sn嬨嬱嬩由式嬨嬱嬩， 立即得到一個快速求Sn的做法： 若嬴 - n

4、， 那么Sn嬽 Sn1 嬫 xn； 否則，Sn 嬽 嬲Sn。這個算法的時間復(fù)雜度由下式給出：T 嬨n嬩 嬽 T 嬨n/嬴嬩 嬫 O嬨孬孯孧 n嬩，解得T 嬨n嬩 嬽 O嬨孬孯孧2 n嬩。注意到這個算法有系數(shù)嬳，即每次除以嬴，最多要嬳輪。我們還可以對此進行一些優(yōu)化。注意到2n+2x4n+1 嬫 x4n+2 嬽 嬨嬱嬩x2n+1 x2n+1 嬽 嬰嬨嬲嬩我們可以得到S4n+2 嬽 S4n 嬫 x4n+1 嬫 x4n+2 嬽 S4n嬨嬳嬩這樣，我們在每一次除以嬴的時候最多只要算嬱次xn，就消除了系數(shù)嬳。有了第三問，第二問顯然也可以做到O嬨孬孯孧2 n嬩。不過我們有更優(yōu)的算法。首先，可以用數(shù)學(xué)歸納法證

5、明，Sn 嬰。因而，我們只需要找出哪些位置是嬰。嬳容易看出，S2n1 6嬽 嬰。這是因為， 數(shù)列xn只含數(shù)字嬱和嬭嬱。由于Si+1 嬽 Si 嬫 xi+1，因此Si+1與Si奇偶性不同。而S1 嬽 嬱為奇數(shù)，S2n1與S1奇偶性相同，因而也為奇數(shù)。而嬰是偶數(shù)，故而S2n1 6嬽 嬰。根據(jù)式嬨嬱嬩嬨嬳嬩， 以及S2 嬽 嬰, S4 6嬽 嬰， 可以看出Sn 嬽 嬰當(dāng)且僅當(dāng)n的嬴進制表示僅含嬰和嬲。這樣第二問就做到了O嬨孬孯孧 n嬩。5數(shù)據(jù)生成方法本題的數(shù)據(jù)生成方法十分容易，只需要依據(jù)數(shù)據(jù)范圍，直接隨機生成即可。不過對于詢問嬲，仍然遇到了一點問題。注意到在上述分析中提到了詢問嬲，回答是嬰的條件。在

6、嬱至嬱嬰18內(nèi)，回答是嬰的數(shù)的個數(shù)大概只有嬲29。當(dāng)在嬱至嬱嬰18范圍內(nèi)隨機時，隨機到嬰的概率小于嬱嬰9。即使隨機嬱嬰5次，存在一個回答是嬰的數(shù)的概率仍小于嬰嬮嬰嬱嬥。事實上，對于大的隨機數(shù)據(jù)，所有詢問嬲的回答都是正數(shù)。因為發(fā)生了這種情況，本人對大數(shù)據(jù)詢問嬲的生成進行了一些改動，手造了一些回答是嬰的情況，混合進去，從而避免了全部是正數(shù)導(dǎo)致的數(shù)據(jù)的不全面。6選手得分統(tǒng)計本題對國家隊候選隊員進行了測試，得分統(tǒng)計如表嬨嬱嬩所示?？讓L孢孬孥 嬱嬺 得分統(tǒng)計本題的平均分大約為嬸嬲嬮嬤分。嬴分數(shù)人數(shù)嬲嬰嬱嬶嬰嬱嬶嬵嬲嬱嬰嬰嬤7后記本題是一個數(shù)列問題。正如來自南京師大附中的同學(xué)所言，數(shù)列問題往往可以用孯孥孩

7、孳來解決。這里，孯孥孩孳，可參考孛嬱孝，指的是一個整數(shù)數(shù)列，收錄了數(shù)以萬計的數(shù)列，包含了豐富的數(shù)列的性質(zhì)。如果本題可以輕易地用搜索工具搜索到性質(zhì)，甚至通項，那么本題就顯得十分沒有意義了。有鑒于此，本人對此數(shù)列進行搜索，幸運的是，這個根本沒有這個數(shù)列。利用知名的搜索引擎進行搜索，也沒有發(fā)現(xiàn)任何有關(guān)這個數(shù)列的信息。因而，將此題命制出來十分妥當(dāng)，沒有什么可以鉆空子的地方。本題進試后，收到了很好的效果。絕大多數(shù)選手都拿到了十分理想的分數(shù)，而選手們采取的方法也是花樣繁復(fù)，爭奇斗艷。來自杭州外國語學(xué)校的同學(xué)，將本文中提到的第三問解法優(yōu)化至O嬨孬孯孧 n嬩。事實上，只要對中途xn的詢問實施時間復(fù)雜度?；纯?/p>

8、。下面，從另一個角度說明這樣做的每一步，同時計算嬲個量：Sn, xn+1。由xn+1可以推出x2n+1和x2n+2，由此又可以推出x4n+1, x4n+2, x4n+3, x4n+4。利用以上四個量， 就可以輕易地由Sn推出S4n嬬S4n+3了。故，求Sn, xn+1，可以化歸為求Sbn/4c, xbn/4c+1。這樣T 嬨n嬩 嬽S4n+1嬬 S4n+2嬬T 嬨n/嬴嬩嬫 O嬨嬱嬩，因此T 嬨n嬩 嬽 O嬨孬孯孧 n嬩。嬵Refereneger SequenTM(OEISTM)孛孅孂嬯孏孌孝嬮孛嬱孝The On-LineEncyclopediaofhttp:/oeis./嬮嬶Appendix

9、完整題面A孭孥 孌孩孭孩孴嬺 嬱孳嬬 孍孥孭孯孲孹 孌孩孭孩孴嬺 嬱嬲嬸孍孂定義數(shù)列x1 嬽 嬱, x2k 嬽 xk, x2k1 嬽 嬨嬱嬩k+1xk嬨k 嬱嬩嬮 存在如下三種類型詢問嬮嬱嬮 求xn嬮嬲嬮 判斷x1 嬫 x2 嬫 嬫 xn的符號嬮嬳嬮 求x1 嬫 x2 嬫 嬫 xn嬮Task:xInput: stdin第一行包含一個整數(shù)q嬬 代表詢問的數(shù)量嬮 接下來q行嬬 每行兩個數(shù)c, n嬬 即詢問的類型，以及n的值。Output: stdout對于每個詢問嬬 輸出一行嬬 即對應(yīng)的負數(shù)嬬 輸出孜嬭嬢嬬 如果是嬰嬬 輸出孜嬰嬢嬮嬮 對于詢問嬲嬬 如果是正數(shù)嬬 輸出孜嬫嬢嬬 如果是Constras有嬱嬰嬥的數(shù)據(jù)嬬 僅含詢問嬱嬮有嬱嬰嬥的數(shù)據(jù)嬬 僅含詢問嬲嬮有嬱嬰嬥的數(shù)據(jù)嬬