hiho #1372:平方求 (bfs)

#1372 : 平方求和

时间限制:1000ms

单点时限:1000ms

内存限制:256MB

描述

对于一个非负整数n，最少需要几个完全平方数，使其和为n？

输入

输入包含多组数据。对于每组数据：

第一行是n；如果n为-1，表示输入结束。(0 <= n <= 1000000001)

输出

针对每组数据，输出最少需要的完全平方数。

样例输入

样例输出

3
1
2

思路：

拿到这个题，我第一想到的是贪心，每次减去一个最大数的平方，但是有时候这样会得不到正确的答案，比如19 ，贪心的话就是4，1，1，1.。。。正确的应该是3，3，1.。。。

然后dp，dp虽然可以得到正确的答案，但是时间复杂度高了。pass。

在想到搜索

让我们可视化一下，

原来是个搜索的题目。

如何加速？

我们应该深度优先搜索吗？

当然不是啦！因为我们求的是最少的拆解，所以应该宽度优先搜索。

宽搜的时候，用一个last和一个nlast分别记录当前行的最后一个元素，和下一行的最后一个元素。

如何再加速？

如果我们为了收敛快，似乎方向反了。

如何再加速？

我们有些节点是不是可能重复访问？建立一个hash表存一下吧。

如何再快呢？

证明题：每个正整数都可以表示为4个完全平方数的和。

什么？居然还需要数论的知识。我不知道怎么办？

没什么啊，我们刚才的宽度优先搜索已经能够保证和这个算法是一个复杂度了。

代码：

宽搜：

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <queue>
 4 using namespace std;
 5 
 6 //5324124312
 7 int bfs(long long n)
 8 {
 9     queue<long long> q;
10     int t = 1;
11     long long head,last=n,nlast; //last当前行最右，nlast下一行最右
12     q.push(n);
13     while (!q.empty())
14     {
15         head = q.front();
16         if (t == 3)
17         {
18             int c = 444;
19         }
20 
21         if (t == 4)
22             break;
23         q.pop();
24         if (head != 0)
25         {
26             for (int i = sqrt(head); i > 0; i--)
27             {
28                 if (head - i*i == 0)
29                     return t;
30                 q.push(head-i*i);
31 
32                 nlast = head - i*i;
33             }        
34 
35             if (head == last && !q.empty())
36             {
37                 t++;
38                 last = nlast;
39             }
40         }
41     }
42 }
43 
44 int main()
45 {
46     long long n;
47     while (cin>>n)
48     {
49         if (n == -1)
50             break;
51         cout<< bfs(n)<<endl;
52 
53     }
54     system("pause");
55     return 0;
56 }

数论方法AC：

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <queue>
 4 using namespace std;
 5 
 6 //5324124312
 7 bool is_sqrt(long long n)
 8 {
 9     int m = sqrt(n);
10     if (m*m == n)
11         return true;
12     else
13         return false;
14 }
15 
16 int solve(long long n)
17 {
18     if (is_sqrt(n))
19         return 1;
20     while (n % 4 == 0)
21         n /= 4;
22 
23     if (n % 8 == 7)
24         return 4;
25 
26     for (int i = 0; i*i < n; i++)
27     {
28         if (is_sqrt(n - i*i))
29             return 2;
30     }
31     return 3;
32 }
33 
34 int main()
35 {
36     long long n;
37     while (cin>>n)
38     {
39         if (n == -1)
40             break;
41         cout<< solve(n)<<endl;
42 
43     }
44     system("pause");
45     return 0;
46 }