codeforces round 160（完全）

又跪了。。。繼續做吧，堅持！！

codeforces 261B   

先用背包處理出一個dp數組，然後枚舉每一個分隔數（即前面的數再加上這個數就超過p了） 統計出所有的數量，然後直接算，，

http://www.codeforces.com/contest/261/submission/2921844

codeforces 261C

首先可以計算出m+1行有幾個1 （畫一畫就能得出規律）：即給定一個m，第m+1行的1的個數為2^(bit_count(m+1) - 1 ) 個 ，是以t肯定是2的指數次幂，否則答案為0

現在問題轉換成求2到n+1中有幾個數的二進制表示中有P+1個1，（2^P = t），典型的數位DP搞一下把。

dp[i][j]表示長度為i有j個1的二進制數的個數，預處理好之後直接統計即可

http://www.codeforces.com/contest/261/submission/2922990

codeforces 261D

我感覺題意好難懂啊。。。。

給你k行數，每行有n個數，然後将這n個數重寫t遍相連，問你新組成的序列（總共有n*t個數）的最長遞增子序列的長度為多少。

有幾個要注意的地方  題目保證所有數都不超過maxb ， maxb*n不超過10的7次

CF的伺服器比較犀利，好像幾個憶的計算量都能飄過，也就是暴力，求出序列後用一個nlogn的求最長遞增子序列的算法也可以過

複雜度應該是k * 10^7 * log(maxb) . 

下面貼一種樹狀數組的做法，相當于用樹狀數組來優化一個n*maxb的dp

http://www.codeforces.com/contest/261/submission/2951761

上述做法雖然考慮了數列的性質，但還有更好的方法。

膜拜了lzqxh的代碼後。。。。thinking。。。。

考慮到數列的性質，長度很長（10^7）, 但因為最多隻有maxb(10^5)個數，是以我們可以考慮這樣的狀态 , dp[i]表示以i結尾的最長遞增子序列的長度，那麼如果目前數為a

目前最長的遞增子序列的長度為len，那麼我們應該找前面比a小的數b，然後判斷一下dp[b]+1能否更新dp[a]，什麼樣的長度能更新dp[a]呢，肯定是dp[a]+1喽，是以應該找長度為dp[a]的且小于a的數接上a，而且如果dp[a]==len+1了，就不用再更新了，因為加入一個a最多能使最長遞增序列的長度增加1，既然已經增加1了，就不需要再更新了。

最後有一個很巧妙的做法是用一個數組映射一下dp值為x的最後一個數，即 num[dp[x]] = x; 找長度為dp[a]的數的時候隻需要用這個數組直接找就好了。稍微想一下就知道為什麼了，tmp = num[dp[a]] 記錄的肯定是目前長度為dp[a]的數字（結尾）中最小的數了，因為如果前面還有長度為dp[a]的，且數字小于tmp的那麼tmp可以接上去進而tmp處的長度就應該更長才對，而不是dp[a] 。每個dp[i]最多增加cnt次cnt是數字的種類數，是以複雜度是cnt*cnt的，由于cnt<=n,且cnt<=maxb,是以cnt*cnt <= n*maxb <=10^7

http://www.codeforces.com/contest/261/submission/2953464

codeforces  261E

題意：初始的時候給你兩個數，1 0    一次操作可以給右邊的數+1，也可以将左邊的數乘上右邊的數再放回左邊，問你有多少的數x（l<=x<=r）可以出現左邊的位置上，要求操作的次數小于等于p。

注意到p <= 100，可以發現x肯定都是由小于等于100的素數組成的。然後就是題目的突破口了，處理出所有的素因子在100以内的數，1e9以内這樣的數大概有300 0000個（尼瑪這種範圍讓我怎麼想！！），設dp[i]代表第i個數最少經過幾次操作可以得到，那麼接下去的事情就是枚舉右邊操作了幾次，直接兩重循環暴力去更新dp就好了，dp[j]肯定是由a[k] * i  == a[j],這樣 的k更新過來，這裡k不用去枚舉，将所有的數排序之後利用單調性不斷地往右移動就好了。

http://www.codeforces.com/contest/261/submission/2958347

總結：這場比賽DP比較多，思維很靈活，一般都是很簡單的DP前面覆寫一層不容易看透的描述（我比較水。。） ， 也就是在一般的Dp上加點東西，非常考驗思維，，