已-中第二試解題報告

提高組Day2（請選手務必仔細閱讀本頁內(nèi)容名名1.511值言C言言fpcfpcfpcCgccat.c–o gccidentity.c–og++at.cppog++poker.cpp–og++identity.cppC/C++main()int0評測時采用的機器配置為：CPUP41.9GHz，內(nèi)存1G，上述時限以此配置為高一學【原題解lca，從葉子開始做，每次減~dfs序+【算法考慮到部分數(shù)據(jù)k比較小，可以用f[i][j]表示i為根的中與i距離為j的結(jié)DP求解。期望得分：60【筆者補充K由于涉及到方面有：深度、求和，大概思路可以想到是先預處理，然后按深度從大到小增刪點，再查詢某有多少個點。增刪點的過程可以通過給點設(shè)權(quán)值來實現(xiàn)，1表示這個點存在，0表示不存在。那么查詢某有多少個點就相當于是對某個中點的權(quán)值進行求和。與相關(guān)可用dfs序，修改和求和可以用樹狀數(shù)組實現(xiàn)【題目簡述

高二學ΣAi*Xi=n|Ai∈[1,4]&Xi>Xi-1&ΣXi=k&Ai,Xi,n,k∈N求解{Xi}的個數(shù)mod1,000,000,009?！舅?【算2【算3把牌按數(shù)值大小，數(shù)值相同的編上4個不同號碼w(i)i【4Symbol如果現(xiàn)在所有的牌面都大于1，假設(shè)有k’張，那么把所有牌面都減小1k1，那么只要把1f[i][j]ji分情況：1）1f[i][j]+=f[i-j][j]；2）1，那么可以枚舉這些牌的數(shù)量t（≤4，則f[i][j]+=f[i-j][j-t]。O(nk)。期望得分：60【算5對算法4進行優(yōu)化，考慮到k比較小，而轉(zhuǎn)移只需要用到前k層的值?？梢园堰B續(xù)k層的f壓在一個矩陣內(nèi)，并按一維，最多不超過個。然后每次轉(zhuǎn)移1層的f，也就是如果現(xiàn)在矩陣記錄的是f[1~k][]的值，那么轉(zhuǎn)移一次，矩陣記錄的就變成了f[2~k+1][時間復雜度為O(logn*k^6)，多組數(shù)據(jù)下，這個方由于常數(shù)大被卡掉期望得分：80。【算6ai（≤4表示這個牌面用了多少張。那么問題就轉(zhuǎn)化成了求Σai*xi=n的正整數(shù)解個數(shù)，其中x1<x2<…<xm，Σai≤k。由于ai和k都比較小，可以枚舉所有情況，再去解方程。而現(xiàn)在約束還是比較多的，得想辦法除去約束。yi=xi-x(i-1)，Σbi*yi=nbi≤k。至此，成功把未知數(shù)單調(diào)這個棘手的約束解決了。接下來，發(fā)現(xiàn)bi比較?。ā?0，那么可以把bi的lcm算出來，最2520bi*yipi*lcm+qiqibilcm*Σpi+Σqi=n考慮到Σqi還是比較小的（≤3W，可以枚舉Σqi的每個可能值，那么pi的方案數(shù)就可以用經(jīng)典的隔板法來計算。而對于Σqi的計算，可以用期望得分：100【算1

高三可能大家一開始想寫，就是2^（n*n）枚舉每一個點是否放上硬幣，但是不幸的是，判重是一個艱難的工作。n<=5的時候，可能很多人會果n=5的時候，就得到分，所以，我只能把分卡到10%?！舅?yyn*n的矩陣，22k個點形成AA1+A2+..