SGU 108 Self-numbers 2

The memory limit is low, and the time limit is also pretty low

Time:

Cut a number into half, numerate sum of digit from 1~9999

Memory:

a number is a self number or not is only determined by at most the number smaller than it by 63.

So you can Divide the numbers into 64 numbers per group, and dp them.

Like this: dp[2][64]

其實就是暴搜啦，但要用滾動壓一壓記憶體

//By momo
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int n, k, ans[5010], v[10000], c[2][64];
struct pos{ int v, i; }s[5010];
bool comp(pos a, pos b){ return a.v < b.v; }

int part(int x){ return (x >> 6) & 1; }
int main(){

    scanf("%d%d", &n, &k);
    for(int i = 0; i < k; i++) scanf("%d", &s[i].v), s[i].i = i;
    
    sort(s, s+k, comp);
    
    for(int i = 0; i < 10000; i++){
        int x = i;
        while(x){ v[i] += x%10; x /= 10; }
    }

    int cnt = 0;
    for(int i = 1, j = 0; i <= n; i++){
        
        int add = i + v[i/10000] + v[i%10000];
        if(c[part(i)][i & 63] == 0){
            cnt++;
            while(j < k && s[j].v == cnt) ans[s[j++].i] = i;
        }
        c[part(add)][add & 63] = 1;
        if((i & 63) == 63) memset(c[part(i)], 0, sizeof(c[0]));
    }

    printf("%d\n", cnt);
    for(int i = 0; i < k; i++) printf("%d%c", ans[i], i == k-1?'\n':' ');
}