题目链接

http://acm.sgu.ru/problem.php?contest=0&problem=108

题目大意

定义d(n):d(n)=n+[n的各位数之和]

如果某个数不能由一个数通过多次d(n)得到这个数,那么称这个数为“自我数”

题解

一开始以为水题很快就写了交上去就错了,然后发现内存只给4M,然后改用滚动数组。

因为长度最大为7,因此每个数只会影响此后最长为7*9 = 63长度的数字。

代码

//
//  main.cpp
//  sgu
//
//  Site @haipz.com
//  Copyright (c) 2015年 林海鸿. All rights reserved.
//

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

const int K = 5e3, L = 64;
struct node {
    int i, ans, idx;
};
bool f[L + 5];
node a[K + 5];

bool cmp(node a, node b) {
    return a.i < b.i;
}

bool _cmp(node a, node b) {
    return a.idx < b.idx;
}

int getD(int x) {
    int tx = x;
    while (x) {
        tx += x % 10;
        x /= 10;
    }
    return tx;
}

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= k; ++i) {
        scanf("%d", &a[i].i);
        a[i].idx = i;
    }
    sort(a + 1, a + 1 + k, cmp);
    memset(f, true, sizeof(f));
    int ansi = 1, cnt = 0;
    for (int i = 1; i <= n; ++i) {
        if (f[0]) ++cnt;
        while (cnt == a[ansi].i) a[ansi++].ans = i;
        int d = getD(i);
        f[d - i] = false;
        for (int i = 0; i < L; ++i) f[i] = f[i + 1];
    }
    sort(a + 1, a + 1 + k, _cmp);
    printf("%d\n", cnt);
    for (int i = 1; i < k; ++i) printf("%d ", a[i].ans);
    printf("%d\n", a[k].ans);
    return 0;
}
转载保留版权:http://haipz.com/blog/i/6442 - 海胖博客