| 数组求和问题 |
| Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB |
| Total submit users: 92, Accepted users: 80 |
| Problem 11461 : No special judgement |
| Problem description |
给定一个长度为n的数组，从这个数组里面随机从前往后取m个数，使得这m个数的和是S，并且这m个数每相邻的两个数的下标相差为p。
|
| Input |
首先是一个整数t，表示有t组数据，每组数据首先是四个整数，n(1<=n<=100000),m(1<=m<=n),S(0<=S<=10^9),
p(1<=p<=100000)意思如题目描述，接下来一行有n个非负数，都小于10^9，表示数组元素的值。
|
| Output |
对于每组数据，首先输出”case #:”,#从一开始，接下来一个数就输出方案总数。输出格式详见样例。
|
| Sample Input |
3
10 2 5 2
1 2 1 3 1 3 2 2 3 2
5 2 10 1
5 5 5 5 5
6 3 10 2
4 2 4 4 4 4 |
| Sample Output |
case 1:3
case 2:4
case 3:1 |
| Problem Source |
| HUNNU Contest //用一个b数组累加 i这个范围符合要求的数，在1-p这个段b[i]=a[i],然后累加和，最后求出连续m个数的和看是否满足要求。 #include
#include
const int N =100005; __int64 a[N],b[N]; int main() { int t,n,m,p,i,j,ans; __int64 s; scanf("%d",&t); for(i=1;i<=t;i++) { ans=0; memset(b,0,sizeof(b)); scanf("%d%d%I64d%d",&n,&m,&s,&p); for(j=1;j<=n;j++) scanf("%I64d",&a[j]); for(j=1;j<=p;j++) b[i]=a[i]; //这个段 b[i]=只能等于a[i]; for(j=1;j+p<=n;j++) b[j+p]=b[j]+a[j+p]; //累加 和 for(j=1;j+(m-1)*p<=n;j++) //j+（m-1)*p就是从j开始到m-1个数但是减去了b[j]等于把a[j]也减去了，所以加上a[j]构成m个数 { if(b[j+(m-1)*p]-b[j]+a[j]==s) ans++; } printf("Case %d:%d\n",i,ans); } return 0; }
|
|