题目描述
如果一个正整数的二进制表示中,00的数目不小于11的数目,那么它就被称为「圆数」。
例如,99的二进制表示为10011001,其中有22个00与22个11。因此,99是一个「圆数」。
请你计算,区间[l,r][l,r]中有多少个「圆数」。
输入格式
一行,两个整数ll和rr。
输出格式
一行,一个整数,表示区间[l,r][l,r]中「圆数」的个数。
样例
输入:2 122 12 输出: 66
思路
显然这道题又是一道数位DP。但是这个题的难点和特殊之处就在于它是在二进制下处理的。这就需要我们重新揣度此题的状态。
设f[i][j][k]f[i][j][k]表示一个有ii位,且其中包括jj个11,且从右往左数第ii个数是kk的圆数的个数。这个如何转移呢?
显然的是,若j<ij<i, f[i][j][0]=f[i−1][j][0]+f[i−1][j][1]f[i][j][0]=f[i−1][j][0]+f[i−1][j][1],若j!=0j!=0, 则f[i][j][1]=f[i−1][j−1][0]+f[i−1][j−1][1]f[i][j][1]=f[i−1][j−1][0]+f[i−1][j−1][1] (这个感性理解一下?)
最后就分成两种情况处理:
1.将位数小于cnt位的圆数累加到答案中
2.和其他数位DP类似,考虑用添数的方法解决问题。若当前遍历到该位为11,那么就存在该位为00的情况,这时候再枚举11的位数,考虑还是否能构成圆数,若能构成,累加答案即可。
最后前缀和统计答案即可。
int f = 1, x = 0;char ch; do{ch = getchar();if(ch=='-')f = -1;} while (ch < '0' || ch > '9'); do{ x = x * 10 + ch - '0';ch = getchar();} while (ch >= '0' && ch <= '9'); f[1][0][0] = 1, f[1][1][1] = 1;//初始化 for (int i = 2; i <= 32;++i){ for (int j = 0; j <= i;++j){ if(j<i) f[i][j][0] = f[i - 1][j][0] + f[i - 1][j][1];//若既有0又有1或只有0 if(j) f[i][j][1] = f[i - 1][j - 1][0] + f[i - 1][j - 1][1];//若有1或全部是1 for (int i = 1; i < cnt;++i){ for (int j = 0; j <= (i >> 1); ++j) }//统计小于cnt位的圆数,(i>>1)这个就是保证了所得的数一定为圆数 int s0 = 0, s1 = 1;//s1一定要赋值为1,因为无论如何我们讨论的数都是大于1的(为0的情况在开头就舍掉了) for (int i = cnt - 1; i >= 1;--i){ if(bn[i]) for (int j = 0; j <= i;++j){ if(s0+i-j>=s1+j) res += f[i][j][0];//已确定的0的个数+枚举的0的个数>=已确定的1的个数+枚举的1的个数 printf("%lld\n", calc(r + 1) - calc(l));
|