HDU 4722 数位dp
2024-08-26 17:50:07
Good Numbers
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4753 Accepted Submission(s): 1511
Problem Description
If we sum up every digit of a number and the result can be exactly divided by 10, we say this number is a good number.
You are required to count the number of good numbers in the range from A to B, inclusive.
You are required to count the number of good numbers in the range from A to B, inclusive.
Input
The first line has a number T (T <= 10000) , indicating the number of test cases.
Each test case comes with a single line with two numbers A and B (0 <= A <= B <= 1018).
Each test case comes with a single line with two numbers A and B (0 <= A <= B <= 1018).
Output
For test case X, output "Case #X: " first, then output the number of good numbers in a single line.
Sample Input
2
1 10
1 20
Sample Output
Case #1: 0
Case #2: 1
Hint
The answer maybe very large, we recommend you to use long long instead of int.
Source
题意:对一个数字 每一位求和%10==0 问一个区间内有多少个这类数字
题解:模板题
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <stack>
#include <queue>
#include <cmath>
#include <map>
#define ll __int64
#define dazhi 2147483647
#define bug() printf("!!!!!!!")
#define M 200005
using namespace std;
int t;
ll l,r;
ll bit[];
ll dp[][];
ll functi(int pos ,int flag,int m)
{
if(pos==) return (m==);
if(flag&&dp[pos][m]!=-) return dp[pos][m];
ll x=flag?:bit[pos];
ll ans=;
for(ll i=;i<=x;i++)
ans+=functi(pos-,flag||i<x,(m+i)%);
if(flag) dp[pos][m]=ans;
return ans;
}
ll fun(ll num)
{
int len=;
memset(bit,,sizeof(bit));
while(num)
{
bit[++len]=num%;
num/=;
}
return functi(len,,);
}
int main()
{
while(scanf("%d",&t)!=EOF)
{
memset(dp,-,sizeof(dp));
for(int i=;i<=t;i++)
{
scanf("%I64d %I64d",&l,&r);
printf("Case #%d: %I64d\n",i,fun(r)-fun(l-));
}
}
return ;
}
最新文章
- RecyclerView添加Header的正确方式
- Codeforces Round #234A
- linux哲学思想
- VC++ CStatic控件背景透明且改变其文本时,文字重叠解决方法
- ASP.NET Core实现OAuth2.0的ResourceOwnerPassword和ClientCredentials模式
- Game Programming Pattern
- C#与数据库访问技术总结(五)之Command对象的常用方法
- Configure SSL for SharePoint 2013
- 【Reorder List】cpp
- linux信号量超过系统限制
- 初识Devexpress ChartControl 之 动态添加stepline及TextAnnotation
- mysql 分析5语句的优化--索引添加删除
- 安装gitlab8.0在reconfigure报错
- Ubuntu 下生成 python 环境安装文件 requirements.txt
- centos7部署asp.net core 应用程序
- 使用Python多渠道打包apk
- mybatis的xml映射文件
- direct加载之ora-39782一例
- hihoCoder week23 最短路径&#183;一
- PMI网站中pdu查询