SGU 108 Self-numbers 2
Problem's Link
Mean:
略有这样一种数字：对于任意正整数n，定义d(n)为n加上n的各个位上的数字（d是数字的意思，Kaprekar发明的一个术语）。如：d(75) = 75 + 7 + 5 = 87。给定任意正整数n，你可以构建出无限的整数递增：n, d(n), d(d(n)), d(d(d(n))), ……举个例子，你从33开始，那么下一个数就是33 + 3 + 3 = 39, 再下一个就是39 + 3 + 9 = 51, 接着就是 51 + 5 + 1 = 57, 那样就生成了一个序列： 33, 39, 51, 57, 69, 84, 96, 111, 114, 120, 123, 129, 141, ... 这里n叫做d(n)的母数 上面的数列中，33是39的母数，39是51的母数，51是57的母数，以此类推……有些数字不止一个母数，比如101有两个母数，91和100。没有母数的数字就叫做self-number。让a[i]成为第i个self-number。现在存在13个小于100的self-number： 1, 3, 5, 7, 9, 20, 31, 42, 53, 64, 75, 86, 和 97. (第一个 self-number是a[1]=1, 第二个是 a[2] = 3, 第十三个是 a[13]=97).
analyse:
此题比较BT，内存卡得比较紧，做的时候需要考虑如何压缩内存,不过还是1.5s把它过了.
主要方法就是用个滚动数组用类似筛法做,题目倒不是很难.
Time complexity: O(N)
view code
/**
* -----------------------------------------------------------------
* Copyright (c) 2016 crazyacking.All rights reserved.
* -----------------------------------------------------------------
* Author: crazyacking
* Date : 2016-01-06-19.55
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long( LL);
typedef unsigned long long( ULL);
const double eps( 1e-8);
pair < int , int > q [ 5010 ];
bool f1 [ 64 ], f2 [ 64 ];
int ans [ 5010 ];
int num ,n , m;
int main()
{
scanf( "%d %d" , &n , & m);
for ( int i = 0; i < m; ++ i)
{
scanf( "%d" , & q [ i ]. first);
q [ i ]. second = i;
}
sort( q , q + m);
int pos = 0;
memset( f1 , true , sizeof( f1));
memset( f2 , true , sizeof( f2));
for ( int i = 1; i <=n; ++ i)
{
if ( i % 64 == 0)
{
memcpy( f1 , f2 , 64);
memset( f2 , true , sizeof( f2));
}
if ( f1 [ i % 64 ])
{
num ++;
while ( q [ pos ]. first == num) ans [ q [ pos ++ ]. second ] = i;
}
int tmp = 0 , j = i;
while ( j > 0)
{
tmp += j % 10;
j /= 10;
}
if ( tmp + i % 64 >= 64) f2 [( tmp + i % 64) % 64 ] = false;
else f1 [ tmp + i % 64 ] = false;
}
printf( "%d \n " , num);
for ( int i = 0 , j; i < m; ++ i)
{
printf( "%d" , ans [ i ]);
if ( i != m - 1) printf( " ");
else printf( " \n ");
}
return 0;
}
* -----------------------------------------------------------------
* Copyright (c) 2016 crazyacking.All rights reserved.
* -----------------------------------------------------------------
* Author: crazyacking
* Date : 2016-01-06-19.55
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long( LL);
typedef unsigned long long( ULL);
const double eps( 1e-8);
pair < int , int > q [ 5010 ];
bool f1 [ 64 ], f2 [ 64 ];
int ans [ 5010 ];
int num ,n , m;
int main()
{
scanf( "%d %d" , &n , & m);
for ( int i = 0; i < m; ++ i)
{
scanf( "%d" , & q [ i ]. first);
q [ i ]. second = i;
}
sort( q , q + m);
int pos = 0;
memset( f1 , true , sizeof( f1));
memset( f2 , true , sizeof( f2));
for ( int i = 1; i <=n; ++ i)
{
if ( i % 64 == 0)
{
memcpy( f1 , f2 , 64);
memset( f2 , true , sizeof( f2));
}
if ( f1 [ i % 64 ])
{
num ++;
while ( q [ pos ]. first == num) ans [ q [ pos ++ ]. second ] = i;
}
int tmp = 0 , j = i;
while ( j > 0)
{
tmp += j % 10;
j /= 10;
}
if ( tmp + i % 64 >= 64) f2 [( tmp + i % 64) % 64 ] = false;
else f1 [ tmp + i % 64 ] = false;
}
printf( "%d \n " , num);
for ( int i = 0 , j; i < m; ++ i)
{
printf( "%d" , ans [ i ]);
if ( i != m - 1) printf( " ");
else printf( " \n ");
}
return 0;
}
