P4719 优雅数（基础）

解题思路

一个数是"优雅的"，是指把它写成数字串后，如果这个数有 n 位，那么 n 个数字中有 n-1 个完全相同，恰好有 1 个数字不同。比如 33323（四个 3 和一个 2）、110（两个 1 和一个 0）都是优雅数；而 9779（两个 9 和两个 7）以及 55555（所有数字都相同）都不是优雅数。

我们可以换个更清晰的角度理解"优雅"：一个数必须是优雅的，当且仅当它"恰好含有两种不同的数字，并且其中一种数字只出现 1 次，另一种数字出现 n-1 次"。

于是算法就很直接了：枚举 [L,R] 区间里的每一个整数 x，逐个判断：

1. 把 x 的每一位数字拆出来，用一个长度为 10 的数组 cnt[0..9] 统计每个数字 0~9 各出现了几次。
2. 统计两个指标：distinct 表示"出现了几种不同的数字"，one 表示"只出现 1 次的数字有几种"。
3. 如果 distinct 恰好等于 2，并且 one 恰好等于 1，说明这个数有两种数字、其中一种只出现一次，另一种自然出现 n-1 次，完全符合优雅数的定义，答案加一。

为什么不用再检查"另一种出现 n-1 次"？因为总位数 n 是固定的，总共就两种数字，一种出现 1 次，剩下的次数自然全落在另一种数字上。

边界情况：L 最小是 100（至少三位），R 最大是 10^6，区间内最多 10^6 个数，每个数最多拆 7 位，运算量约 7×10^6，非常快。像 1000000 这样的数（一个 1 和六个 0）也满足"一种数字出现一次"，只要它在区间内就会被正确统计。

参考代码

// 优雅数：统计[L,R]中满足n-1个数字相同、恰有1个数字不同的数
#include <cstdio>
int cnt[10]; // 统计每个数字出现的次数
int main() {
    int L, R;
    scanf("%d%d", &L, &R);
    int ans = 0;
    for (int x = L; x <= R; x++) {
        for (int i = 0; i < 10; i++) cnt[i] = 0;
        int t = x;
        while (t > 0) { // 拆出每一位数字
            cnt[t % 10]++;
            t /= 10;
        }
        int distinct = 0, one = 0;
        for (int i = 0; i < 10; i++) {
            if (cnt[i] > 0) {
                distinct++;          // 出现过的数字种类数
                if (cnt[i] == 1) one++; // 只出现1次的数字个数
            }
        }
        // 优雅：恰好2种数字，且其中一种只出现1次（另一种自然出现n-1次）
        if (distinct == 2 && one == 1) ans++;
    }
    printf("%d\n", ans);
    return 0;
}

复杂度分析

程序要枚举 [L,R] 区间内的每个整数，区间最多有 10^6 个数；对每个数拆位统计，每个数最多 7 位数字。总操作量大约 7×10^6，时间复杂度 O((R-L+1)×10)，完全可以接受。

空间方面，只用一个长度为 10 的计数数组和几个 int 变量，空间复杂度 O(1)，非常节省。