关于CSP-X题目

这里说的是 JX 的题目，个人评级：红红红?

T1 到 T3 非常简单，可是 T4 全场无人做对。

T4 题目大意：给定一个正整数

n

，要求将

n

分解为

k

个整数的平方之和的形式，求这个最小的

k

。

数据范围：

n\le10^5

。

同学们的主要做法有两种：

CPP

for (int i = 1; i <= n; i++) {
    for (int j = 1; j * j <= i; j++) {
        f[i] = min (f[i], f[i - j * j] + 1);
    }
}

CPP

while (n) {
    int x = sqrt (n);
    n -= x;
    ans++;
}

据说题目是请 mx 出的。

求问此题正解。

小学生不才，求问正解。~~其实教练不让我发的这个帖子的。~~

讨论操作