蓝桥杯K倍区间问题详解（Python解法）

目录

题目描述

输入描述

输出描述

输入输出样例

运行限制

解题思路

方法一：暴力法（超时）

方法二：前缀和+暴力法（超时）

方法三：前缀和+哈希表法

总结

题目描述

输入描述

输出描述

输出一个整数，代表 K 倍区间的数目。

输入输出样例

输入：

5 2
1
2
3
4
5

输出：

6

运行限制

最大运行时间：2s

最大运行内存: 256M

解题思路

方法一：暴力法（超时）

        题目要求“k倍区间”，最简单粗暴的方法依然是暴力法：将长度为 N 的数列的所有子序列全部枚举出来，逐个判断是否满足条件，若满足条件，则计数加 1，最终求得“k倍区间的个数”。

# 方法一：暴力法
# 读入数据
N, K = map(int, input().split())

list_num = []
count = 0
for i in range(N):
    list_num.append(int(input()))

# 枚举所有子序列
for i in range(N):
    for j in range(i, N):
        if sum(list_num[i:j+1]) % K == 0:
            count += 1

print(count)

作者：歪歪不想敲damn码