首页 > 其他分享 >URAL - 1057 Amount of Degrees--数位dp

URAL - 1057 Amount of Degrees--数位dp

时间:2022-12-06 19:34:27浏览次数:67  
标签:cnt 1057 -- ik int Amount ans include dp


原题链接:​​http://vjudge.net/problem/URAL-1057​


题意:[ x , y ]里一共有多少个数可以由k个b整数幂组成。




#define _CRT_SECURE_NO_DEPRECATE

#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
#include<stack>
#include<algorithm>
#include<cmath>
#include<string>
#include<stdio.h>
#define INF 99999999
#define eps 0.0001
using namespace std;

int dp[35][35];//dp[i][j]表示深度为i有j个1的种类,根深度为0
int x, y, k, b;
int cnt[35];

void init()
{
for (int i = 0; i <= 31; i++)
{
dp[i][0] = 1;
for (int j = 1; j <= i; j++)
dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];

}
}

int solve(int n)
{
int len = 0;
int ans = 0;
int ik = k;
int ib = b;
while (n)
{
cnt[len++] = n%ib;
n /= ib;
}

for (int i = len - 1; i >= 0; i--)
{
if (cnt[i] == 1)
{
ans += dp[i][ik];//以0开头,找到k个1;然后k--,固定开头为1,继续做
ik--;
}
else if (cnt[i] > 1)
{
ans += dp[i + 1][ik];
break;
}
if (ik < 0)//注意是小于0
return ans;
}

if (ik == 0)//n本身满足
ans++;
return ans;
}

int main()
{
init();
while (~scanf("%d%d%d%d", &x, &y, &k, &b))
{
printf("%d\n", solve(y) - solve(x - 1));
}
return 0;
}




标签:cnt,1057,--,ik,int,Amount,ans,include,dp
From: https://blog.51cto.com/u_11937443/5916560

相关文章

  • hdu3715 Go Deeper--二分 & 2-sat
    原题链接:​​http://acm.hdu.edu.cn/showproblem.php?pid=3715​​题意:有一个递归代码:go(intdep,intn,intm)begin   outputthevalueofdep.   ifdep......
  • 1610.maximum-number-of-visible-points 可见点的最大数目
    问题描述1610.可见点的最大数目解题思路利用atan2函数,即可将斜率转化为\(-\pi\sim\pi\)的角度;扩充数组,令angle[n+i]=angle[i]+360,使角度数组长度为2*n,这样......
  • 一文解读等保
    一、什么是等保?“等保”,即信息安全等级保护,是我国网络安全领域的基本国策、基本制度。早在2017年8月,公安部评估中心就根据网信办和信安标委的意见将等级保护在编的5个基本......
  • hdu3078 Network--RMQ & LCA
    原题链接:​​http://acm.hdu.edu.cn/showproblem.php?pid=3078​​题意:给定n个点标号1到n,每个点一个权值,接下来n-1行u,v表示u和v两点连线,接下来k行查询,op,u,v,如果u为0,表示把点u......
  • hdu4115 Eliminate the Conflict--2-sat
    原题链接:​​http://acm.hdu.edu.cn/showproblem.php?pid=4115​​题意:x,y两个人玩剪刀石头布,玩n局,1代表剪刀,2代表石头,3代表布。先给出y的n局每次所出的,再给出m行对x的出法的......
  • hdu1814 Peaceful Commission--dfs
    原题链接:​​http://acm.hdu.edu.cn/showproblem.php?pid=1814​​题意:n个党派参加会议,每个党派有2名代表,且每个党派必须只能派一个人去,但是有m对人是有仇的,他们不能同时参......
  • 1805.number-of-different-integers-in-a-string 字符串中不同整数的数目
    问题描述1805.字符串中不同整数的数目解题思路把数字当作字符串处理,存入unordered_set(哈希表)中,注意最后一个字符是数字的情况。代码classSolution{public:i......
  • hdu1824 Let's go home--2-sat
    原题链接:​​http://acm.hdu.edu.cn/showproblem.php?pid=1824​​题意:n个队伍,每一个队(三人一队),或者队长留下或者其余两名队员同时留下;接下来m对编号,每一对队员,如果队员A留......
  • 使用docker安装RocketMQ
    1.创建namesrv服务拉取镜像dockerpullrocketmqinc/rocketmq创建namesrv数据存储路径mkdir-p/docker/rocketmq/data/namesrv/logs/docker/rocketmq/data/namesrv/st......
  • hdu2586 How far away ?--tarjan & LCA
    原题链接:​​http://acm.hdu.edu.cn/showproblem.php?pid=2586​​题意:n个点,编号1-n,接下来n-1行,每行三个数字表示两点之间的距离,题目是保证两点间不会出现两条可行的路,也就......