P6218 [USACO06NOV] Round Numbers S 题解

题面

题目传送门

如果一个正整数的二进制表示中，00 的数目不小于 11 的数目，那么它就被称为「圆数」。

例如，99 的二进制表示为 10011001，其中有 22 个 00 与 22 个 11。因此，99 是一个「圆数」。

请你计算，区间 [l,r][l,r] 中有多少个「圆数」。

前置芝士

1.数位dp
相关的题：P4317 花神的数论题

思路

l,r的数据范围为2e9，显然不能用暴力枚举

数位 DP：用来解决一类特定问题，这种问题比较好辨认，一般具有这几个特征：
1.要求统计满足一定条件的数的数量（即，最终目的为计数）；
2.这些条件经过转化后可以使用「数位」的思想去理解和判断；
3.输入会提供一个数字区间（有时也只提供上界）来作为统计的限制；
4.上界很大（比如 10^{18}），暴力枚举验证会超时。

看到上面从oiwiki里抄的描述，发现完美符合本题，于是我们考虑使用数位dp来解决这道题

本题解使用的是记忆化搜索的方式（其实是不会递推写法喵）

状态设计

看到洛谷题解区的大佬好像很多都是用一维表示0和1的个数的差，也有没有在dp数组中存储前导0的大佬，那样貌似空间小一些。但是我太菜了，一开始都没想到，于是用了两维分别表示0和1的个数。

这个表示：枚举到第cnt位，0的总数为sum0，1的总数为sum1，前面的每一位数是不是都是前导0，的数有多少个。（当qd=1时表示前面数都是前导0，qd=0时则表示前面数不是都是前导0）

前导0

关于为什么要看前面的每一位数是不是都是前导0：
因为如果不判断前导0的话，类似于 $ 00100 $ 这样的数的前面的0本来是不应该统计的，但不判断前导零时则会被统计进sum0中去。所以一定要看前导零。

tips:

1.因为这个题的数据范围只有2e9，所以不用开long long。
2.在2进制中2e9有30位（貌似），主包一开始开小了（只有我会这样吧）
3.主包写代码写一半忘记是2进制了，怒调两分半。
4.记得初始化

代码：

#include<bits/stdc++.h>
using namespace std;
int l,r;
const int MAXN=35;
int a[MAXN];//十进制的数拆分成2进制每一位是什么 
int dp[MAXN][MAXN][MAXN][2];//枚举到第i位，有j个0，k个1,前面是不是都是前导0的数的个数 
int dfs(int cnt,int flag,int sum0,int sum1,int qd){
//cnt：枚举到了cnt位，flag：这一位有没有限制，其他的看上文：P 
	if(qd){//如果前面全都是前导0，那么这些0都不能算进0的总个数中 
		sum0=0;
	}
//下面的就是数位dp经典模板了（划掉 
	if(!cnt){
		if(sum0>=sum1){
			return 1;
		}
		return 0;
	}
	if(!flag && ~dp[cnt][sum0][sum1][qd]){
		return dp[cnt][sum0][sum1][qd];
	}
	int maxi=a[cnt];
	if(!flag){
		maxi=1;
	}
	int ret=0;
	for(int i=0;i<=maxi;i++){
		ret+=dfs(cnt-1,flag&&(i==maxi),sum0+(i==0),sum1+(i==1),qd&&(i==0));
	}
	if(!flag){
		return dp[cnt][sum0][sum1][qd]=ret;
	}
	return ret;
} 
int query(int x){
	int cnt=0;
	while(x){
		cnt++;
		a[cnt]=x&1;
		x>>=1;
	}
	return dfs(cnt,1,0,0,1);//从最后一位开始，有限制，0和1的个数都是0，有前导零 
}
int main(){
	cin>>l>>r;
	memset(dp,-1,sizeof(dp));
	cout<<query(r)-query(l-1);	
}

结语

煮包的通过记录

呃呃，真的写不动题了啊啊，只能来水题解了。（吐血

我的洛谷（魂兮归来......