首页 > 代码库 > 【HDOJ】4982 Goffi and Squary Partition

【HDOJ】4982 Goffi and Squary Partition

2024-07-19 21:13:14   214人阅读

题意就是整数划分，选出和为n的K个整数，其中K-1个数的和为完全平方数S。
选择整数时需要从1,2,3..连续选择，当选择整数与n-S相等时，需要跳过n-S，即选择n-S+1。
如此选择K-2个数，从而可确定第K-1个数，若该数已经出现（小于或等于K-2），则划分失败；
若第K-1个数不等于n-S，则肯定划分成功，否则K-1个数若等于n-S。
即需要通过将第K-2个数+1，同时第K-1个数-1得到正确的划分，并且需要保证调整后第K-2个数仍小于第K-1个数，因此，两数之间的距离至少大于2。

 1 #include <cstdio> 2 #include <cmath> 3  4 int n, k; 5  6 bool judge(int s) { 7     int p, q; 8     int i, j = 0, sum = 0, tmp; 9 10     p = s*s;11     if (n == p)12         return false;13     q = n-p;14 15     for (i=1; i<=k-2; ++i) {16         ++j;17         if (j == q)18             ++j;19         sum += j;20     }21     if (sum >= p)22         return false;23     tmp = p - sum;24     if (tmp <= j)25         return false;26     if (tmp == q) {27         if (q <= j+2)28             return false;29     }30     return true;31 }32 33 int main() {34     int m;35 36     while (scanf("%d %d", &n, &k) != EOF) {37         m = sqrt((n-1)*1.0);38 39         if (judge(m))40             printf("YES\n");41         else42             printf("NO\n");43     }44 45     return 0;46 }

 

【HDOJ】4982 Goffi and Squary Partition


联系
我们