首页 > 代码库 > [ACM] ural 1057 Amount of degrees (数位统计)
[ACM] ural 1057 Amount of degrees (数位统计)
1057. Amount of Degrees
Time limit: 1.0 second
Memory limit: 64 MB
Memory limit: 64 MB
Create a code to determine the amount of integers, lying in the set [X;Y] and being a sum of exactlyK different integer degrees of B.
Example. Let X=15, Y=20, K=2, B=2. By this example 3 numbers are the sum of exactly two integer degrees of number 2:
17 = 24+20,
18 = 24+21,
20 = 24+22.
18 = 24+21,
20 = 24+22.
Input
The first line of input contains integers X and Y, separated with a space (1 ≤ X ≤ Y ≤ 231?1). The next two lines contain integers K and B (1 ≤ K ≤ 20; 2 ≤ B ≤ 10).
Output
Output should contain a single integer — the amount of integers, lying between X and Y, being a sum of exactly K different integer degrees of B.
Sample
input | output |
---|---|
15 20 2 2 | 3 |
Problem Source: Rybinsk State Avia Academy
数位统计的第一题。看的刘聪的论文:浅谈数位类统计问题http://wenku.baidu.com/view/d2414ffe04a1b0717fd5dda8.html
做完这道题,觉得数位统计真的很奇妙,不需要一个数一个数的去枚举判断,在判断一个数的时候,把比它小的数全都判断了出来,效率高。其中也有组合的运用,当高位确定后,后面几位就随便取就可以。
题目中当B不是二进制时:
为什么这样做呢? 一个数可以化成题意中给的形式,其B进制数中系数中应该不是0,就是1,如果从左到右找到系数>1,那么这个数肯定是不符合题意的,应该使其化为1,这就使得原数小了一些,为了不漏掉一些数,应使修改的这一位后面的所有位都变为1,这样是最大的且不超过n的B进制中只包含0和1的数。这样化完以后按照二进制做就可以了。
代码:
#include <iostream> #include <string.h> using namespace std; int X,Y,K,B; int c[40][40]; void init()//组合数 { c[0][0]=1; for(int i=1;i<=31;i++) { c[i][0]=c[i-1][0]; for(int j=1;j<=i;++j) c[i][j]=c[i-1][j]+c[i-1][j-1]; } } int change(int n) { int b[40]; int len=0; while(n) { b[len++]=n%B; n/=B; } int ans=0; for(int i=len-1;i>=0;i--) { if(b[i]>1) { for(int j=i;j>=0;j--) ans+=(1<<j); break; } else ans+=(b[i]<<i); } return ans; } int cal(int x,int k) { int tot=0,ans=0; for(int i=31;i>0;i--) { if(x&(1<<i))//第i位为1(从0开始的),那么后面还剩下i个数字,后面的第一个数字为0,从i-1个数字中任意挑k-tot个 { ++tot; if(tot>k) break; x=x^(1<<i);//1变为0 } if((1<<(i-1))<=x) ans+=c[i-1][k-tot]; } if(tot+x==k)//考虑x这个数本身 ++ans; return ans; } int main() { init(); while(cin>>X>>Y>>K>>B) cout<<cal(change(Y),K)-cal(change(X-1),K)<<endl; return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。