3956. 截断数组

3956. 截断数组 - AcWing题库

 3956. 截断数组

【题目描述】

给定一个长度为 nn 的数组 a1,a2,…,ana1,a2,…,an。

现在，要将该数组从中间截断，得到三个非空子数组。

要求，三个子数组内各元素之和都相等。

请问，共有多少种不同的截断方法？

【输入】

第一行包含整数 nn。

第二行包含 nn 个整数 a1,a2,…,ana1,a2,…,an。

【输入】

输出一个整数，表示截断方法数量。

数据范围

前六个测试点满足 1≤n≤10；1≤n≤10。
所有测试点满足 1≤n≤；1≤n≤，−10000≤≤10000；−10000≤≤10000。

解题思路：

因为题意是由一个不变的数组，截成三段，所以这个数组的总和 sum 是相等的，其中截成的三段的值要都相等，那么这三段应该截成的三段它们的和应该满足： sum1==sum2==sum3==sum/3 .首先想到的是用前缀和，后缀和，因为要判断的情况太多了，刚开始是这么写的：

大概是先判断前缀和到达 sum1==sum/3 的时候就判断后缀和，但是会有漏掉的情况，因为 i 层的循环是一直自增的，判断完第一段满足要求后，接着要遍历后一段满足要求的区域，此时可以用数组来存储后一段满足条件的 sum3==sum 的部分（数据过大时可能会重复计算很多遍），而且还要保证统计出来的数量没有重复的部分。

一直在改的错误代码：

#include<stdio.h>
int a[100005],book[100005];
int main(){int n,sum=0;scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d",&a[i]);sum=sum+a[i];}int x=sum/3;if(sum%3!=0){printf("0\n");return 0;}int S=0;int sum1=0,sum2=0;int k=n-1,i,j;for(i=0;i<n;i++){sum1=sum1+a[i];if(sum1==x){for(k=n-1;k>i+1;k--){if(sum2==x){S++;book[k]=1;}sum2=sum2+a[k];n--;if(book[k]==0&&sum2==x){S++;book[k]=0;}}}} printf("%d\n",S);return 0;
} 

然后，看到题解，写的很简单。（sum 是数组的总和）

他的思路是记录前缀和（sum1）中满足 sum1==sum/3 的部分（也就是第一次截断的点）以及满足 sum1==sum/3*2 的部分（第二次截断的点）。

数据有些大，要开 long long 存储。

#include<stdio.h>
int a[100005];
int main(){int n,x,sum=0;scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d",&a[i]);sum=sum+a[i];}x=sum/3;long long S=0,ans=0;long long flag=0;if(sum%3!=0||n<3){printf("0\n");return 0;}for(int i=0;i<n-1;i++){//第二次截断后，第三个位置不能为空 S=S+a[i];if(S==2*x)ans=ans+flag;if(S==x)flag++;}printf("%lld\n",ans);return 0; 
}

795.前缀和

代码如下：

#include<stdio.h>
int sum[100005];
int main(){int a,b,x,n,m;scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){scanf("%d",&x);sum[i]=sum[i-1]+x;} for(int i=0;i<m;i++){scanf("%d%d",&a,&b);printf("%d\n",sum[b]-sum[a-1]);}return 0;
}

796.子矩阵的和

 代码如下：

#include<stdio.h>
int a[1005][1005],sum[1005][1005];
int main(){int x,y,z,w,i,j,n,m,k;scanf("%d%d%d",&n,&m,&k);for(i=1;i<=n;i++){for(j=1;j<=m;j++){scanf("%d",&a[i][j]);}}for(i=1;i<=n;i++){for(j=1;j<=m;j++){sum[i][j]=a[i][j]+sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1];}}for(i=0;i<k;i++){scanf("%d%d%d%d",&x,&y,&z,&w);printf("%d\n",sum[z][w]-sum[x-1][w]-sum[z][y-1]+sum[x-1][y-1]);}
}