HDU 4982 Goffi and Squary Partition(推理)

HDU 4982 Goffi and Squary Partition

思路:直接从全然平方数往下找,然后推断是否能构造出该全然平方数,假设能够就是yes,假设都不行就是no。注意构造时候的推断,因为枚举一个全然平方数。剩下数字为kk。构造的时候要保证数字不反复

代码:

#include <cstdio>
#include <cstring>
#include <cmath> int n, k; bool judge(int num) {
int yu = num * num;
int kk = n - yu;
if (kk == 0) return false;
int sum = 0;
int cnt = 0;
for (int i = 0; i < k - 2; i++) {
cnt++;
if (cnt == kk) cnt++;
sum += cnt;
}
if (sum + kk >= n) return false;
int need = n - sum - kk;
if (need <= cnt) return false;
cnt++;
if (kk == cnt || kk == cnt + 1) {
if (need == kk) return false;
}
return true;
} bool solve() {
int m = sqrt(n * 1.0);
for (int i = m; i >= 1; i--) {
if (judge(i)) {
return true;
}
}
return false;
} int main() {
while (~scanf("%d%d", &n, &k)) {
if (solve()) printf("YES\n");
else printf("NO\n");
}
return 0;
}
上一篇:ASP.NET Core WebApi使用Swagger生成api


下一篇:web应用和http协议