2022-6-22 真题练习-前缀和

MT19 K 的倍数    校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。

描述

序列中任意个连续的元素组成的子序列称为该序列的子串。 现在给你一个序列 P 和一个整数 K ，询问元素和是 K 的倍数的子串的最大长度。

比如序列 [1,2,3,4,5]，给定的整数 K 为 5，其中满足条件的子串为 {5}、{2,3}、{1,2,3,4}、{1,2,3,4,5} ，

那么答案就为 5，因为最长的子串为 {1,2,3,4,5} ; 如果满足条件的子串不存在，就输出 0。   数据范围： 1 \le n \le 10^5 \1≤n≤105  ， 0 \le p_i \le 10^5 \0≤pi?≤105  ， 1 \le K \le 10^5 \1≤K≤105 

输入描述：

第一行包含一个整数N, 1 ≤ ?? ≤ 105。

第二行包含 N 个整数????，????表示序列P第i个元素的值。0 ≤ ???? ≤ 105。第三行包含一个整数K，1 ≤ ?? ≤ 105。

输出描述：

输出一个整数ANS，表示答案。

 1 import java.util.*;
 2 public class Main{
 3 
 4     public static void main(String[] args) {
 5         Scanner sc = new Scanner(System.in);
 6         int n = sc.nextInt();
 7         long s=0;
 8         long[] sum=new long[n+1];
 9         for (int i=1;i<=n;i++){
10             int t=sc.nextInt();
11             s+=t;
12             sum[i]=s;
13         }
14         int k=sc.nextInt();
15         int ans=0;
16         //System.out.println(s);
17         for (int i=n;i>=1;i--){
18             if (i<=ans) break;
19             for (int j=0;j){
20                 if (i-j<=ans) break;
21                 if ((sum[i]-sum[j])%k==0) ans=Math.max(ans,i-j);
22             }
23         }
24         System.out.println(ans);
25     }
26 
27 }

思路：记录前缀和可以快速计算子串和，剪枝穷举，小于当前长度的直接跳过。