fzu2113 Jason的特殊爱好(数位DP)

                                           Problem 2113 Jason的特殊爱好

Accept: 314    Submit: 1012
Time Limit: 1000 mSec    Memory Limit : 32768 KB

 Problem Description

Jason很喜欢数字，特别是1这个数字，因为他觉得1有特殊的含义。为了让更多的人喜欢上1，他决定出一题关于1的水题（每个人都喜欢水题）。

 Input

输入数据中有多组数据，每组数据输入为两个正数，a,b(1<=a,b<=10^18)。

 Output

输出a到b之间的整数包含多少个1。

 Sample Input

1 1000

 Sample Output

301

1.思路

假如统计的是5014,对于每一位数，我们假设其左边的数位l，右边的数位r；

        (1).首先枚举的是个位数：l = 501, r = 0, 当个位数是1时，左边我们可以假设位0-501到的任何一个数字，因此个位数为1时有(l+1) * 1 + r = 502种情况，属于当前位的值大于1的情况；

       (2).然后是第二位：l = 50, r = 4, 因为5014的第二位为1，所以当左边取0-49时，右边可以取0-9，而当右边取50时，左边只能是0-4，因此第二位是1时有l * 10 + (r + 1) = 505,属于当前位的值等于1的情况；

   (3).然后是第三位：l = 5, r = 14,因为5014的第三位为0 < 1,所以当第三位取1时，左边只能取0-4, 右边取0-99，有500种情况，属于当前位的值小于1的情况；

        (4).第四位：l = 0, r = 14, 当第四位取1时，有(l + 1) * 1000 = 1000种；

所以0到5014总共有2507个1；

2.代码

#include <iostream>
using namespace std;
typedef long long ll;int digit[20];
ll p[20];void init() {p[0] = 1;for(int i = 1; i < 19; ++ i) {p[i] = p[i-1] * 10;}
}ll f(ll n) {int pos = 0;ll res = 0, m = n;while(n) {digit[++pos] = n % 10;n /= 10;}for(int i = 1; i <= pos; ++ i) {ll r = m % p[i-1];              // 第i位右边的数ll l = m / p[i];		// 第i位左边的数if(digit[i] > 1) {		// 当前位的值大与1的情况res += (l + 1) * p[i-1];}else if(digit[i] == 1) {        // 当前位的值等于1的情况res += l * p[i-1] + r + 1;}else {				// 当前位的值小于1的情况res += l * p[i-1]; }}return res;
}int main() {ll a, b;init();while(cin >> a >> b) {cout << f(b) - f(a-1) << "\n";}return 0;
}