蓝桥杯-k倍区间

用户10271432

发布于 2023-03-20 10:47:59

1740

发布于 2023-03-20 10:47:59

文章被收录于专栏：机器学习-大数据

题目描述：

已知一个数组中的所有数据，已知数组的长度为n,已知一个除数为k。要求我们从这组数据中找到这样的区间，其中所有的元素之和能够被k整除。最终统计出所有的区间数目

输入描述：

第一行：

n,k表示数组的长度，和除数k

第二行及后面的n+1行：

每行一个数字，表示初始数组中的所有元素的数据

输出描述：

输出满足上述条件（区间中所有元素的和可以整除k）所有区间数

样例输入输出：

样例输入:

5 2

样例输出：

算法：

最开始暴力解法，当然是没有通过所有案例

import os
import sys
n,k = map(int,input().split())
ans = []
for i in  range(n):
    a = int(input())
    ans.append(a)
cnt = 0
for l in range(1,n+1):
    for i in range(n-l+1):
        res = sum(ans[i:i+l])
        if res%k==0:
            cnt+=1
print(cnt)

利用前缀和的思想，和一些数学的思维的AC代码

import os
import sys
#前缀和、优化
n,k = map(int,input().split())
cnt = [0]*(k)
ans = 0
for i in range(n):
    a = int(input())
    ans+=a
    cnt[ans%k]+=1
##print(cnt[0],cnt[1])
ans = cnt[0]
for i in range(k):
    ans+=(cnt[i]*(cnt[i]-1))//2
print(ans)

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2023-03-19，如有侵权请联系 cloudcommunity@tencent.com 删除

数学