poj 2282 The Counting Problem 3252 round numbers

两个都是麻烦的计数问题,只不过一个是二进制,另一个似乎更贴近十进制的现实世界.不过计算机里,还是二进制感觉能跑得更快一些,移位总比乘十来得更快一些.
计数从0-n的每一位的数字个数,先计数位数小于n的位数的数字个数,再从高位到低位依次循环累加计数和n位数相同且小于n的数的各位数字.考虑的情形很多,有一点考虑不到就很难得到正确答案.

/*Source Code

Problem: 2282  User: y09shendazhi 
Memory: 220K  Time: 16MS 
Language: C++  Result: Accepted 

Source Code 
*/

#include 
<iostream>
using namespace std;

int ans[15];//answer
int pow(int a,int b)
{
    
int an=1;
    
for(int i=0;i<b;i++)
        an
*=a;
    
return an;
}

void solve(int n)
{
    
int i,j,k;
    memset(ans,
0,sizeof(ans));
    
if(n<10)
    
{
        
for(i=1;i<=n;i++)
            ans[i]
=1;
        
return ;
    }

    
    
int digit[20]={0};
    
int dec=0;//decimal of n
    int temp=0;
    temp
=n;
    
while(temp)
    
{
        digit[dec
++]=temp%10;
        temp
/=10;
    }

    temp
=pow(10,dec-1);

    
for(i=1;i<10;i++)//位数小于n的
        ans[i]+=(dec-1)*temp/10;
    ans[
0]+=(dec-1)*temp/10-(temp-1)/9;
    
    
for(i=1;i<digit[dec-1];i++)//最高位是  1~最高位
    {
        ans[i]
+=temp;
        
for(k=0;k<10;k++)
            ans[k]
+=(dec-1)*temp/10;
    }

    temp
/=10;
    
for(i=dec-2;i>=0;i--)
    
{
        
for(j=0;j<digit[i];j++)
        
{
            
for(k=dec-1;k>i;k--)
                ans[digit[k]]
+=temp;
            ans[j]
+=temp;
            
for(k=0;k<10;k++)
                ans[k]
+=i*temp/10;
        }

        temp
/=10;
    }

    
for(i=0;i<dec;i++)
        ans[digit[i]]
++;
}

int main(int argc, char *argv[])
{
    
int n,m;
    
int ans1[15]={0};
    
int temp=0;
    
while(cin>>n>>m)
    
{
        
if(n==0 && m==0)
            
break;
        
if(n>m)
        
{
            temp
=n;
            n
=m;
            m
=temp;
        }

        solve(n
-1);
        memcpy(ans1,ans,
sizeof(ans));
        solve(m);
        
for(int i=0;i<9;i++)
            cout
<<ans[i]-ans1[i]<<' ';
        cout
<<ans[9]-ans1[9]<<endl;
    }

    
    
return 0;
}


/*Source Code

Problem: 3252  User: y09shendazhi 
Memory: 136K  Time: 0MS 
Language: C++  Result: Accepted 

Source Code 
*/

#include 
<iostream>
using namespace std;

// /n\
// | |
// \m/
__int64 com(__int64 n ,__int64 m)
{
    
if(n<m)
        
return 0;
    __int64 result
=1;
    m
=m<n-m?m:n-m;
    
for(__int64 i=1;i<=m;i++)
        result
=(result*(n-m+i))/i;    
    
return result;
}


__int64 sumCom(__int64 n,__int64 m)
{
    
if(n==0 && m>=0)
        
return 1;
    
if(m>n)
        m
=n;
    
if(m<0)
        
return 0;
    __int64 ans
=0;
    
for(__int64 i=0;i<=m;i++)
    
{
        ans
+=com(n,i);
    }

    
return ans;
}


__int64 solve(__int64 n)
{
    
if(n==0 || n==1)
        
return 0;

    __int64 ans
=0;
    __int64 dec
=0;//二进制位数
    __int64 temp=n;
    
while(temp)
    
{
        dec
++;
        temp
>>=1;
    }

    temp
=1;
    temp
<<=dec-1;

    __int64 one
=0;
    
for(__int64 j=1;j<dec;j++)
            ans
+=sumCom(j-1,j/2-1);
    temp
>>=1;
    one
++;
    
for(__int64 i=dec-1;i>0;i--)
    
{
        
if(temp&n)
        
{
            ans
+=sumCom(i-1,dec/2-one);
            one
++;
        }

        temp
>>=1;
    }

    
if(one<=dec/2)
        ans
++;
    
return ans;
}

int main()
{
    __int64 S,F;
scanf(
"%I64d%I64d",&S,&F);
    
{
        
if(S==0)
            printf(
"%I64d\n",solve(F));
        
else
            printf(
"%I64d\n",solve(F)-solve(S-1));

    }

    
return 0;
}


posted on 2010-08-20 17:22 若余 阅读(399) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

<2009年8月>
2627282930311
2345678
9101112131415
16171819202122
23242526272829
303112345

统计

常用链接

留言簿

随笔档案(16)

搜索

最新随笔

最新评论

评论排行榜