桥头做网站,小程序源码网网盘,如何取消危险网站提示,建设证件查询官方网站题目描述
给定一个长度为N的数列#xff0c;A1, A2, … AN#xff0c;如果其中一段连续的子序列Ai, Ai1, … Aj(i j)之和是K的倍数#xff0c;我们就称这个区间[i, j]是K倍区间。
你能求出数列中总共有多少个K倍区间吗#xff1f;
输入#xff1a; 第一行包含两个…题目描述
给定一个长度为N的数列A1, A2, … AN如果其中一段连续的子序列Ai, Ai1, … Aj(i j)之和是K的倍数我们就称这个区间[i, j]是K倍区间。
你能求出数列中总共有多少个K倍区间吗
输入 第一行包含两个整数N和K。(1 N, K 100000) 以下N行每行包含一个整数Ai。(1 Ai 100000)
输出
输出一个整数代表K倍区间的数目。
例如
输入
5 2
1
2
3
4
5程序应该输出
6代码
import java.util.Scanner; /** * author Fancier * version 1.0 * description: k倍区间 * date 2024/3/8 9:31 */
public class Main {public static void main(String[] args) {Scanner scanner new Scanner(System.in);int n scanner.nextInt(), k scanner.nextInt();long res 0;int[] arr new int[n 1];long[] counts new long[k];counts[0] 1;for (int i 1; i n; i) {arr[i] arr[i - 1] scanner.nextInt();arr[i] % k;}for (int i 1; i n; i) {res counts[arr[i]];}System.out.println(res);}
}题解
这道题很容易让人联想到前缀和, 但它并不是求最大区间和, 而是要求区间和能被k整除的区间个数 所以复杂度还会是2次方 仔细研究 符合条件的区间(i, j)的 测试公式: (sum[j] - sum[i - 1]) % k 0 会发现 其可以转变为 sum[i] % k sum[j] % k 这样我们就可以用到dp的思想, 再得到前缀和数组后再遍历其一遍 每次遍历需要直到当前下标前有多少与其值 % k 相同值的个数 就可以知道新增了几个这样的区间了 这一轮遍历下来就得到了最终答案 (值得注意得是 0 % k 0, 所以需要考虑小标)
细节问题
counts数组的初始化 counts[0] 1如果用最终结果用int存, 遇到大的测试数据会爆掉, 所以用long存arr数组只需要保存余数即可, 如果存总和用long也会爆掉 具体代码参上
好的!本次分享到这就结束了 如果对铁汁你有帮助的话记得点赞收藏⭐️关注➕ 我在这先行拜谢了
