目录

一，数位DP

二，OJ实战

CSU 1642: Problem B

ACdream - 1156 LCP SUM

BZOJ 2757: Blinker的仰慕者

剑指 Offer 43. 1～n 整数中 1 出现的次数

一，数位DP

有一类奇特的DP问题，对象空间是一个整数集，而解空间是把每一位作为一维，在这样的高维空间内完成DP，这类问题叫数位DP

二，OJ实战

CSU 1642: Problem B

题目：

Description

已知两个正整数a和b，求在a与b之间（包含a和b）的所有整数的十进制表示中1出现的次数。

Input

多组数据(不超过100000组)，每组数据2个整数a，b.(1≤a,b≤1000000).

Output

每组数据的答案占一行。

Sample Input

1 10
10 100
2 1

Sample Output

      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。

HINT

【数据范围】 

对于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