涨姿势题1

TimeLimit:1000MS  MemoryLimit:128000KB 64-bit integer IO format: %lld   涨姿势题就是所谓的优化题，在组队赛中，队伍发现了一题水题，那么应该交给谁去处理？作为处理水题的代码手，应该具备什么样的素养？ 1，要快，水题拼的就是速度！ 2，不能卡水题！水题都卡，绝对不是一个代码手的风范！ 3，不能出错，错一次即罚时20分钟，对于水题来讲是致命的！ 4，要能看出来一题是水题！没有这条，上面三条都是没有意义的！ 如果你希望你成团队中一个合格的代码手，那么这套题是你最好的选择，快AC吧！ 本系列即是为了提高水题代码手的素养而准备的！水题经常需要用到简单的优化，中难题的解题过程中也经常需要各种优化，优化是处理超时的首要选择，目的是降低时间复杂度。 涨姿势题为3题，题面完全相同，仅数据范围不同，请根据不同的数据范围选择合适的算法。 题目描述： 给定数列a[1] a[2] ... a[n] 多次询问 每次询问 有一个数字 qi 求有多少组(l,r)满足 f(l,r)=a[l]+a[l+1]+...+a[r]=qi   输入要求： 第一行是一个t表示测试数据的组数。 每组数据的第一行是两个整数n、q，分别表示数组长度和询问的次数 第二行是n个整数a[1],a[2],...,a[n]。 接下来是q行，每行一个整数qi表示第i次询问。 数据范围： 第1题：t<=130，1<=n<=1000，-10^9<=ai<=10^9，-10^12<=qi<=10^12，大数据不超过一半，每组大数据的q为1或2。 第2题：t<=130，1<=n<=10000，q<=50，1<=ai<=10^9，1<=qi<=10^12，大数据不超过一半。 第3题：t<=30，1<=n<=1000，q<=1000000，-10^6<=ai<=10^6，-10^6<=qi<=10^6，大数据不超过5组。 注意认真比较每题的每个数的数据范围，然后选择合适的算法AC吧。注意不要提交错题目了。   输出要求： 对于每个询问，输出一个整数表示答案 SampleInput 1 5 6 4 5 6 5 4 4 11 1 20 6 10 SampleOutput 2 2 0 2 1 0思路：由题目可以知道，这题是一题要我们优化处理的题目，怎么优化处理呢：就是将数据转变成方便计算的形式。在这题里我们要求的是有多少个子序列总和等于特定数M，如果每次都用for来加未免太麻烦了，要是可以很快就得出答案就好了。于是我们将sum作为一个数组用来存储我们输入数每一项a（因为已经有一个存储数组sum存在，所以a[]的存在是多余的，可以直接替换常数）的前n项和，如sum[1]=a,sum[2]=sum[1]+a,这个样子，我们就可以简单的用枚举求每一个区间的大小了；这里呈上代码 for(i=1; i<=n; i++)//注意要由1开始 { scanf("%lld", &a); s[i]=s[i-1]+a; }

之后再暴力的遍历就可以了；

转载于:https://www.cnblogs.com/DCD112358/p/6341361.html

相关资源：JAVA上百实例源码以及开源项目