B_建造新家

B_建造新家

思路：数学公式法

这是一道数学题，根据题目算出求和公式来缩短时间 （这居然是一道数学题！！！！！ヾ(≧へ≦)〃）

难以置信我卡在了什么鬼地方

先贴上我的错题

#include<stdio.h>
typedef long long int i64;
int main(void)
{
    i64 n;
    scanf("%lld",&n);
    i64 a[100005];
    i64 A=0,B=0,C=0;
//    printf("1\n");
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        A+=a[i];
        B+=(i*i*a[i]); //这里
        C+=(i*a[i]);
    }
    i64 min;
    i64 sum=0;
    for(int i=1;i<=n;i++)
    {
        sum=i*i*A+B-2*i*C; //这里
        if(i==1)
        {
            min=sum;
        }
        if(sum<min)
        {
            min=sum;
        }
    }
    printf("%lld\n",min);
    return 0;
}

再看看正确的

#include<stdio.h>
typedef unsigned long long int i64;
int main(void)
{
	i64 n;
	scanf("%lld",&n);
	i64 a[100005];
	i64 A=0,B=0,C=0;
//	printf("1\n");
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		A+=a[i];
		B+=(i*a[i]*i); //这里
		C+=(i*a[i]);
	}
	i64 min;
	i64 sum=0;
	for(int i=1;i<=n;i++)
	{
		sum=i*A*i+B-2*C*i; //这里
		if(i==1)
		{
			min=sum;
		}
		if(sum<min)
		{
			min=sum;
		}
	}
	printf("%lld\n",min);
	return 0;
}

来找不同吧(●'◡'●)

涨知识 遇到int的乘法都需要注意一下

与整型乘整型结果只能是整型，所以B+=(i * i* a[ i ]);这里爆int了

需要改变顺序B+=(i * a[ i ] * i);

或者改成这样 B+=(1ll * i * i * a[ i ]);

（1ll就是将1转化为long long再相乘就将结果转化为long long类型了）

（感觉和 i * 1.0 这样的处理方法类似）

再或者就直接开全局long long了

E_小青找宝藏

思路：列表然后暴力

（什么时候才能不在细节出问题😭）

先看看错误代码

#include<stdio.h>
typedef long long int i64;
int main(void)
{
    i64 fib[100005]={0};
    fib[0]=0;
    fib[1]=1;
    fib[2]=1;
    i64 cnt=2;
    while(fib[cnt]>0)
    {
        fib[++cnt]=fib[cnt-1]+fib[cnt-2];
    }
    i64 t;
    scanf("%lld",&t);
    for(int o=0;o<t;o++)
    {
        i64 n;
        scanf("%lld",&n);
        i64 sum=0;
        int p=0;
        for(int i=cnt-1;i>=0;i--)
        {
            sum+=fib[i];
            if(sum>n)
            {
                sum-=fib[i];
                continue;
            }
            for(int j=i;j>=0;j--)
            {
                sum+=fib[j];
                if(sum>n)
                {
                    sum-=fib[j];
                    continue;
                }
                for(int k=j;k>=0;k--)
                {
                    sum+=fib[k];
                    if(sum==n)
                    {
                        printf("%lld %lld %lld\n",fib[i],fib[j],fib[k]);
                        p=1;
                        break;
                    }
                    sum-=fib[k];
                }
                if(p==1)break;
                sum-=fib[j];
            }
            if(p==1)break;
            sum-=fib[i];
        
        }
        if(p==0)printf("-1\n");
    }
    return 0;
    
}

问题： 1、fib数列开得太大，增加时间开销 2、一定要把数字越界问题牢记心中，绷紧这根弦，这里的关键问题就是sum爆了

对策，①，可以用判断差来代替判断和，②，for循环不必每次从头开始，这样既节省时间又避免数字越界，③，不必维护sum，省去回溯更方便

#include<stdio.h>
typedef long long int i64;
int main(void)
{
    i64 fib[100005]={0};
    fib[0]=0;
    fib[1]=1;
    i64 cnt=2;
    while(fib[cnt-1]+fib[cnt-2]<1000000009)
    {
        fib[cnt++]=fib[cnt-1]+fib[cnt-2];
    }
    i64 t;
    scanf("%lld",&t);
    for(int o=0;o<t;o++)
    {
        i64 n;
        scanf("%lld",&n);
        int p=0;
        for(int i=cnt-1;i>=0;i--)
        {
            if(fib[i]>n)
            {
                continue;
            }
            for(int j=i;j>=0;j--)
            {
                if(fib[i]+fib[j]>n)
                {
                    continue;
                }
                i64 re=n-fib[i]-fib[j];
                for(int k=j;k>=0;k--)
                {
                    if(fib[k]==re)
                    {
                        printf("%lld %lld %lld\n",fib[i],fib[j],fib[k]);
                        p=1;
                        break;
                    }
                }
                if(p==1)break;
            }
            if(p==1)break;
        
        }
        if(p==0)printf("-1\n");
    }
    return 0;
    
}