YY and Lucky Number

★ 题目信息

题目描述：

YY 的幸运数字是…，是什么数字我也不知道，但是已知这个数字的十进制表示（不含前导零）中只包含不超过两个不同的数字。

给定一个数 n ，请计算出不超过 n 的所有正整数中，有可能是 YY 的幸运数字的个数。

输入：

输入一行，包含一个正整数 n。

对于 60% 的数据：1≤n≤1051≤n≤10^5

对于 100% 的数据：1≤n≤1091≤n≤10^9

输出：

输出一个整数，表示不超过 nn 的所有正整数中，有可能是 YY 的幸运数字的个数。

输入样例：

1
103

输出样例：

1
101

样例解释：

不超过103的所有正整数中，只有102、103不可能是 YY 的幸运数字。

★ 题解

这题的解法五花八门，数位dp、二分的都有，比较了各方答案之后，感觉这个最好理解了…（实际是自己做不出来，想了两天，思路都太复杂）

  1. 对于一个数字而言，各个位置上的数字不能有超过两个不同，因此在使用dfs进行逐位遍历并循环可能取值的时候，需要有pre和post保存之前使用过的数字。
  2. 当i值和pre或者post重复时，显然当前这个值是可以被选作幸运数字的，那么就继续之后的dfs过程。
  3. 如果i值和pre、post都不重复，又可以分成两种情况。其中一个是post为-1时，表明前面只用了一个数，那么接下来的dfs中post将赋值为i，表明它是可用的。第二种情况是i与pre、post均不相同，那可以进行剪枝操作，就是整个都废了。
  4. 最后需要注意的是，我们处理的数是不能大于n的，所以(n - i) / cur < 10判断也非常重要。
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
#include<iostream>
#include<vector>
using namespace std;
vector<int> nums;
int n, ans = 0;

void dfs(int cur, int pre, int post) {
    
    ++ans; // 当前结果可行
    
    for(int i = 0; i < 10; i++) {  //   确定下一位的值，取值范围为0-9
        
        // 当前位的取值不能使得数值大于n
        if((n - i) / cur < 10) continue;
        
        // 判断当前位置取值是否与前面相同
        if(i == pre || i == post) {
            dfs(cur*10+i, pre, post);
        } else if(post == -1) {
            dfs(cur*10+i, pre, i);
        }
    }
}

int main() {
    cin >> n;
    for(int i = 1; i < 10; i++) {
        dfs(i, i, -1);  // 遍历第一位可能出现的所有结果
    }
    cout << ans;
}

YY and One

★ 题目信息

题目描述：

YY 很享受一个人独处的时光。

这可能也是 YY 对 1 这个数字情有独钟的原因。

现在，对于给定的一个正整数 n，YY 想把它表示为若干个加数之和，其中每个加数都是仅包含 1 的整数。YY 想知道这些加数最少可以包含多少个 1 。

例如：对于正整数 10，可以表示为：10=11+(−1)10=11+(−1) ，包含 3 个 1 。

输入：

输入一行，包含一个正整数 n。

对于 60% 的数据：1≤n≤1051≤n≤10^5

对于 100% 的数据：1≤n≤10121≤n≤10^12

输出：

输出一个整数，表示所有加数包含 1 的个数的最小值。

输入样例：

1
1232

输出样例：

1
10

样例解释：

最优解为：1232=1111+111+11+(−1) ，包含 10 个 1 。

★ 题目信息

  1. 对于整数n，先找到第一个比它大且全为1的数，和第一个比它小且全为1的数。比如对于123来说，第一个比他大并且全为1的数是1111，第一个比它小并且全为1的数是111。
  2. 比较它们和n之间的差值，对较小的那个进行递归处理，处理差值即可。比如，123离111更近，实际问题就转化成了，（123-111）之间还需要多少个1才能完成计算。也就是说，count(123)表示的是实现123要几个1，现在的问题就变成了，count(111) + count(12) = 3 + count(12)
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
#include<iostream>
using namespace std;

int SumOne(long long num) {
    if (num == 0) return 0;
    int count = 0;
    long long res = num, t = 1, mini = 0;
    while (t <= res) {
        count++;
        mini = t;
        t = t * 10 + 1;
    } // 结束时t>n，是第一个大于n且全为1的数，1的个数为count+1
    if(res - mini <= t - res) {
        return count + SumOne(res - mini);
    } else {
        return count + SumOne(t - res) + 1;
    }
}

int main() {
    long long n;
    cin >> n;
    cout << SumOne(n);
    return 0;
}