自动搬运

查看原文

来自洛谷，原作者为

	Peter_Z 我永远喜欢珂朵莉 (AFO)

搬运于2025-08-24 21:40:13，当前版本为作者最后更新于2017-11-18 14:38:12，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

两年前的题解竟然获得了这么多赞，不胜惶恐，更新一波。（主要是更详细地解释题目大意和新增一种方法）

题目简略大意

Bessie有四块正方形草皮，一共包含$N$个格子，现在Bessie想知道有多少种安排草皮边长的方法，让总格子数为$N$。

换句话说，就是有4个完全平方数$a^2,b^2,c^2,d^2$，问有多少种安排$a,b,c,d$的办法，使$a^2+b^2+c^2+d^2=N$（其中$a,b,c,d \ge 0$）。

做法：暴力/dfs/双向搜索。

1.暴力

思路：枚举三个完全平方数的可能性，然后判断剩下这个数是不是完全平方数。

具体地说，枚举$a,b,c$，那么剩下这个数就确定了，是$N-a^2-b^2-c^2$，只需要判断这个数是否为完全平方数。

可以用一个数组来保存平方数的集合，另一个数组来保存每个数是否为平方数。

这样判断平方数的时间复杂度就可以降为O(1)，总时间复杂度为$O(\sqrt{N^3})=O(N\sqrt N)$，当$N$取$10000$时$N\sqrt N=1000000$，可过。

2.dfs

思路：仍然用一个数组来保存平方数的集合，另一个数组来保存每个数是否为平方数，然后暴力dfs即可。

3.Meet in the middle

这个算法听起来比较高端，但实际上很简单……

我们把题目中要求的$a^2+b^2+c^2+d^2=N$移项，让变量平均分在等式两端：$a^2+b^2=N-c^2-d^2$。

我们先枚举$a,b$，预处理出对于每个数$x$，安排$a,b$使得$a^2+b^2=x$的方案数有多少。记这个方案数为$num[x]$。

然后我们枚举$c,d$，对于每次枚举到的$c,d$，计算出$n-c^2-d^2$。那么我们可以把$num[N-c^2-d^2]$累加到答案中。因为对于当前的$c,d$共有$num[N-c^2-d^2]$种方案。

可以看出，前两种的时间复杂度是$O(N\sqrt N)$的。而这种方法只需要枚举两个变量，每个变量是$O(\sqrt N)$的，因此这种方法的时间复杂度是$O(\sqrt{N^2})=O(N)$。

代码：

1.暴力

#include<stdio.h>
#include<math.h>
int sqr[101];
bool app[20001];
int main() {
    int n,f,ans=0;
    scanf("%d",&n);
    f=sqrt(n);
    for(register int i=0; i<=f; i++) {
        sqr[i]=i*i;
        app[i*i]=true;
    }
    for(register int i=0; i<=f; i++) {
        for(register int j=0; j<=f; j++) {
            if(sqr[i]+sqr[j]>n) break;
            for(register int k=0; k<=f; k++) {
                if(sqr[i]+sqr[j]+sqr[k]>n)  break;
                if(app[n-sqr[i]-sqr[j]-sqr[k]]) {
                    ans++;
                }
            }
        }
    }
    printf("%d",ans);
    return 0;
}

2.dfs

//dfs 
#include<stdio.h>
#include<math.h>
int sqr[101],n,f,ans;
int a[5];
bool app[10001];
void dfs(int p,int sum) {
    if(sum>n)    return;
    if(p==3 && !app[n-sum])    return;
    if(p==4 && n==sum) {
        ans++;
        return;
    }
    if(p>4)    return;
    int f2=sqrt(n-sum);
    for(int i=0; i<=f2; i++) {
        dfs(p+1,sum+sqr[i]);
    }
}
int main() {
    scanf("%d",&n);
    f=sqrt(n);
    for(int i=0; i<=f; i++) {
        sqr[i]=i*i;
        app[i*i]=true;
    }
    dfs(0,0);
    printf("%d",ans);
    return 0;
}

3.Meet in the middle

#include<stdio.h>
#include<math.h>
int sqr[101],num[10001];
bool app[20001];
int main() {
    int n,f,ans=0;
    scanf("%d",&n);
    f=sqrt(n);
    for(int i=0; i<=f; i++) {
        sqr[i]=i*i;
        app[i*i]=true;
    }
    for(int i=0; i<=f; i++) {
        for(int j=0; j<=f; j++) {
            if(sqr[i]+sqr[j]>n) break;
			//第一步，先预处理出把一个数表示为两个完全平方数相加的方案数 
            num[sqr[i]+sqr[j]]++;
        }
    }
    for(int i=0; i<=f; i++) {
    	for(int j=0; j<=f; j++) {
    		if(sqr[i]+sqr[j]>n)	break;
    		//第二步，枚举i,j，把num[n-i^2-j^2]累加到答案中 
    		ans+=num[n-sqr[i]-sqr[j]];
		}
	}
    printf("%d",ans);
    return 0;
}