1974: A+B+C+D(打表，观察，隔板，三种解法）

解题思路:

看到这道题，我们很容易想到写一个四重循环再if判断。

#include <stdio.h>
 
int main(){
     
     
    int i;
    int x,y,n,m,z=0;
    for(i=0;i<=1000;i++){
        z=0;
        for(x=1;x<i;x++){
            for(y=1;y<i;y++){
                for(n=1;n<i;n++){
                    for(m=1;m<i;m++){
                        if(x+y+n+m==i){
                            z++;
                        }
                    }
                }
            }
        }
        printf("%d,%d\n",z,i);
    }
     
    return 0;
}

但是这样时间复杂度太高了，对于输入最大数1000来说甚至达到循环10^12次方，提交后时间会超时。

这里给大家提供三种方法。

方法一：打表。

这也是比赛常用的方法，简单来说就是使用一个代码预先得到每一种测试的答案，然后把答案放到一个数组里面，然后直接调用就可以了。

然而用for循环得到答案显然是不现实的，它在处理一百以上的数值就开始吃力了，等它得到所有答案比赛也快结束了。

这里使用递归的方法进行求解：

#include <stdio.h>
 
long long int ans = 0;
 
int dfs(int n, int m) {//n是需要处理的数，m是需要分解成几位
    
    if (m == 1 && n>0){
        ans++; 
        return 0;
    }
    for (int i = 1; i <= n - m + 1; i++) 
        
            dfs(n - i, m - 1);
}
int main()
{
    int n;
    for (int i = 0; i <= 1000; i++) {
        dfs(i, 4);
        printf("%d,\n",ans);//这里需要加上,放到数组时用于分隔
        ans = 0;
    }
    return 0;
}

这个算法在处理800以上的数值速度才开始出现放慢，不过直接用来提交答案还是会“时间超限”。

最后将得到的数据放到数组里面，这才是我们要提交的最终答案：

#include int main()
{
	int n;
	scanf("%d",&n);
	int p[1000]={ctrt+v};//把得到的数值Ctrl+c Ctrl+v过来
	while(scanf("%d",&n)!=EOF){
		printf("%d\n",p[n]); 
	}
	
	return 0;
}

当然这种方法比较麻烦，递归函数也比较难理解，我还是推荐大家用数学的角度去做题，这样可以减轻大量的工作。

方法二：观察。

观察数值，当n是2，3，4，5，6，7，8，9时

答案是                0，0，1，4，10，20，35而这些数之间的差,0,1,3,6,10,15，而这些差的差是1,2,3,4,5……

是不是很神奇，这样我们就得出他的规律来了

开两组数组，用来存放他们的差和差的差

具体代码如下：

#include <stdio.h>
 
int main()
{
    int i;
    int n,z=0;
    scanf("%d",&n);
    int p[1001]={0,0,0,1,3,6};//答案的差
    int l[1001]={0,0,1,2,3,4}; //答案的差的差
    while(scanf("%d",&n)!=EOF){
        for(i=0;i<n;i++){
            if(i>2){//开始有不符合规律的0，需要排除 
                p[i]=p[i-1]+l[i-1];
                z+=p[i];
                l[i]=l[i-1]+1;
            }
        }
        printf("%d\n",z);
        z=0; 
    }
     
     
    return 0;
}

方法三：隔板法。

这里需要用到一点高中学过的排列组合的知识，以输入8为例，我们把8分成8个1，依次排开，会得到七个间隔。

用3个隔板放到间隔中，就把这8个1分成了4份，也就是我们需要的四个数。

在七个间隔中任意取三个空位放上隔板，全部的放法有C(7,3)=(7*6*5)/(3*2*1)。

因为题目要求分成四个数，所以一直是三个隔板，即分母上是6一直不变，分子是(n-1)*(n-2)*(n-3)

代码实现如下：

#include <stdio.h>
 
int main()
{
    int n;
    scanf("%d",&n);
    while(scanf("%d",&n)!=EOF){
        if(n>3)printf("%d\n",(n-1)*(n-2)*(n-3)/6);
        else printf("0\n");
    }
     
    return 0;
}