题解 P2666 【Bessie的秘密牧场】

· · 题解

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

题目简略大意

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;
}