HDU 4982 Goffi and Squary Partition：構造平方數分割序列

題目大意

給定 n 和 k，判斷是否存在 k 個互不相同的正整數，使得前 k-1 個數的和是完全平方數，且所有 k 個數的總和等於 n。

解題思路：枚舉平方數 + 貪心構造

1. 枚舉可能的平方數 s = i*i (1 ≤ i*i ≤ n)，設 lef = n - s 為第 k 個數。
2. 構造前 k-1 個數的最小可能和：從 1 開始取 k-2 個最小的不等於 lef 的正整數，設其和為 ss。
3. 第 k-1 個數為 temp = n - ss - lef。需滿足：temp > 前 k-2 個數的最大值、temp != lef、且不與前 k-2 個數衝突。
4. 通過調整前 k-2 個數（整體 +1 或 +2）來避開衝突，檢查可行性。

核心判斷函數

bool judge(int sum, int lef) { // sum = s = i*i, lef = n - s
    if (lef == 0 || 2*sum < (k-1)*k) return false; // 最小和超過 sum
    if (sum == 1 && lef == 1) return false; // 特殊情況
    int x = 0, ss = 0;
    for (int i = 0; i < k-2; i++) { // 構造最小的 k-2 個數
        x++;
        if (x == lef) x++; // 跳過 lef
        ss += x;
    }
    int temp = n - ss - lef; // 第 k-1 個數
    if (temp <= x) return false; // 必須大於前 k-2 個數的最大值
    x++; // 前 k-2 個數整體 +1 的情況
    if (temp == x && temp == lef) return false; // 衝突情況 1
    if (temp == x+1 && temp == lef) return false; // 衝突情況 2 (+2)
    return true;
}

完整 C++ 代碼

#include <cstdio>
int k, n;
bool judge(int sum, int lef) { /* 如上 */ }
int main() {
    int i, lef;
    while (scanf("%d %d", &n, &k) != EOF) {
        int flag = 0;
        for (i = 1; i*i <= n; i++) {
            lef = n - i*i;
            if (judge(i*i, lef)) break;
        }
        if (i*i <= n) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

複雜度分析

• 枚舉平方數：O(√n)
• 每次判斷：O(k)
• 總體：O(k√n)，滿足題目限制。