U389139 至少有一位重复的数字-题解

题目传送门

一、举例说明

以 \(654923\) 为例
要判断在 \([0, 654923]\) 区间至少有一位重复的数值的数，可以考虑其补集，即\(\color{red}所有位数均不重复的数\)，用 \(N\) 减去补集即为结果。
首先可以将其分为两种情况。

• 情况一，位数小于 \(6\) 位。所有位数均不重复的有 \(9 \times 9 \times 8 \times 7 \times 6\) 种（首位不为0）。
• 情况二，位数等于 \(6\) 位，这也可以分为两种情况，首位小于 \(6\) 或等于 \(6\) 。对于首位小于 \(6\) 的数据，所有位数均不重复的有 \(5 \times 9 \times 8 \times 7 \times 6 \times 5\) 种情况。

对于首位等于 \(6\) ，那么就要考虑次高位。可以定义一个 \(st\) 数组，来记录是否有重复的数，比如 \(654423\) ，枚举到第四位也是 \(4\) ，那么后两位无论是多少数字都无意义了，都一定没有不重复的数。因此用该数组判断某一个数字是否已被使用，已被使用就直接跳过。
从第二位 \(j=5\) 开始枚举，于是我们第二位考虑比 \(j\) 小的数即 \(0\) 到 \(4\) ，加上后面四位不重复的数，即 \(8 \times 7 \times 6 \times 5 = P(8,4) = P(10-2,4)\)，枚举后 \(st[5] = true\)。
从第三位 \(j=4\) 开始枚举，于是我们第三位考虑比 \(j\) 小的数即 \(0\) 到 \(3\) ，对于每一位数如果 \(st[k]\) 不为 \(true\) 的话，就说明此时这个数可以来当第三位数，加上后三位不重复的数即 \(7 \times 6 \times 5 = P(7,3) = P(10-3,3)\) ，枚举后 \(st[4] = true\) 。
以此将每一位数进行循环判定。每次循环完毕之后都判断一次，对应位数 \(j\) 是否重复有 \(st[j] = true\) ，如果重复了就不用继续往下面循环了，后面对应的数一定都重复。
最后跳出循环，同时我们在枚举的过程中，可以发现，第二位我们没有枚举 \(5\) ，第二位没有枚举 \(4\) …，第六位没有枚举 \(3\) ，如果能够枚举到这里，说明枚举过程中没有遇到重复的数，即这个数不是重复的数，所以要减去这个数。

二、代码实现

#include <bits/stdc++.h>
using namespace std;
int getSum(int a,int b){
    int res = 1;
    for(int i = a;b>0;b--,a--){
        res *= a;
    }
    return res;
}
vector<int>nums;
int numDupDigitsAtMostN(int n) {
    int res = n;
    //先将数整理为数组
    while(n) {
        nums.push_back(n % 10);
        n /= 10;
    }
    //情况一 比给定数位数少
    for(int i = nums.size() - 1;i > 0;i--){
        res -= 9 * getSum(9,i-1);
    }
    //情况二 和给定数位数相同 但最高位小于给定数最高位
    res -= (nums.back() - 1) * getSum(9,nums.size() - 1);
    //情况三 和给定数位数相同 最高位相同
    vector<bool> st(10);
    //然后去除首位的情况，设置首位为true不可再使用
    st[nums.back()] = true;
    for(int i = nums.size() - 2;i >= 0;i--){
        int j = nums[i];
        for(int k = 0;k < j;k++){
            //每次遇到前面用过的数就continue
            if(st[k]) continue;
            res -= getSum(10 - (nums.size() - i),i);
        }
        if(st[j]) {
            return res;
        }
        st[j] = true;
    }
    return res-1;
}
int main()
{
    int originNum;
    cin>>originNum ;
    cout<<numDupDigitsAtMostN(originNum);
    return 0;
}

如果你看到这里，你就浪费了2分钟，因为这代码太烦了(bushi