数位DPCSU 1642: Problem B
目录
一，数位DP
有一类奇特的DP问题，对象空间是一个整数集，而解空间是把每一位作为一维，在这样的高维空间内完成DP，这类问题叫数位DP
二，OJ实战
CSU 1642: Problem B
题目：
已知两个正整数a和b，求在a与b之间（包含a和b）的所有整数的十进制表示中1出现的次数。
多组数据(不超过100000组)，每组数据2个整数a，b.(1≤a,b≤1000000).
每组数据的答案占一行。
1 10
10 100
2 1
-
2
-
20
-
1
思路：基本的数位DP
代码：
-
#include <iostream>
-
#include<stdio.h>
-
using namespace std;
-
-
int g(int n)//n有多少个1
-
{
-
int r = 0;
-
while (n)r += (n % 10 == 1), n /= 10;
-
return r;
-
}
-
-
int f(int n)//1到n有多少个1
-
{
-
if (n == 0)return 0;
-
return (n + 9) / 10 + f(n / 10) * 10 - g(n / 10)*(9 - n % 10);
-
}
-
-
int main()
-
{
-
int a, b;
-
while (scanf("%d%d",&a,&b)!=EOF)
-
{
-
if (a > b)a ^= b ^= a ^= b;
-
printf("%d\n", f(b) - f(a - 1));
-
}
-
return 0;
-
}
ACdream - 1156 LCP SUM
题目：
long long ans = 0;
for(int i = 1; i <= n; i ++)
ans += lcp(i - 1,i)
给出n，求ans
lcp(i - 1,i)指的是两个数字的最长公共前缀，比如lcp(2,3) = 0,lcp(10,11) = 1,lcp(12345,12346) = 1234
Input
多组数据，每组数据一个n (1 <= n <= 10^9)
Output
对于每个n，输出一行，求得的ans
Sample Input
-
10
-
11
-
12
-
22
-
100
Sample Output
-
0
-
1
-
2
-
13
-
405
Hint
数据组数<=50000
需要注意的是109-110这种情况，lcp(109,110)=lcp(10,11)
本质上是数位DP
代码：
-
#include<iostream>
-
using namespace std;
-
-
long long lcpsum(int n)
-
{
-
if (n < 10)return 0;
-
long long l = n / 10;
-
return (l - 1)*l / 2 * 9 + l * (n % 10) + lcpsum(l);
-
}
-
-
int main()
-
{
-
int n;
-
while (cin >> n)cout << lcpsum(n) << endl;
-
return 0;
-
}
BZOJ 2757: Blinker的仰慕者
题目：
Description
Blinker 有非常多的仰慕者，他给每个仰慕者一个正整数编号。而且这些编号还隐藏着特殊的意义，即编号的各位数字之积表示这名仰慕者对Blinker的重要度。 现在Blinker想知道编号介于某两个值A,B之间，且重要度为某个定值K的仰慕者编号和。
Input
输入的第一行是一个整数N，表示Blinker想知道的信息个数。
接下来的N行，每行有三个数，A,B,K。表示 Blinker想知道编号介于A和B之间的，
重要度为K的仰慕者的编号和。
Output
输出N行，每行输出介于A和B之间，重要度为 K的仰慕者编号和。结果可能很大，
模上20120427。
Sample Input
3
1 14 4
1 30 4
10 60 5
0<=K<=10^18
Sample Output
18
40
66
【样例解释】
第一组样例中，在 1到14之间各位数字之积等于 4的有 4和 14，故编号和为18。
【数据范围】
对于20%的数据，保证： 2<=A<=B<=1000000000，1<=N<=30
对于50%的数据，保证：2<=A<=B<=1000000000000000000，1<=N<=30
对于100%的数据，保证： 2<=A<=B<=1000000000000000000，1<=N<=5000
代码：
-
#include<iostream>
-
#include<map>
-
#define ll long long
-
using namespace std;
-
-
int p = 20120427;
-
typedef pair<ll, ll> pairll;
-
map<pairll, ll>maps;
-
map<pairll, ll>::iterator it;
-
-
ll num1(ll n, ll k)//n到2n-1中积为k的个数,n为10的幂
-
{
-
if (n == 1)return k == 1;
-
ll sum = 0;
-
for (int i = 1; i <= 9; i++)if (k%i == 0)sum += num1(n / 10, k / i);
-
return sum % p;
-
}
-
-
ll num2(ll b, ll k)//1到b中积为k的个数
-
{
-
if (b <= 0 || k == 0)return 0;
-
if (b < k)return 0;
-
if (b < 10)return 1;
-
it = maps.find(make_pair(b, k));
-
if (it != maps.end())return it->second;
-
ll m = 1;
-
while (m * 10 <= b)m *= 10;
-
ll h = b / m, sum = num2(m - 1, k);
-
for (int i = 1; i < h; i++)if (k%i == 0)sum += num1(m, k / i);
-
if (k%h == 0)sum += num2(b%m, k / h) - num2(m / 10 - 1, k / h);
-
it = maps.begin();
-
pairll temp = make_pair(b, k);
-
maps.insert(it, make_pair(temp, sum%p));
-
return sum % p;
-
}
-
-
ll ans(ll b, ll k)//1到b中积为k的所有数的和
-
{
-
if (b <= 0 || k == 0)return 0;
-
if (b < 10)return (k < 10)*k;
-
ll m = 1;
-
while (m * 10 <= b)m *= 10;
-
ll h = b / m, sum = 0;
-
sum = ans(m - 1, k);
-
for (int i = 1; i < h; i++)if (k%i == 0)sum += num1(m, k / i)*i*m%p + ans(m - 1, k / i) - ans(m / 10 - 1, k / i);
-
if (k%h == 0)sum += (num2(b%m, k / h) - num2(m / 10 - 1, k / h))*h*m%p + ans(b%m, k / h) - ans(m / 10 - 1, k / h);
-
return sum % p;
-
}
-
-
int main()
-
{
-
int n;
-
ll a, b, k;
-
cin >> n;
-
while (n--)
-
{
-
cin >> a >> b >> k;
-
cout << (ans(b, k) + p - ans(a - 1, k)) % p << endl;
-
}
-
return 0;
-
}
数据太大了会超时
剑指 Offer 43. 1～n 整数中 1 出现的次数
输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。
例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。
示例 1：
输入：n = 12
输出：5
示例 2：
输入：n = 13
输出：6
限制：
1 <= n < 2^31
思路：
把最后一位的1的个数计算出来，然后问题规约为子问题。
-
class Solution {
-
public:
-
int countDigitOne(int n) {
-
if(n<10)return (n>=1)?1:0;
-
int ans=countDigitOne(n/10-1)*10+(n-1)/10+1;
-
int ans2=0,m=n/10;
-
while(m){
-
if(m%10==1)ans2++;
-
m/=10;
-
}
-
return ans+ans2*(n+1-n/10*10);
-
}
-
};
文章来源: blog.csdn.net，作者：csuzhucong，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/nameofcsdn/article/details/113071516
- 点赞
- 收藏
- 关注作者
评论（0）