[数据结构与算法]1585 例题1 Amount of Degrees(Ural 1057 LOJ10163) 进制转换纯枚举从40分到60分 数位DP100分 初次使用string

总目录

在线测评地址(ybt)

在线测评地址(LOJ)

看完题目，感觉就是一个进制转换。

样例数据如下：

17对应2进制10001 数1的个数有2个
18对应2进制10010 数1的个数有2个
20对应2进制10100 数1的个数有2个

该题有个极端的测试数据：

1 2^31-1
20
2

即
1 2147483647
20
2

很明显，AC的解法，一定是成片的计算数量。

目前能怎么办？从初级的算法入手，慢慢改进，看能到什么程度。

1.进制转换,纯枚举,输出符合的数量.

样例通过，提交40分

ybt

未通过

LOJ

?40分代码如下：

#include <bits/stdc++.h>
using namespace std;
int x,y,k,b;
void init(){
	scanf("%d%d%d%d",&x,&y,&k,&b);
}
int count1(int a){
	int cnt=0;
	while(a){
		cnt+=((a%b)==1);//统计1的数量 
		a/=b;
		if(cnt>k){//优化，避免无谓的计算 
			cnt=-1;
			break;
		}
	}
	return cnt;
}
void solve(){
	int i,ans=0;
	for(i=x;i<=y;i++){
		ans+=(count1(i)==k);
	}
	printf("%d\n",ans);
}
int main(){
	init();
	solve();
	return 0;
}

超时可以理解，有测试点错误，不可接受，想不通。

突然想到一组测试数据：

输入:
1 9
1 3

输出:
3

有效的是
1=1*3^0
3=1*3^1
9=1*3^2

然而上述代码对应的输出是5

很显然5=2*3^0+1*3^1等无效数据也被统计了。

ybt

未通过

LOJ

?60分代码如下：

#include <bits/stdc++.h>
using namespace std;
int x,y,k,b;
void init(){
	scanf("%d%d%d%d",&x,&y,&k,&b);
}
int count1(int a){
	int cnt=0;
	while(a){
		if(a%b==1)cnt+=1;//统计1的数量
		else if(a%b){//系数不是1 
			cnt=-1;
			break;
		} 
		a/=b;
		if(cnt>k){//优化，避免无谓的计算 
			cnt=-1;
			break;
		}
	}
	return cnt;
}
void solve(){
	int i,ans=0;
	for(i=x;i<=y;i++){
		ans+=(count1(i)==k);
	}
	printf("%d\n",ans);
}
int main(){
	init();
	solve();
	return 0;
}

2.数位DP??????

由于所求的幂互不相等，符合条件的数写成B进制一定只由0和1组成。

因此我们只考虑B=2的情况。

此处区间满足区间减法，即count(X,Y)=count(0,Y)-count(0,X-1)

因此我们唯一需要求的就是，给定n，求出所有不超过n的正整数中，其二进制表示恰好含有K个"1"的有多少。

这里，我使用一棵完全二叉树来代表一个区间内的数。

例如图中高度为4的完全二叉树就可以代表所有长度为4的二进制数。

(左枝是0，右枝是1，有点像哈夫曼编码。)

其范围为[0,2^4-1]

每个叶子就代表了一个数。

假设K=3 ，n=13，其二进制为1101。

很容易递推求出这个问题：

设f[h,s]表示在高度为h(h>=1,因根节点0是人为引入)的完全二叉树包含的数中（范围是[0,2^h-1]），二进制中恰含s个1的数有多少。(注意s<=h,因具体到某个数，是从根节点走到叶节点经历的01)

f[h,s]? =? f[h-1,s] (左子树中的个数)?+? f[h-1,s-1](右子树中的个数)

(注：f[h,s]根是0

f[h-1,s]左子树的根是0，故除左子树根节点0外，还需s个1.

f[h-1,s-1]右子树的根是1，故除右子树根节点1外，还需s-1个1.)

剩下的问题就是，如何将任意进制问题转化为二进制问题。

(若左起有大于1的数位，下面转换对右边界Y没有问题，转换只是将不大于Y的符合题意的数找出，因Y本身不符合题意，故右边界没有少计数，也没有多计数。)

(若左起有大于1的数位，下面转换对左边界X没有问题，转换只是将不大于X的符合题意的数找出，因X本身不符合题意，故左边界没有少计数，也没有多计数。)

(思维难点)只需贪心将n的B进制表示转化为只含01：找到n的左起(左是高位)第一位大于1的数位，将它以及它右边所有数位赋为1(即找到最接近n的符合题意的数)。

递推求f的时间复杂度为O(log^2(n))，每次询问的时间复杂度为O(log(n))，因此总时间复杂度为O(log^2(n))。

问题得到完美解决！

实际上，我们也可以只用“位”的思想来考虑这个问题，而不使用树的思想。

我们每次找到n的"1"数位，将它赋为0，则其右面的数位可任取0、1。

可根据组合数算出满足题意的数的个数。

穷举所有“1”数位，计算组合数，即可完成询问。

事实上，f的递推公式正是组合数公式！

与树的思想异曲同工!

?使用高度为h的完全B叉树表示所有长度为h的B进制数，思考起来更加直观，在处理较复杂问题时优点明显。

当然，最终程序我们并不真正建树，它的作用只是帮助我们思考。

无论从树结构考虑还是从数位的角度考虑，基本思想都是：

?逐位确定

ybt

通过

LOJ

#include <bits/stdc++.h>
using namespace std;
int x,y,k,b;
int f[35][35];
void init(){
	scanf("%d%d%d%d",&x,&y,&k,&b);
}
int i2b(int x){//将整数x转换成B进制 
	string s;
	int i,j;
	while(x){//将整数x转换成字符串,逆序存储 
		s=s+char(x%b+'0');//注意 2<=B<=10,故s%b的值落在[1,9]区间 
		x/=b;
	}
	for(i=0;i<s.size();i++){
		if(s[i]>'1')//若i位大于1,将0-i位之间数据设置为1 
			for(j=0;j<=i;j++)
				s[j]='1';
	}
	x=0;
	for(i=0;i<s.size();i++)//以01形式重写x 
		x|=((s[i]-'0')<<i);
	return x;
}
void fx(){//处理手法,类杨辉三角 
	int i,j;
	//全是0,全是1,均只有一种情形,初始化,需注意
	for(i=0;i<=31;i++)//边界初始化 
		f[i][0]=f[i][i]=1; 
	for(i=1;i<=31;i++)
		for(j=1;j<i;j++)
			f[i][j]=f[i-1][j]+f[i-1][j-1];
}
int count(int x){
	int i,j,tot=0,ans=0;
	for(i=31;i>0;i--){//自高位向低位扫描 
		if(x&(1<<i)){
			tot++;
			if(tot>k)break;
			x^=(1<<i);//将第i位从1置为0 
		}
		if((1<<(i-1))<=x)//寻找合适的左子树 
			ans+=f[i-1][k-tot];
	}
	if(tot+x==k)ans++;//判断自身是否相同
	return ans; 
}
int main(){
	init();
	x=i2b(x-1);
	y=i2b(y);
	fx();
	printf("%d\n",count(y)-count(x));
	return 0;
}

该题习得什么？

第一次对数位DP有了印象，心心念的二进制位操作出现了。

在统计ans过程中，细节较多，该题若作为试题，100分的代码初次编写时很难完成的。