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;

}