SGU 108. Self-numbers 2 离线+位优化

本文主要是介绍SGU 108. Self-numbers 2 离线+位优化，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

可以像筛选法那样标记 但是内存最多只能开1024的int数组 我用了位优化 用一个int 32 位标记32个数字 接下来就离线 排个序 算出第k大的哪个数

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;int a[10000000/32];struct node
{int x, y, id;
}b[50010];
int get(int x)
{int ans = x;while(x){ans += x%10;x /= 10;}return ans;
}
void dfs(int x)
{int tmp = x + get(x);if(tmp > 10000000 || a[tmp])return;a[tmp] = 1;dfs(tmp);
}bool cmp1(node a, node b)
{return a.x < b.x;
}
bool cmp2(node a, node b)
{return a.id < b.id;
}int main()
{//for(int i = 1; i <= 10000; i++)//	p[i] = get(i);int n, k;while(scanf("%d %d", &n, &k) != EOF){for(int i = 0; i < k; i++){scanf("%d", &b[i].x);b[i].id = i;}sort(b, b+k, cmp1);memset(a, 0, sizeof(a));int c = 0, j = 0;for(int i = 1; i <= n; i++){if(!(a[i/32]&(1<<(i%32)))){c++;while(j < k && b[j].x == c){b[j].y = i;j++;}}int x = get(i);if(x <= n)a[x/32] |= (1<<(x%32));}printf("%d\n", c);sort(b, b+k, cmp2);for(int i = 0; i < k; i++){if(i)printf(" ");printf("%d", b[i].y);}puts("");}return 0;
}

这篇关于SGU 108. Self-numbers 2 离线+位优化的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---