网站建设开发哪家质量好,如何设立官方网站,网站tkd怎么做,郑州建设招标办网站文章目录描述解析代码thanks for reading#xff01;传送门描述
如果把一个数的某一位当成支点#xff0c;且左边的数字到这个点的力矩和等于右边的数字到这个点的力矩和#xff0c;那么这个数就可以被叫成杠杆数。
比如4139就是杠杆数#xff0c;把3当成支点#xff0c…
文章目录描述解析代码thanks for reading传送门描述
如果把一个数的某一位当成支点且左边的数字到这个点的力矩和等于右边的数字到这个点的力矩和那么这个数就可以被叫成杠杆数。
比如4139就是杠杆数把3当成支点我们有这样的等式4 * 2 1 * 1 9 * 1。
给定区间[x,y]求出在[x,y]中有几个杠杆数。
解析
数位dp 具体实现看代码注释吧
代码
#includecstdio
#includecmath
#includecstring
#includealgorithm
using namespace std;
#define ll long long
int n;
#define int long long
ll dp[20][20][5000];
ll num[20],cnt;
/*
dp定义
dp[pos][pl][num1]
位数为pos杠杆支点位置在pl力矩和为num1的数字的个数
*/
ll find(int pos,int pl,int num1,bool lim,bool flag){
//flag判断前导〇
//lim判断是否受最高位限制if(num10) return 0;//如果杠杆力矩已经是负的了以后只会更负所以回去if(pos0) return num10;//填完如果力矩还需要0就符合条件if(!limdp[pos][pl][num1]!-1) return dp[pos][pl][num1];//记忆化int mx lim ? num[pos] : 9;//可以填的最高位数ll ans0;for(int i0;imx;i){ansfind(pos-1,pl,num1(pos-pl)*i,limimx,flagi0);//枚举当前需要填的位数}if(!lim) dp[pos][pl][num1]ans;//记忆化return ans;
}
ll solve(int x){cnt0;while(x){num[cnt]x%10;x/10;//把每一位存起来}ll ans0;for(int i1;icnt;i) ansfind(cnt,i,0,1,1);//枚举杠杆支点位置return ans-cnt1;
}
signed main(){ll l,r;memset(dp,-1,sizeof(dp));scanf(%lld%lld,l,r);if(l0) printf(%lld\n,solve(r));else printf(%lld\n,solve(r)-solve(l-1));//用前缀和相减
}
/*
if(flag) ansfind(pos-1,pl,(pos-pl)*i,limimx,flagi0);else ansfind(pos-1,pl,num1(pos-pl)*i,limimx,flagi0);
*/thanks for reading
