題型是數位DP中很常見的,給一個區間[l,r]求區間[l,r]中的 符合題目要求的數的個數,本題求的 是 區間中 的數 它的二進制中0的個數大於等於1的個數的 這些數的個數,不好意思表達能力有點差。。。例如[1,4]答案是2, 因為 2的二進制是10,0的個數大於等於1的個數,4的二進制是100,0的個數大於1的個數,所以答案是兩個
好了第一反應肯定是 設定一個函數 f(r) - f[l - 1]就是答案,那麼顯然這個函數f(r)的意思就是 1 到 r之間符合要求的數的個數,很容易想到數位DP,但是真心不好推啊,由於推數位DP的過程中對每個數的二進制 都畫了一下,後來發現了 組合數學其實也是可以做的,
首先每一個數化為二進制數 第一位肯定是1,那麼剩下的位數中 讓一定的位數 上的數字為0就可以達到目的,例如 1 {}{}{} 其中{}表示空位,剩下的三個空位中至少讓兩個為0即可,那麼答案其實就是 C(3,2) + C(3,3),跟組合數聯系上了,那麼就好辦了
首先 把一個數m處理成二進制數,假設長度為n,那麼 所有 長度為[1,n-1]的數 中 合法的 個數很容易就求出來了,直接掃一遍 然後判斷它的長度再求組合數即可
接下來的部分就是分析 長度等於n的 且 大小必須小於等於m的 數中 合法的個數,有點麻煩,就是掃他的二進制數,若掃到的當前位上的數字為1,那麼就令這個位置上的數為0,這樣當前二進制表示的數 肯定是小於m的,這樣就對於還未掃到的位 上的數 進行組合數求解答案即可,具體見代碼中的注釋部分
郁悶的是,我做的時候腦子有點糊塗,做到一半曲解了題目的意思,求的是 [l,r]中 數的二進制中1的個數大於0的個數的 這些數的個數,還好答案直接由總數減一下就可以了。。。不然就慘了。。。
int s,e; int bin[33]; const int MAXN = 33; int C[33+1][33+1]; int cnt = 0; void Initial() { int i,j; for(i=0; i<=33; ++i) { C[0][i] = 0; C[i][0] = 1; } for(i=1; i<=33; ++i) { for(j=1; j<=33; ++j) C[i][j] = (C[i-1][j] + C[i-1][j-1]); } } void init() { } bool input() { while(cin>>s>>e) { return false; } return true; } void Binary(int n) { memset(bin,0,sizeof(bin)); cnt = 0; while(n) { bin[cnt++] = n&1; n >>= 1; } } int slove(int n) { if(n == 0)return 0; int ret = 0; Binary(n); for(int i=cnt - 1;i>0;i--) {//統計所有二進制數長度小於n的,可以自由組合數 int tmp = (i - 1); if(tmp&1)tmp = (tmp>>1) + 1; else tmp >>= 1; for(int j=tmp;j<=i - 1;j++) { ret += C[i - 1][j]; //cout<0;i--) {//統計長度與n相同的且小於等於n的 if(bin[i - 1]) { int tmp; if(cnt&1)tmp = (cnt + 1)>>1; else tmp = (cnt>>1) + 1;//長度為cnt的至少需要多少個1 tmp = tmp - mark1;//減去前面已經掃到的1的個數,當前至少還需幾個1 if(tmp < 0)tmp = 0;//有可能前面已經超過了需要的1的個數,這裡需要注意,置0,WA出翔 for(int j= tmp;j<=i - 1;j++) ret += C[i - 1][j]; mark1++;//這個必須放最後,因為當前為0,不是必須為1,調試了半年 } else mark2++; } ret += mark1>mark2?1:0;//寫到最後發現我無意曲解了題意, ret = n - ret;//我求的是一個數的二進制中1大於0的個數,那麼好辦求反就可以了 return ret; } void cal() { cout<