转载请注明出处,谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents
by---cxlove
题目:给出一个区间,问这个区间内的数,转换成B进制后,刚好有B个1的的数有多少个。
http://acm.timus.ru/problem.aspx?space=1&num=1057
关于数位统计类问题可以看论文 《浅谈数位类统计问题》
其中的一个思想是转换成树型结构,通过组合数求出i位中有j个1的数目。
然后从高位开始枚举。又有点像数位DP
二进制很好理解,对于B进制的话。如果当前位大于1,那么后面的可以随意选都比原来的数小。
枚举时要统计高位出现了多少1。
#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define N 30
#define inf 1<<29
#define MOD 2007
#define LL long long
using namespace std;
int c[32][32]={0};
int slove(int n,int b,int k){
int bit[35]={0},len=0,t=n;
while(t){
bit[len++]=t%b;
t/=b;
}
int sum=0,tot=0;
for(int i=len-1;i>=0;i--){
//当前位大于1,则后面的选出若干位为1,其余为0
if(bit[i]>1){
sum+=c[i+1][k-tot];
break;
}
else if(bit[i]==1){
if(i>=k-tot) sum+=c[i][k-tot];
if(++tot>k) break;
}
//由于是闭区间,不要忘了统计原数本身
if(!i&&tot==k)
sum++;
}
return sum;
}
int main(){
int x,y,k,b;
for(int i=0;i<32;i++){
c[i][0]=c[i][i]=1;
for(int j=1;j<i;j++)
c[i][j]=c[i-1][j]+c[i-1][j-1];
}
while(scanf("%d%d%d%d",&x,&y,&k,&b)!=EOF)
printf("%d\n",slove(y,b,k)-slove(x-1,b,k));
return 0;
}
分享到:
相关推荐
Ural解题思路 Ural解题思路 Ural解题思路 Ural解题思路
Ural
lazycal的集训队报告:初探数位DP 以HDU 2089,HDU 3652, URAL 1057等题目为例,介绍了数位DP的算法
URAL3D
Pascal acm_timus_ural_1148.pas
URAL(Timus Online Judge)部分测试数据 不全
Ural 1238 源代码 涉及算法(动态规划、贪心、DFS)
Pascal acm_timus_ural_1099.pas
包含了ural题库中Vol_I 到Vol_III的所有题目的解题思路
ural 题解 yuhch123。 关于yuhch123: ioi2008 金牌第一名,这是当初它做ural 第一卷时的题解
部分题解 大牛出品 Vol1-3 不是很全,约有200题左右
URAL-PHA
Ural ACM 1000源代码(c++),vc++6.0在XPsp2下编译通过,Timus Online Judge再线测评通过
因为大三了 不弄ACM了 所以这些就删了 删之前希望可以帮到别人
大量线段树题目 zoj 1610 线段覆盖 poj 2777 线段覆盖 poj 2528 需要离散化,建树不同,需要处理不同->...ural 1019 覆盖加统计最长同一个颜色 zoj 2301 和上一题差不多,但是这个染色染的是点,注意染色为空的状况
资源分类:Python库 所属语言:Python 资源全名:ural-0.28.0.tar.gz 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
基于张量类模板的线性代数C ++库,可用于表示等级0的张量,标量向量,1的向量,2的矩阵,3的等级3的张量等。它还包括BLAS和LAPACK子例程的接口。
28. The Theoretical Background of the Ural-Altale Hypothesis The hypothesis of common origin of the Altaic languages,and even the Ural-Altaic languages,dates from the first half of the last century....
chieves t he integration of optical and st ruct ural design sof tware. Mainly based on black box compo2 nent met hod , t he development of optical and st ruct ural design sof tware is completed using ...
乌拉尔