URAL 1057 Amount of Degrees

短命女 2022-03-29 08:46 201阅读 0赞

题目链接：[http://acm.timus.ru/problem.aspx?space=1&num=1057][http_acm.timus.ru_problem.aspx_space_1_num_1057]

题意：求区间\[L,R\]内有多少数字将其化成B进制后含有K个1？

思路：首先说二进制，这个比较简单。对于不是二进制的，将其化成B进制后，从高位开始找到第一个大于1的位，将该位以及该位之后的都修改为1.然后将其看做二进制即可。

i64 C[N][N];
    
    void init()
    {
        C[0][0]=1;
        int i,j;
        for(i=1;i<N;i++)
        {
            C[i][0]=C[i][i]=1;
            for(j=1;j<i;j++) C[i][j]=C[i-1][j-1]+C[i-1][j];
        }
    }
    
    int L,R,K,B;
    
    
    int deal(int n)
    {
        int a[N],aNum=0;
        while(n)
        {
            a[aNum++]=n%B;
            n/=B;
        }
        int i;
        for(i=aNum-1;i>=0;i--) if(a[i]>1) break;
        int j;
        for(j=i;j>=0;j--) a[j]=1;
        n=0;
        for(i=aNum-1;i>=0;i--) n=n*2+a[i];
        return n;
    }
    
    int cal(int n,int k)
    {
        if(B!=2) n=deal(n);
        int ans=0,i,cnt=0;
        for(i=31;i>=1;i--)
        {
            if(n&(1<<i))
            {
                cnt++;
                if(cnt>k) break;
                n^=(1<<i);
            }
            if((1<<(i-1))<=n) ans+=C[i-1][k-cnt];
        }
        if(n+cnt==k) ans++;
        return ans;
    }
    
    
    int main()
    {
        init();
        Rush(L)
        {
            RD(R,K,B);
            int ans=cal(R,K)-cal(L-1,K);
            printf("%d\n",ans);
        }
    }

[http_acm.timus.ru_problem.aspx_space_1_num_1057]: http://acm.timus.ru/problem.aspx?space=1&num=1057

发表评论取消回复

表情：

评论列表（有 0 条评论，201人围观）

还没有评论，来说两句吧...

相关阅读

相关【数位DP】[LOJ10163]Amount of Degrees

发现自己以前对数位DP其实一窍不通... 这题可以做一个很简单的转换：一个数如果在$b$进制下是一个01串，且1的个数恰好有k个，那么这个数就是合法的（刚开始没判断必定是01

古城微笑少年丶/ 2023年06月01日 06:10/ 0 赞/ 21 阅读

相关 ural 1057 Amount of degrees 【数位dp】

题意：求（x--y）区间转化为 c 进制 1 的个数为 k 的数的出现次数。分析：发现其满足区间减法，所以可以求直接求0---x 的转化为 c 进制中

超、凢脫俗/ 2022年08月13日 12:56/ 0 赞/ 71 阅读

相关 LeetCode697. Degree of an Array解答

一早上起来，先做一道题降降起床气，这道题花了一个小时多十分钟，但是！当我看到accept之后的结果了的时候！ ![这里写图片描述][SouthEast] 贼开心 \

本是古典何须时尚/ 2022年06月07日 09:08/ 0 赞/ 158 阅读

相关 URAL 1057 (数位dp)

问题描述: Create a code to determine the amount of integers, lying in the set \[ X; Y\] and

比眉伴天荒/ 2022年06月04日 05:16/ 0 赞/ 196 阅读

相关 697. Degree of an Array

> Given a non-empty array of non-negative integers nums, the degree of this array is def

Love The Way You Lie/ 2022年06月03日 03:12/ 0 赞/ 131 阅读

相关 697. Degree of an Array

Given a non-empty array of non-negative integers `nums`, the degree of this array is def

拼搏现实的明天。/ 2022年05月30日 12:21/ 0 赞/ 132 阅读

相关 697. Degree of an Array

原题链接： [https://leetcode.com/problems/degree-of-an-array/description/][https_leetcode.com

╰+攻爆jí腚メ/ 2022年05月29日 02:11/ 0 赞/ 130 阅读

相关 URAL 1057 Amount of Degrees

题目链接：[http://acm.timus.ru/problem.aspx?space=1&num=1057][http_acm.timus.ru_problem.aspx_

短命女/ 2022年03月29日 08:46/ 0 赞/ 202 阅读

相关 fake_useragent.errors.FakeUserAgentError: Maximum amount of retries reached

2019.5.17 已更新全部，linux&windows 在新电脑（windows）上安装了fake-useragent，但是不能正常工作，出现如题的报错 fake\_u

Dear 丶/ 2022年01月30日 01:57/ 0 赞/ 801 阅读

相关 MAXDOP(max degree of parallelism)

概述当 SQL Server 在具有多个微处理器或 CPU 的计算机上运行时，它将为每个并行计划执行检测最佳并行度（即运行一个语句所使用的处理器数）。您可以使用 max

朴灿烈づ我的快乐病毒、/ 2021年12月20日 23:47/ 0 赞/ 176 阅读