程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ3252 Round Numbers 組合數學||數位DP

POJ3252 Round Numbers 組合數學||數位DP

編輯:C++入門知識

POJ3252 Round Numbers 組合數學||數位DP


 

題型是數位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<

 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved