歷年題目訓練solution

1、solutionyycgame1、對于 20%的數(shù)據(jù)，, = 10。可以枚舉取牌的所有可能。時間復雜度為( )。+2、對于 60%的數(shù)據(jù)，, = 2000。因為先手和后手取牌情況類似，所以只先手?？梢栽O為取牌時考慮這一輪的情況：了張黑色牌，張白色牌時的獲勝概率。取到黑色牌，直接獲勝；取到白色牌，對手取到黑色牌，對手獲勝；取到白色牌，對手也取到白色牌，pupil 取到白色牌，進入到下一輪；取到白色牌，對手也取到白色牌，pupil 取到黑色牌，進入到下一輪?？梢酝瞥觯?21 =+ 3 + 1 2 +則是要求的+1+2+1+2。時間復雜度和空間復雜度都為( )。3、對于 100%的數(shù)據(jù)，, = 10

2、000?？梢园l(fā)現(xiàn) 60 分算法中，真正對有貢獻的狀態(tài)只有1 個，于是只算這些狀態(tài)3就可以了。還有個更加方便的，可以設表示進行了輪，nyx 和 Diaoyeye 全都取的白色牌，pupil 已經(jīng)取走了張黑色牌的概率。這個轉(zhuǎn)移方程也很好推，而且先手和后手獲勝概率可以一起算。1數(shù)組開滾動就行了。時間復雜度為( )。3str1、對于 30%的數(shù)據(jù)， = 40。直接枚舉兩個子串，然后用 hash 判重。時間復雜度為(4)。如果你不會算第二問，就只能得 10 分了。2、另有 20%的數(shù)據(jù)，串由 1 個 a 和 1個 b。我沒有寫這個部分分，大概可以枚舉一下 a 的個數(shù)和幾個塊中 b 的個數(shù)，然后算一算。2

3、、對于 100%的數(shù)據(jù)， = 2000。得到的串由 + ，考慮僅當串的長度最長時計算它。容易證明，被計算的方案滿足 + ()不為的子串，其中()表示串的第一個字母。定義()為串中以字母開頭的不同非空子串的個數(shù)，()為串中加上字母以后不為的子串的不同非空子串的個數(shù)。又因為, 均可為空，所以最終為 () () + 1)。u對于求()和()，可以將的所有子串下就行了。第二問純屬搞笑的。到一個中去重，然后直接判斷一這些串中字典序最大的顯然是由的字典序最大的子串的前綴加上這個子串，可以發(fā)現(xiàn)，這個前綴全由同一個字母組成，所以這一部分也可以通過計算。時間復雜度為(2 26)。3、數(shù)據(jù)范圍可以開到105級別，

4、用后綴自處理字符串就可以了。test1、對于 20%的數(shù)據(jù)， = 50。 直接按題目里給出的式子算。時間復雜度為(4)。2、對于 40%的數(shù)據(jù)， = 0 = =1 =1 =1 =1即滿足 + = ( + )的, , , 的個數(shù)不小于。那么可以算出所有 + 的值，求出每個值的出現(xiàn)次數(shù)，然后再乘一乘就可以了。時間復雜度為(2 log2 )。3、另有 30%的數(shù)據(jù)，全相等。要求一個最大的，滿足 + + + =1 =1 =1 =1= = 4 可以注意到， = = 4 + 不會超過 1000，所以把每個值的個數(shù)算出來再求個后綴和就行了。4 + + + 的出現(xiàn)次數(shù)同樣可以分兩邊算。時間復雜度為(2)。4、對于 100%的數(shù)據(jù)，1 = = 100000，1 = = 4。對于任意1 = = ，保證0 = =