指针原来是套娃的


私信TA

用户名:uq_92467646842

访问量:52369

签 名:

个人博客:blog.imtwa.top

等  级
排  名 11
经  验 26504
参赛次数 49
文章发表 128
年  龄 0
在职情况 学生
学  校
专  业 物联网工程

  自我简介:

解题思路:

看到这道题,我们很容易想到写一个四重循环再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;
}


 

0.0分

164 人评分

  评论区

  • «
  • »