SGU 108 (空间优化)

本文主要是介绍SGU 108 (空间优化)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这题本来觉得是道没什么的水题，结果没想到空间卡得这么死

于是注意观察式子，发现每个推到后面最多加7 * 9 (7位数，每位是9)

于是就只要开64的空间，利用滚动数组去优化即可

另外还要注意，答案表全打出来也是会MLE的，只能根据输入的k去存放k个答案

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;int n, k, dp[65], sum[10005];int get(int x) {int sum = 0;while (x) {sum += x % 10;x /= 10;}return sum;
}struct A {int a, id;void read(int id) {this->id = id;scanf("%d", &a);}
} x[5005];bool cmp(A a, A b) {return a.a < b.a;
}int ans[5005];int main() {for (int i = 1; i <= 10000; i++) sum[i] = get(i);scanf("%d%d", &n, &k);int out = 0;for (int i = 0; i < k; i++)x[i].read(i);sort(x, x + k, cmp);int u = 0;for (int i = 1; i <= n; i++) {if (!dp[i % 64]) {out++;while (x[u].a <= out) {if (x[u].a == out) ans[x[u].id] = i;u++;}}dp[(i + sum[i / 10000] + sum[i % 10000]) % 64] = true;dp[i % 64] = false;}printf("%d\n", out);for (int i = 0; i < k; i++)printf("%d%c", ans[i], i == k - 1 ? '\n' : ' ');return 0;
}

这篇关于SGU 108 (空间优化)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---