B3878 [信息与未来 2015] 连续数的和 题解

· · 题解

这道题做法比较多，我这里讲两种。

第一种

我们会发现这道题数据较小，所以考虑暴力。

暴力就是枚举每个数，然后把这连续 k 个数相加，最后判断一下就行了。但是如果全是暴力的话时间复杂度就有点高了，所以我们在这个连续数的和上面考虑优化。

都知道高斯求和吧。用高斯求和来优化最适合不过了。我们首先求出两头的数，然后高斯求和。最后判断就行了。

讲的简短，代码一样简短。

#include <bits/stdc++.h>
using namespace std;
long long n, k;
long long ans, sum;
bool check(int n){
    for(int i=1;i*i<=n;i++)
        if(i*i==n) return 1;
    return 0;
}
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        sum=(i+i+k-1)*k/2;
        if(check(sum)) ans++;
    }
    cout<<ans<<endl;
    return 0;
}

你会发现上面的代码没有加注释。因为他只有九十分。

那么为什么呢？

我们会发现，如果用高斯求和的话会有一个弊端。就是如果你的前面没有 k 个数了，他依旧会计算，就是往前延伸，然后相加。所以我们不能枚举每个数。如果前面没有 k 个数了，我们就不枚举了。其实就是枚举到 n-k。

现在才算讲完第一个思路。

#include <bits/stdc++.h>
using namespace std;
long long n, k;
long long ans, sum;
bool check(int n){//判断是否成立的函数
    for(int i=1;i*i<=n;i++)//枚举
        if(i*i==n) return 1;//如果是完全平方数，就返回是
    return 0;//不成立，返回否
}
int main(){
    cin>>n>>k;//输入
    for(int i=1;i<=n-k;i++){//枚举到 n-k 就不能往后枚举了
        sum=(i+i+k-1)*k/2;//高斯求和
        if(check(sum)) ans++;//判断是否成立，如果成立就将答案加一
    }
    cout<<ans<<endl;//输出答案
    return 0;//结束程序
}

第二种

第二种的时间复杂度比第一种要强上不少。

我们需要用一个sqrt函数，这个函数就是开平方。

然后会发现，如果不是完全平方数，他就会返回一个小数，我们用一个int类型的数来信存储，这样他就会改变这个数值。然后再把这个数乘上这个数，判断是不是原来的数就行了。

别忘了那个坑。

#include <bits/stdc++.h>//万能头文件
using namespace std;
long long n, k;
long long ans, sum;
int main(){
    cin>>n>>k;
    for(int i=1;i<=n-k;i++){//枚举
        sum=(i+i+k-1)*k/2;//高斯求和
        int t=sqrt(sum);
        if(t*t==sum) ans++;//如果成立，答案加一
    }
    cout<<ans<<endl;//输出答案
    return 0;//结束程序
}

尾

这道题比较好理解的两种思路，大家都要掌握。再见！