我要招人

去企业版

首页 > 试题广场 >

多多的求和计算

[编程题]多多的求和计算

热度指数：8693 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

多多路上从左到右有N棵树（编号1～N），其中第i个颗树有和谐值Ai。

多多鸡认为，如果一段连续的树，它们的和谐值之和可以被M整除，那么这个区间整体看起来就是和谐的。
现在多多鸡想请你帮忙计算一下，满足和谐条件的区间的数量。

输入描述:

第一行，有2个整数N和M，表示树的数量以及计算和谐值的参数。
（ 1 <= N <= 100,000, 1 <= M <= 100  ）
第二行，有N个整数Ai, 分别表示第i个颗树的和谐值。
（ 0 <= Ai <= 1,000,000,000 ）

输出描述:

共1行，每行1个整数，表示满足整体是和谐的区间的数量。

示例1

输入

5 2
1 2 3 4 5

输出

说明

长度为1: [2], [4]
长度为2: 无
长度为3: [1,2,3], [3,4,5]
长度为4: [1,2,3,4], [2,3,4,5]
长度为5: 无
共6个区间的和谐值之和可以被2整除。

备注:

对于50%的数据，有N<=1,000
对于100%的数据，有N<=100,000

算法知识视频讲解

Java

物理魔法使

动态规划:

import java.util.*;
import java.io.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNextInt()) { // 注意 while 处理多个 case
int N = in.nextInt();
int M = in.nextInt(); in.nextLine();
// BufferedWriter wirter = new BufferedWriter(new OutputStreamWriter(System.out));
String[] itt = in.nextLine().split(" ");
int[] dend = new int[N+1];

long res =0L;
for(int idx=N-1;idx>=0;idx--){
int mod=0;
for(int jdx=idx;jdx<N;jdx++){
mod=(mod+Integer.parseInt(itt[jdx]))%M;
if(mod==0){
dend[idx]=1+dend[jdx+1];
break;
}
}
res+=dend[idx];
}
System.out.println(res);
}
}

}

编辑于 2024-03-14 23:21:16 回复(0)

Java

瓜子儿。

O(n2)算法

区间的长度范围为[1,arr.length]。对于每个区间长度，遍历数组判断区间是否满足条件

private static int f(int[] arr,int mod){
    int n = arr.length,count=0;
    
    //c代表区间长度
    for(int c=1;c<=n;c++){
    
        //区间开始结束值以及区间和的大小
        int end=0,start=0;
        long sum=0;
        while (end<c-1){
            sum+=arr[end++];
        }
        
        //从左到右“滑动区间”并计算是否满足条件
        while (end<n){
            sum+=arr[end++];
            if(sum%mod==0){
                count++;
            }
            sum-=arr[start++];
        }
    }
    return count;
}

复杂度为O(n2)，只过了60%测试用例就超时了：

如何优化？

前缀和

假设有prefix[]数组，那么sum[i,j]就等于prefix[j]-prefix[i-1]

那么如果按照上面的框架，代码会变成：

private static int f(int[] arr,int mod){
    long[] prefix=new long[arr.length+1];
    int k=1;
    for(int i : arr){
        prefix[k]=prefix[k-1]+i;
        k++;
    }

    int n = arr.length,count=0;
    for(int c=1;c<=n;c++){
        int start=0;
        int end = start+c-1;
        if(end<n){
            while(end<n){
                if((prefix[end+1]-prefix[start])%mod==0){
                    count++;
                }
                start++;end++;
            }
        }else {
            break;
        }
    }
    return count;
}

复杂度还是O(n2)==仍然过不了

做卷的时候我就思考到了这一步==因为数组并不有序并不为等差，我认为前缀和优化没有用就没做了==

前缀和直接取模

==感觉不可能想得到==反正不看答案我是没想到==

核心公式：

据此，我们可以计算所有prefix[i]%m的值，以该值作为key(表达式的x)，value为所有满足prefix[i]%m==x的prefix的个数。

这样，可以确保，每个key下面任何两个前缀和取出来计算得到的区间都满足要求（即右侧表达式）

debug--要用long才行

private static long f(int[] arr,int mod){
    long[] prefix=new long[arr.length];
    prefix[0]=arr[0];
    Map<Long,Long> map = new HashMap<>();
    map.put(prefix[0]%mod,1L);
    for(int i=1;i<arr.length;i++){
        prefix[i]=prefix[i-1]+arr[i];
        map.put(prefix[i]%mod,map.getOrDefault(prefix[i]%mod,0L)+1);
    }
    return map.values().stream().mapToLong(n->n*(n-1)/2).sum()
        +map.getOrDefault(0L,0L);
    //需要加上单值区间直接可以mod到0的情况
}

复杂度O(n)，啪的一下就完了

发表于 2022-07-24 10:49:47 回复(2)

Java

牛客300774646号

import java.util.*;
public class Main{
      public static void main(String[] args){
      Scanner scanner = new Scanner(System.in);
      int N = scanner.nextInt();
      int M = scanner.nextInt();
int [] array=new int [N];//记录前缀和
array[0]=scanner.nextInt()%M;
for(int i=1;i<N;i++){
array[i]=scanner.nextInt();
array[i]=(array[i-1]%M+array[i])%M;
}
int mod=0;
int count=0;
HashMap<Integer,Integer> imap=new HashMap<>();
imap.put(0,1);
for(int i=0;i<N;i++){

if(imap.containsKey(array[i])){
int num=imap.get(array[i]);
count+=num;
imap.put(array[i],num+1);
}
else imap.put(array[i],1);


}System.out.println(count);}}

//为什么会输出负数