天猫淘宝优惠券网站怎么做,wordpress强大之处,产品vi设计哪家好,企业建设网站的重要性题目 输入样例#xff1a;
5 2
1
2
3
4
5输出样例#xff1a;
6 思路
本题默认所有读者已经理解了如何求前缀和。 可以利用双层循环分别枚举左端点和右端点即可枚举完所有区间#xff0c;而对于每个区间#xff0c;利用一维前缀和判断它是否是一个k倍区间#xff0c;是…题目 输入样例
5 2
1
2
3
4
5输出样例
6 思路
本题默认所有读者已经理解了如何求前缀和。 可以利用双层循环分别枚举左端点和右端点即可枚举完所有区间而对于每个区间利用一维前缀和判断它是否是一个k倍区间是的话答案数1但时间复杂度为O(10^10)超时。代码如下
//s[]为前缀和数组, res 为总区间数
for (int r 1; r n; r )
for (int l 1; l r; l )
{if ((s[r] - s[l - 1]) % k 0)res ;
}实际上这个双层循环可以理解为在右端点r固定l 在 0 ~ r - 1 之间变化的情况下可以找到多少个满足 (s[r] - s[l]) % k 0的区间判断条件变换一下得(s[r] % k - s[l] % k) % k 0即在 0 ~ r - 1 之间能找到有多少个s[l] % k 等于 s[r] % k使得[l, r]构成k倍区间。而 s[r] % k的个数可以在r从前往后遍历过程中用一个数组cnt统计出来cnt[i]代表 s[r]%k余数等于i的个数。 特别注意当s[i] % k 等于0时说明s[i]本身即可构成一个k倍区间因此cnt[0]要预置为1这样当遇到第一个s[i] % k0时就可以统计到答案res中去了。 代码
#includebits/stdc.h
using namespace std;
typedef long long LL;
const int N 1e5 10;
LL a[N], cnt[N];int main()
{ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int n, k;cin n k;//求前缀和for (int i 1; i n; i ){cin a[i];a[i] a[i - 1];}LL res 0;cnt[0] 1;for (int i 1; i n; i ){res cnt[a[i] % k] ;}cout res;return 0;
}
