Running-Turtle

My blogs

0%

Atcoder387-C

发表于 分类于

题目链接 ：C - Snake Numbers

Snake Numbers，蛇数，是指最高位大于其余所有位的数，给定 $10\leq L,R\leq 10^{18}$ ，求 $[L,R]$ 有多少蛇数 ？

1、设 $f(x)$ 表示 $10 \sim x$ 有多少蛇数，答案就是 $f(R)-f(L-1)$ 。

2、假设 $x$ 的位数为 $n$ ，分三种情况讨论 ：

  • 假设 $x$ 的位数 $<n$

  • 假设 $x$ 的位数 $=n$ ，开头元素 $<S_0$

  • 假设 $x$ 的位数 $=n$ ，开头元素 $=S_0$ （Trick ：按照前缀相同的位数枚举）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include<bits/stdc++.h>
using namespace std;
#define int long long

/**
 * Snake Numbers :
 * 蛇数，是指最高位的值大于其余所有位的值的一种数, 给你 x , y (10 <= x <= y), 求 x ~ y 一共有多少蛇数 ?
 * 1、f(x) 表示 10 ~ x 有多少蛇数, 那么答案 = f(y) - f(x - 1)
 * 2、假设 x 的位数为 n, 
 *      2.1、首先考虑所有位数 < n 的数, 
 */

/**
 * 举例 
 * 56126
 * 1、先考虑 < n 位的 :
 * 对于 2 位数 : 10 ; 20 21 ; 30 31 32 ; 40 41 42 43 统一 : 1 + 2 + 3 + ... + 9
 * 对于 3 位数 : 100 ; 200 201 210 211 ; 统一 : 1 + 2^2 + 3^2 + 4^2 + ... + 9^2
 * 对于 4 位数 : 1000 ; 2000 2001 ... ; 统一 : 1 + 2^3 + 3^3 + 4^3 + ... + 9^3
 * 2、在考虑 = n 位的, 先考虑开头小于 S0 的情况
 * 1 开头 : 10000
 * 2 开头 : 2____ 2^4
 * 3 开头 : 3____ 3^4
 * 4 开头 : 4____ 4^4
 * 3、最后考虑 = n 位, 且开头元素 = S0 的情况
 * 考虑按照第几位出现不同分情况讨论 :
 * 以 54265 为例
 * 第二位不同 : 5 x _ _ _, 0 1 2 3 -> 4 * 5^3
 * 第三位不同 : 5 4 x _ _, 0 1     -> 2 * 5^2
 * 第四位不同 : 5 4 2 x _, 5 * 5^1
 * 特殊情况 : 
 *  5 4 3 2 2 
 * 最后一位 2 可以取0、1、2，并非只有 0、1可以取
 */ 

/**
 * 求 1 ~ x 有多少个蛇数 ?
 */

int pow(int a, int b) {
    int res = 1;
    while(b --) {
        res *= a;
    }
    return res;
}

int f(int x) {
    if(x < 10) return 0;

    string sx = to_string(x);
    int n = sx.size();
    int res = 0;

    // 1 : 从 2 开始枚举位数, 枚举开头 
    for(int ln = 2; ln < n; ln ++) { 
        for(int st = 1; st <= 9; st ++) {
            res += pow(st, ln - 1);
        }
    }

    // 2 : 位数 = n, 开头 < S[0]
    int S0 = sx[0] - '0';
    for(int st = 1; st < S0; st ++) {
        res += pow(st, n - 1);
    }

    // 3 : 位数 = n, 开头 = S0
    for(int i = 2; i <= n; i ++) {
        int Si = sx[i - 1] - '0';
        if(Si >= S0) { 
            res += S0 * pow(S0, n - i); // [i, n] 都可填 0 ~ S0 - 1
            break;
        }
        else {
            res += Si * pow(S0, n - i); // 这一位 Si 种, 最后几位 0 ~ S0 - 1
            if(i == n) res ++; // 特判
        }
    }
    return res;
}

void solve(){
    int x, y;
    cin >> x >> y;
    cout << f(y) - f(x - 1) << '\n';
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0); 
    solve();
    return 0;
}