宁波市建设银行网站/台湾搜索引擎

目录

前缀和模板

！3956. 截断数组 - 前缀和+枚举 

---

前缀和模板

活动 - AcWing

import java.util.*;class Main
{static int N=100010;static int[] a=new int[N],s=new int[N];public static void main(String[] args){Scanner sc=new Scanner(System.in);int n=sc.nextInt(),t=sc.nextInt();for(int i=1;i<=n;i++){a[i]=sc.nextInt();s[i]=s[i-1]+a[i];}while(t-->0){int l=sc.nextInt(),r=sc.nextInt();System.out.println(s[r]-s[l-1]);}}
}

！3956. 截断数组 - 前缀和+枚举 

3956. 截断数组 - AcWing题库

题目：

一个数组切两刀，有三段，每段总和相等，问有多少种切法？

思路：

三段相等，则每段是sum/3，记作avg

如果总和sum不是avg的倍数，则不可能被平均分为3段

剩下的情况就是必然能分成3段，每段总和相等：

我们可以枚举第二刀的位置，枚举每种第二刀位置j时，对应有cnt种第一刀的切法

res累加这些情况即可

• 因为要分成3段，则第二刀之前至少要留2个元素给第一段和第二段，所以枚举第二段的位置i从3开始
• 先记录第一段的和==avg的个数
• 如果此时对应的第三段和==avg，则res累加

import java.util.*;public class Main {static int N = 100010;static int[] s = new int[N];static int n,m;public static void main(String[] sss) {Scanner sc = new Scanner(System.in);n = sc.nextInt();for(int i=1;i<=n;i++) {s[i]=sc.nextInt();s[i]+=s[i-1];}if(s[n]%3!=0) {System.out.println(0);return ;}int avg=s[n]/3;//均值long res=0;long cnt=0;//记录第一刀的位置for(int i=3;i<=n;i++) //只要把第一段和第三段确定下来 就完成了题目{if(s[i-2]==avg) cnt++; //满足第一段==avg的个数 也就是合法的第一刀位置的个数if(s[n]-s[i-1]==avg) res+=cnt; //如果第三段和==avg 说明这个第二刀可以对应之前所有出现过的合法的第一刀}System.out.println(res);}
}