1230. K倍区间（超级详细，小白入！！！）

news/2024/5/19 22:43:04

输入样例：

输出样例：

这个题看到区间两个字，两眼一瞪可能就和前缀和差分有关

做题思路：

通过记录每个[1,r]区间值的和,看它前面是否出现过一个[1,l](l<=r),使得[l,r]区间的值能除尽k

有同学就好奇，这个双重循环，搞两个指针l,r，直接卡区间不就完了，为啥要左端点都从1开始，因为数据范围不允许O(N^2)的时间复杂度

如下面我的第一次错误代码

#include<iostream>
using namespace std;
const int N=100010;
int n,k,cnt;
long long a[N],f[N];int main()
{cin>>n>>k;for(int i=1;i<=n;i++){cin>>a[i];f[i]=f[i-1]+a[i];}for(int i=0;i<n;i++){for(int j=i+1;j<=n;j++)//j一定严格大于i{if((f[j]-f[i])%k==0)cnt++;}}cout<<cnt;return 0;
}

思路和逻辑没问题，就是太暴力了，导致时间复杂度太高，TLE超时了！/(ㄒoㄒ)/~~

下面是我看一个大佬的，他将两重循环，直接缩减到一层

画个简图也就是这个意思

#include<iostream>
using namespace std;
const int N=100010;
int n,k;
int a[N],f[N],ans[N];//这里面存的是取余后的结果所有定义为int就行
long long cnt;int main()
{cin>>n>>k;for(int i=1;i<=n;i++){cin>>a[i];f[i]=(f[i-1]+a[i])%k;//其实相当于求除每个左端点为第一个元素的前缀和除k的余数//然后如果前面存在余数相同的，说明咱们这个区间减去前面的区间结果为0,说明组合成的新区间可以除尽k//则可以使用排列组合进行两两配对,也就是前面有几个余数相同的，则就可以生成几个k倍区间cnt+=ans[f[i]];ans[f[i]]++;}cout<<cnt+ans[0];//上面算的都是区间，最后要加上单个的，自己就可以除尽k的数(%k为0的数)return 0;
}