写点什么

【Python 训练营】Python 每日一练 ---- 第 31 天: k 倍区间

作者:是Dream呀
  • 2022 年 3 月 11 日
  • 本文字数:1453 字

    阅读完需:约 5 分钟

【Python训练营】Python每日一练----第31天: k倍区间

📢📢📢📣📣📣🌻🌻🌻Hello,大家好我叫是 Dream 呀,一个有趣的 Python 博主,多多关照😜😜😜🏅🏅🏅2021 年度博客之星 TOP100,2021 年度博客之星领域 TOP5,Python 领域优质创作者,欢迎大家找我合作学习(文末有 VX 想进学习交流群 or 学习资料 欢迎+++)💕 入门须知:这片乐园从不缺乏天才,努力才是你的最终入场券!🚀🚀🚀💓最后,愿我们都能在看不到的地方闪闪发光,一起加油进步🍺🍺🍺🍉🍉🍉“一万次悲伤,依然会有 Dream,我一直在最温暖的地方等你”,唱的就是我!哈哈哈~🌈🌈🌈🌟🌟🌟✨✨✨


题目描述

资源限制时间限制:2.0s 内存限制:256.0MB 问题描述  给定一个长度为 N 的数列,A1, A2, … AN,如果其中一段连续的子序列 Ai, Ai+1, … Aj(i <= j)之和是 K 的倍数,我们就称这个区间[i, j]是 K 倍区间。


你能求出数列中总共有多少个 K 倍区间吗?输入格式  第一行包含两个整数 N 和 K。(1 <= N, K <= 100000)  以下 N 行每行包含一个整数 Ai。(1 <= Ai <= 100000)输出格式  输出一个整数,代表 K 倍区间的数目。


样例输入5 212345样例输出6
复制代码

解题思路

方法 1: 暴力求解法


  • 暴力法求解,直接将所有情况的值进行求值,看看是否符合题目要求,不过这种方法肯定是会超时的,接下来把源码分享给大家


import osimport sys
# 请在此输入您的代码N, K = map(int,input().split())list1 = []for i in range(N): a = int(input()) list1.append(a)count = 0for i in range(N): for j in range(i,N): a = sum(list1[i:j+1]) if a % K == 0: count += 1print(count)
复制代码


方法二: 数学分析方法


  • 首先我们知道 ( s [ j ] − s [ i − 1 ] ) % k = s [ j ] % k − s [ i − 1 ] % k 所以 ( s [ j ] − s [ i − 1 ] ) % k = 0 就相当于 s [ j ] % k − s [ i − 1 ] % k = 0 也就是 s [ j ] % k = s [ i − 1 ] % k

  • 所以我们可以直接在列表中存储余数出现的次数


拿题目给的例子说:前5项的和是15,15%2=1前两项的和是3,3%2=1前一项的和是1,1%2=1
复制代码


  • 所以这个取余之后值为 1 出现了三次,我们不难看出:我们可以取第五个数 - 第一个数、第五个数 - 第二个数、第二个数 - 第一个数这三种结果说白了,就是在出现的次数 3 里面任选两个,即:C32。

  • 所以说,创建一个列表来存储余数,余数的种类一定和除数一样大,因为还包括 0 在内:s = [0]*k

  • 这里用依次相加余数的方法求解第一项、第一项+第二项、第一项+第二项+第三项.....的余数:temp_sum.append((temp_sum[i - 1] + int(input())) % k) # 求temp_sum[i]即下一项的值

  • 不同的余数出现则进行+1:s[temp_sum[i]] += 1

  • 由数学中的组合排列公式进行求值处理,Cnk 模式:`res += s[i] * (s[i] - 1) // 2

  • 加 s[0]的原因是不用做减法,其本身相除后的余数就是 0,所以直接加进去就可以啦print(res+s[0])

源码分享

n, k = map(int, input().split())s = [0]*k  # 创建一个列表来存储余数,余数的种类一定和除数一样大,因为还包括0在内temp_sum = [0]  # 前缀和取余Kfor i in range(1, n + 1):    # 这里用依次相加余数的方法求解第一项、第一项+第二项、第一项+第二项+第三项.....的余数    temp_sum.append((temp_sum[i - 1] + int(input())) % k)  # 求temp_sum[i]即下一项的值    s[temp_sum[i]] += 1
res = 0for i in range(len(s)): # 由数学中的组合排列公式进行求值处理,Cnk模式 res += s[i] * (s[i] - 1) // 2
print(res+s[0]) # 加s[0]的原因是不用做减法,其本身相除后的余数就是0,所以直接加进去就可以啦
复制代码

学习总结

🏅今天是我在Python训练营的第 31 天,希望每天都能见到最棒的你🏅




用户头像

是Dream呀

关注

Python领域优质创作者 2021.03.30 加入

2021年度博客之星TOP100,2021年度领域TOP5 Python领域优质创作者,交流、合作、学习,欢迎私信我VX+++ 一万次悲伤,依然会有Dream,我一直在最温暖的地方等你!

评论

发布
暂无评论
【Python训练营】Python每日一练----第31天: k倍区间_3 月月更_是Dream呀_InfoQ写作平台