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;
}
| Github | Facebook | Twitter |