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 题解

相关内容

热门资讯

安卓系统可以打印吗,开启移动打... 你有没有想过,你的安卓手机或者平板,除了打电话、刷微博、玩游戏,还能干点啥?没错,今天我要给你揭秘一...
安卓怎么调用系统拨号,Andr... 你是不是也和我一样,对安卓手机的系统功能充满了好奇?比如说,你知道怎么让你的安卓手机像打电话一样,直...
什么叫安卓双系统,一机多能的智... 你有没有想过,为什么你的手机可以同时运行两个操作系统呢?这就是我们今天要聊一聊的安卓双系统。想象一边...
安卓系统有哪些表情,轻松表达你... 你知道吗?安卓系统里的表情包那可真是五花八门,让人眼花缭乱。今天,就让我带你一起探索一下安卓系统里那...
安卓系统怎么下载树洞,安卓系统... 你有没有想过,在安卓手机上下载一个可以让你畅所欲言、分享心情的树洞应用呢?树洞,顾名思义,就是一个可...
山寨安卓导航升级系统,功能升级... 你有没有发现,手机导航越来越智能了?但是你知道吗,市面上那些看似高大上的安卓导航升级系统,其实有不少...
诺基亚原生安卓系统怎,创新与体... 你有没有想过,那个曾经风靡一时的诺基亚手机,竟然也玩起了原生安卓系统?没错,就是那个经典的“诺基亚”...
如果安卓系统换成ios,系统更... 想象如果安卓系统突然宣布:“咱们来个大的改变,把安卓换成iOS!”这得是多大的新闻啊!想象你的手机、...
安卓开发新手引导系统,掌握核心... 你刚踏入安卓开发的广阔天地,是不是有点晕头转向呢?别担心,今天我就要给你来一场新手引导大作战,让你从...
国外安卓操作系统,全球视角下的... 你知道吗?在手机的世界里,操作系统可是个大头戏呢!今天,咱们就来聊聊国外那些风头正劲的安卓操作系统,...
安卓17系统窗口调用,Andr... 你知道吗?最近安卓系统又出新花样了!安卓17系统窗口调用,这可是个大招啊!今天,我就要带你深入了解一...
苹果庄安卓通讯系统,通讯系统融... 你知道吗?在手机江湖里,有两个门派可是鼎鼎大名,一个是以苹果为首的iOS,另一个则是安卓阵营。今天,...
安卓系统10寸屏幕,功能与体验... 你有没有想过,拥有一台10寸屏幕的安卓系统设备,会是怎样的体验呢?想象小巧的机身,却拥有强大的功能,...
安卓刷入linux系统,轻松刷... 你有没有想过,你的安卓手机其实可以变身成一个强大的Linux工作站呢?没错,就是那个在服务器上大显神...
安卓系统 看电视软件,便捷观影... 亲爱的手机控们,你是不是也和我一样,对安卓系统上的看电视软件情有独钟?没错,那种随时随地都能追剧的快...
安卓13系统图片备份,随时随地... 亲爱的安卓用户们,你是否在期待着安卓13系统的到来呢?听说这个新系统将会带来许多令人兴奋的新功能,但...
安卓手机系统壁纸大全,海量精美... 你有没有发现,手机屏幕上那一抹色彩,有时候能瞬间提升你的心情呢?没错,说的就是那些精美的壁纸!今天,...
白板 安卓系统内置电脑,融合移... 亲爱的读者,你是否曾想过,在你的安卓手机上,竟然可以变身为一台迷你电脑?没错,这就是今天我要跟你分享...
安卓系统游戏昵称英文,Unlo... 你有没有想过,在安卓系统的游戏世界里,一个独特的昵称能给你带来怎样的不同体验呢?想象当你化身成为一名...
原生安卓6.0系统占用,原生安... 你有没有发现,自从你的手机升级到了原生安卓6.0系统,它的反应速度好像变得不那么敏捷了?别急,今天就...