hdu 4982 Goffi and Squary Partition(构造)

本文主要是介绍hdu 4982 Goffi and Squary Partition(构造)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：hdu 4982 Goffi and Squary Partition

题目大意：给定n和k，求一个包含k个不相同正整数的集合，要求元素之和为n，并且其中k-1的元素的和为完全平方数。

解题思路：枚举平方数然后判断剩下的是否能组成即可。尽量用小的数去构造。

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>using namespace std;int N, K;bool check (int s, int f, int n) {if (f == 0)return false;int p = 1;for (int i = 1; i < n; i++) {if (p == f)p++;if (s <= p)return false;s -= p;p++;}while (true) {if (s < p)return false;if (s != f)return true;p++;s--;}return false;
}bool judge () {int n = (int)sqrt((double)N);while (n) {if (check(n * n, N - n * n, K - 1))return true;n--;}return false;
}int main () {while (scanf("%d%d", &N, &K) == 2) {printf("%s\n", judge() ? "YES" : "NO");}return 0;
}

这篇关于hdu 4982 Goffi and Squary Partition(构造)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---