Compete

I can't fall down before I die
  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  11 Posts :: 3 Stories :: 2 Comments :: 0 Trackbacks

常用链接

留言簿(2)

我参与的团队

随笔档案

文章档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜
POJ 3252 (Round Numbers)
#include<iostream>
using namespace std;
__int64 c[32][32];
__int64 solve(int x);
int main()
{
    int i,j,m,n;
    for(i=0;i<=31;i++)
    {
        c[i][0]=1;
        c[i][i]=1;
    }
    c[0][0]=0;
    for(i=2;i<=31;i++)
        for(j=1;j<i;j++)
            c[i][j]+=c[i-1][j]+c[i-1][j-1];
    cin>>m>>n;
    cout<<solve(n)-solve(m-1)<<endl;
    return 0;
}
__int64 solve(int x)
{
    __int64 note[32]={0};
    bool flag;
    if(x<=1) return 0;
    if(x==2) return 1;
    int i,j,cnt=0,len;
    __int64 sum=0,d,dd;
    i=30;
    while(((1<<i)&x)==0&&i>=0) i--;
    len=i;
    __int64 pre0=0,pre1=0;
    for(i=len;i>=0;i--)
    {
        if((1<<i)&x)  note[i]=++cnt;
    }
    for(i=0;i<len;i++)
    {
        if((1<<i)&x)
        {
            flag=false;
            pre1=note[i]-1;
            pre0=len-i-note[i]+2;
            d=pre1-pre0;
            dd=d;
            for(j=i;j>=0;j--)
            {
                if(pre1+(i-j)>pre0+j)
                    break;
                sum+=c[i][j];
            }
            if((i==0)&&d<1) sum++;
        }
    }
    for(i=len-1;i>=1;i--)
    {
        if(i==1) 
        {
            sum++;
            break;
        }
        for(j=i;j>i/2;j--)
            sum+=c[i][j];
    }
    if(++len>=2*cnt) sum++;
    return sum;
}
posted on 2010-04-21 09:55 丁立洋 阅读(511) 评论(0)  编辑 收藏 引用

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