题目链接
https://ac.nowcoder.com/acm/contest/13504/C
解题思路
1.深搜剪枝
1.很难从1~1000打表,记录所有的数;
2.我们可以选择每输入一次,进行判断一次;
3.剪枝优化
DFS(k,num)表示第5-k个数选择之后的num值,当num==0&&k==0时,即为答案;
每次遍历选择 sqrt(num)~1,这样只需要根号n的时间复杂度;
代码展示
#include<bits/stdc++.h>
using namespace std;
const int inf=1000000;
/*
思路:
*/
bool DFS(int k,int num){
if(num==0&&k!=0)return false;
if(k==0&&num!=0)return false;
if(num==0&&k==0){
return true;
}
int x=sqrt(num);
for(int i=x;i>=1;i--){
if(DFS(k-1,num-i*i))
return true;
}
return false;
}
int main(){
int t;
cin>>t;
while(t--){
int x;
cin>>x;
if(DFS(5,x))
cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}
2.数论
1.首先了解`拉格朗日四平方数和定理:`
即对于任意一个正数,都能表示成4个平方数的和(平方数包括0)
2.然后有一个特殊的数`169`
·169可以表成1个、2个、3个或者四个平方数之和
169=13*13
169=12*12+5*5
169=12∗12+4∗4+3∗3
169=10∗10+8∗8+2∗2+1∗1
169=12∗12+4∗4+2∗2+2∗2+1∗1
3.再然后我们证明大于169的数都能用5个平方数表示:设n=m+169 (n>=169)
由拉格朗日四平方数和定理:得知m的四个平方数中可以包含[0,4]个正数
当m中有四个正数平方数时,n=m+13*13 ----总共五个平方数
当m中有三个正数平方数时,n=m+12*12+5*5 ----总共五个平方数
当m中有二个正数平方数时,n=m+12∗12+4∗4+3∗3 ----总共五个平方数
~~~~~
4.以上可说明大于169的任意数都能用5个正平方数表示,然后再打表计算1~169中不能用5个正平方数表示的数即可;
总结
1.找规律的题当规模不大时,优先考虑深搜;
2.当规模很大时,先打表找一个小范围的取值情况,看能不能找到规律;