这个题目前还没有好的办法，只能在筛法的基础上做优化。筛法是这样的：对于任意一个k，将d(k)标记一下，这样，1-n之间不带标记的，就是self-number。
　　标记并不需要O(n)的空间，可以采用循环使用数组的办法，因为d(k)-k<=9*7=63，所以数组开到64就够了。
　　为了再取得一些时间上的优势，可以把10000以下的数的各个数位上数字之和预处理出来，这样，计算k的各个数位上数字之和所需时间就下降到O(1)了。
　　注意题目中给出的s1...sk并不是从小到大的。
　　Submit 1: WA on 2。可能是由于数组超界造成的，加设一个哨兵。特殊点n=1的时候也错了。并不是特殊点错了，而是只判断了[1,n-1]之间的self-number。
　　Submit 2: WA on 5。s1...sk不一定是不重复的。
　　Submit 3: AC。

?View Code CPP
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

#include <cstdio>
#include <algorithm>
using namespace std;
 
struct selfnum
{
    int id,idx,num;
};
 
inline bool cmp_id(const selfnum &s1,const selfnum &s2)
{
    return s1.id<s2.id;
}
 
inline bool cmp_idx(const selfnum &s1,const selfnum &s2)
{
    return s1.idx<s2.idx;
}
 
int main()
{
    int n,k,r(0),p(0),sumdig[10000];
    selfnum s[5001];
    bool self[64];
    scanf("%d%d",&n,&k);
    for (int i(0);i<k;i++)
    {
        scanf("%d",&s[i].idx); s[i].id=i;
    }
    s[k+1].idx=0;
    sort(s,s+k,cmp_idx);
    fill(self,self+64,true);
    for (int i(0);i<10000;i++) sumdig[i]=i/1000+i/100%10+i/10%10+i%10;
    for (int i(1);i<=n;i++)
    {
        if (self[i&63])
        {
            r++;
            while (r==s[p].idx) s[p++].num=i;
        }
        int di=i+sumdig[i/10000]+sumdig[i%10000];
        self[i&63]=true; self[di&63]=false;
    }
    sort(s,s+k,cmp_id);
    printf("%d\n",r);
    for (int i(0);i<k;i++) printf("%d ",s[i].num);
    return 0;
}