dp之数位dp---(度的数量)
创始人
2024-05-30 08:23:18
0

题目:

在这里插入图片描述

思路:
首先对题目意思进行分析:恰好等于 K 个互不相等的 B 的整数次幂之和,这句话的意思是说对于某一个B进制数x说,x只有k位上只有1,其他位为0。然后让你求区间[X,Y]的满足条件的数字有多少,这里我们可以用区间[1,Y]-[1,X-1]来更加容易的得到答案。

那么我们怎么获得前n个数的满足条件的数呢,首先将B进制数x中的 每一位用a表示为anan-1an-2an-3…a0,然后从第一位an开始,把它分为两部分0-an-1和an,所有的决策都可以由第一部分和第二部分的和组成(图片画横线的部分)。

当我们选第一部分0-an-1的时候,那么第an-1位以及以后的数字我们可以任意选取,(不会超过x),但是因为题目要求只能选0或者1那么先取0的话就是n个数(因为最后一个数的下标为a0)中选出k-last(当前已经选了多少个1)个1的结果,如果取1的话那么就是n个数中选出k-last个1的结果,这部分结果可以用组合数来求得(根据组合数公式C(a,b)=C(a-1,b)+C(a-1,b-1)来获得),但是取1有个前提条件,那么就是an必须大于1(因为如果an等于1的话,那么他是会分到第二部分的)。

这样第一部分就选完了,那么对于第二部分an的时候,如果an不为1,那么根据题意不能选择除了0或者1之外的任意数字,那么直接break退出即可;否则如果为1,那么last就要++(接下来需要的1少一个),然后继续往下走每次计算左边的决策,然后走到最后一位的时候a0如果选0,那么就可以根据判断条件[last=k]是否成立,如果成立结果res++即可;如果选1,那么也会last++,然后因为走到了最后一位,后面没有可以再进行的决策,那么还是根据[last=k]是否成立来使res++。
在这里插入图片描述
大体思路就是这样子的,具体细节可以看看代码:

/**
*  ┏┓   ┏┓+ +
* ┏┛┻━━━┛┻┓ + +
* ┃       ┃
* ┃   ━   ┃ ++ + + +
*  ████━████+
*  ◥██◤ ◥██◤ +
* ┃   ┻   ┃
* ┃       ┃ + +
* ┗━┓   ┏━┛
*   ┃   ┃ + + + +Code is far away from  
*   ┃   ┃ + bug with the animal protecting
*   ┃    ┗━━━┓ 神兽保佑,代码无bug 
*   ┃  	    ┣┓
*    ┃        ┏┛
*     ┗┓┓┏━┳┓┏┛ + + + +
*    ┃┫┫ ┃┫┫
*    ┗┻┛ ┗┻┛+ + + +
*/#include
#include 
#include 
#include 
#include 
#include 
#include
#include
#include
#define sc_int(x) scanf("%d", &x)
#define sc_ll(x) scanf("%lld", &x)
#define pr_ll(x) printf("%lld", x)
#define pr_ll_n(x) printf("%lld\n", x)
#define pr_int_n(x) printf("%d\n", x)
#define ll long long 
using namespace std;const int N=1000000+100;
int x,y,k,b;
int s[40][40];//因为如果是二进制位可能会有30位多开了点void cal()//用于计算组合数 
{for(int i =0;i<=40;i++)for(int j =0;j<=i;j++)if(j==0)s[i][j]=1;//i个数中不选也有一种方案else s[i][j]=s[i-1][j]+s[i-1][j-1];
}int dp(int n)
{if(n==0)return 0;//特判,0的时候没有任何一种方案vectorcnt;//用来存储进制转换后的数while(n)cnt.push_back(n%b),n/=b;int res=0;//结果int last=0;//到当前情况已经选了多少个1for(int i =cnt.size()-1;i>=0;i--)//从最高位开始运算{int x=cnt[i];if(x)//如果x大于等于1{res+=s[i][k-last];//i个数中选k-last个1if(x>1){if(k-last-1>=0) res+=s[i][k-last-1];//选1的情况就少了一个1可以选择,//到此左半部分计算完毕break;//因为x大于1的时候右半部分不能得到1,直接退出即可}else{//x为1 的情况last++;//已经选了的1增加if(last>k)break;//如果已经选了1的数量大于k那么也可以直接退出}}if(i==0&&k==last)res++;//走到了a0的情况判断一下是否可以构成一种方案} return res;
}int main()
{cal();cin>>x>>y>>k>>b;cout<

看y总的大概思路就是把这些数按树形结构分成两部分考虑,每一部分的答案根据上一部分获得,反正自己也不是很会,只能尽量写了那么清楚了qwq

上一篇:MyBatis开发详解

下一篇:FJWC2019 Day2 题解

相关内容

热门资讯

适合htpc的安卓系统,精选适... 你有没有想过,家里的电视盒子或者电脑,要是能装上安卓系统,那得多方便啊!想象你可以在上面玩各种游戏,...
安卓如何检测系统广播,Andr... 你有没有想过,你的安卓手机里那些神奇的“广播”是怎么工作的呢?没错,就是那些悄无声息地在你手机后台运...
安卓系统怎么刷recovery... 你有没有想过,你的安卓手机突然间变得有点儿不听话了?别急,别急,我来告诉你怎么刷recovery,让...
不用安卓和苹果系统,多元化移动... 你有没有想过,在这个科技飞速发展的时代,我们竟然可以不用安卓和苹果系统,也能畅游网络世界呢?没错,今...
安卓系统忘记网络设置,安卓系统... 亲爱的安卓用户们,你是否曾经遇到过这样的烦恼:手机连接网络时,突然忘记了网络设置,各种网络连接问题层...
安卓系统无法自己升级,自主升级... 你是不是也遇到了这个问题?安卓系统怎么就突然不升级了呢?别急,今天就来给你好好捋一捋这个让人头疼的小...
华为变成原生安卓系统,原生安卓... 你知道吗?最近科技圈可是炸开了锅,华为的大动作让所有人都瞪大了眼睛。没错,就是那个我们熟悉的华为,竟...
安卓系统手机很便宜,高性价比的... 你有没有发现,最近逛手机市场,安卓系统手机的价格真是让人惊喜不已呢!没错,就是那种我们平时用的最多的...
原生的安卓系统 索尼,深度解析... 你知道吗?在智能手机的世界里,有一个品牌总是以其独特的魅力和精湛的工艺吸引着众多科技爱好者。那就是索...
安卓系统更新历史,从初代到最新... 你有没有发现,你的安卓手机每次更新后都变得焕然一新?没错,这就是安卓系统更新带来的魔力!今天,就让我...
安卓系统的第二套系统,创新与变... 你知道吗?在科技飞速发展的今天,安卓系统已经成为了智能手机市场上的霸主。但是,你知道吗?安卓系统其实...
全军出击安卓系统版本,战力再攀... 你有没有发现,最近全军出击这款游戏在安卓系统上的版本更新可是越来越频繁了呢?这不,我就来给你好好扒一...
安卓系统热点限速软件,优化热点... 你有没有遇到过这种情况:手机连接热点后,网速就像蜗牛爬行一样慢,简直让人抓狂!别急,今天就来给你揭秘...
安卓系统占内存多,揭秘内存消耗... 你有没有发现,手机用着用着,内存就不够用了?尤其是安卓系统,好像特别能吃内存,让人头疼不已。今天,就...
最近安卓系统奔溃,揭秘原因与应... 最近手机界可是炸开了锅呢!安卓系统竟然出现了大规模奔溃,这可真是让人摸不着头脑。咱们一起来探究这背后...
ce系统能刷安卓系统吗,揭秘能... 你有没有想过,你的安卓手机是不是也能用上CE系统呢?这可不是天方夜谭,今天就来给你揭秘一下这个神秘的...
安卓系统UI设计特色,创新与用... 你有没有发现,每次打开安卓手机,那界面设计得真是让人眼前一亮呢?今天,就让我带你一起探索一下安卓系统...
ipod有安卓系统吗,跨界融合... 你有没有想过,那个曾经风靡一时的iPod,它到底有没有安卓系统呢?这个问题,估计让不少音乐爱好者都好...
安卓多少系统最高的,揭秘最高版... 你有没有想过,你的安卓手机到底升级到了哪个系统版本呢?是不是好奇安卓系统里哪个版本才是最高级的呢?别...
现在安卓最高的系统,揭秘安卓1... 你有没有发现,手机更新换代的速度简直就像坐上了火箭呢!这不,最近安卓系统又来了一次大升级,听说这是现...