資源描述：
《solution day2題解》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在行業(yè)資料-天天文庫。
1、全國信息學奧林匹克聯(lián)賽（NOIP2011）提高組復賽模擬Day2廣東中山紀念中學全國青少年奧林匹克聯(lián)賽(NOIP2011)復賽模擬提高組Day2（請選手務必仔細閱讀本頁內(nèi)容）一、題目概覽中文題目名稱高一學堂高二學堂高三樓英文題目名稱atPokerIdentity可執(zhí)行文件名at.exePoker.exeIdentity.exe輸入文件名at.inPoker.inIdentity.in輸出文件名at.outPoker.outIdentity.out每個測試點時限1秒1秒1秒測試點數(shù)目101010每個測試點分值101010比較方式全文比較全
2、文比較全文比較題目類型傳統(tǒng)傳統(tǒng)傳統(tǒng)二、提交源程序文件名對于Pascal語言at.paspoker.pasidentity.pas對于C語言at.cpoker.cidentity.c對于C++語言at.cpppoker.cppidentity.cpp三、編譯命令（不包含任何優(yōu)化開關）對于Pascal語言fpcat.pasfpcpoker.pasfpcidentity.pas對于C語言gccat.c–oat.exegccpoker.c–opoker.exegccidentity.c–oidentity.exe對于C++語言g++at.cpp
3、–oat.exeg++poker.cpp–opoker.exeg++identity.cpp–oidentity.exe四、運行內(nèi)存限制運行內(nèi)存上限256M256M256M注意事項：1.文件名（程序名和輸入輸出文件名）必須使用小寫。2.C/C++中函數(shù)main()的返回值類型必須是int，程序正常結束時的返回值必須是0。3.全國統(tǒng)一評測時采用的機器配置為：CPUP41.9GHz，內(nèi)存1G，上述時限以此配置為準。各省在自測時可根據(jù)具體配置調(diào)整時限。全國信息學奧林匹克聯(lián)賽（NOIP2011）提高組復賽模擬Day2廣東中山紀念中學1.高一學堂
4、(at.pas/c/cpp)【原題解】lca，從葉子開始做，每次減~或dfs序+樹狀數(shù)組?！颈┝λ惴ā靠紤]到部分數(shù)據(jù)k比較小，我們可以用f[i][j]表示i為根的子樹中與i距離為j的結點的個數(shù)，可以樹形DP求解。期望得分：60。【筆者補充】題目實際上是求每個結點深度差不超過K的兒子個數(shù)。由于涉及到方面有：深度、子樹求和，大概思路可以想到是先預處理，然后按深度從大到小增刪點，再查詢某子樹有多少個點。增刪點的過程可以通過給點設權值來實現(xiàn)，1表示這個點存在，0表示不存在。那么查詢某子樹有多少個點就相當于是對某個子樹中點的權值進行求和。與子樹相
5、關可用dfs序，修改和求和可以用樹狀數(shù)組實現(xiàn)。全國信息學奧林匹克聯(lián)賽（NOIP2011）提高組復賽模擬Day2廣東中山紀念中學2.高二學堂(Poker.pas/c/cpp)【題目簡述】ΣAi*Xi=n
6、Ai∈[1,4]&Xi>Xi-1&ΣXi=k&Ai,Xi,n,k∈N求解{Xi}的個數(shù)mod1,000,000,009?！舅惴?】輸出n，不解釋。。。期望得分：10?！舅惴?】利用上式對Ai和Xi進行搜索，同樣不解釋。。。期望得分：20?！舅惴?】把牌按數(shù)值大小編號，數(shù)值相同的編上4個不同號碼。用f[i][j][k]表示現(xiàn)在處理完前i張牌
7、，一共用了j張，構成和為k的方案數(shù)。轉(zhuǎn)移只要使用類似背包的方法即可。方程為：f’[i][j][k]=f[i][j][k]+Σf[i-1][j-1][k-w(i)]。其中w(i)為i的牌面。為免MLE，可把第一維省去。期望得分：40?！舅惴?】這是Symbol提出來的方法。如果現(xiàn)在所有的牌面都大于1，假設有k’張，那么把所有牌面都減小1，總和減少k’之后，問題顯然是等價的；而如果有牌面等于1，那么只要把這幾張牌去掉，剩下的牌面就又都是大于1的了。所以可以使用f[i][j]表示用j張牌構成和為i的方案數(shù)，轉(zhuǎn)移的時候分情況：1）所有牌面大于1
8、，則f[i][j]+=f[i-j][j]；2）有牌面等于1，那么我們可以枚舉這些牌的數(shù)量t（≤4），則f[i][j]+=f[i-j][j-t]。最后答案就是f[n][1~k]的最小值。時間復雜度為O(nk)。期望得分：60。【算法5】對算法4進行優(yōu)化，考慮到k比較小，而轉(zhuǎn)移只需要用到前k層的值。我們可以把連續(xù)k層的f壓在一個矩陣內(nèi)，并按一維編號，最多不超過k^2個。然后我們每次轉(zhuǎn)移1層的f，也就是如果現(xiàn)在矩陣記錄的是f[1~k][]的值，那么轉(zhuǎn)移一次，矩陣記錄的就變成了f[2~k+1][]的值。然后填矩陣就是了。時間復雜度為O(logn
9、*k^6)，多組數(shù)據(jù)下，這個方法會由于常數(shù)大被卡掉。期望得分：80。全國信息學奧林匹克聯(lián)賽（NOIP2011）提高組復賽模擬Day2廣東中山紀念中學【算法6】首先，假設牌面的集合為{xi}，集合中的每個元素
