题目描述
芸如是一位天才科学家, 为中国阵营效力. 她有着出众的才智, 在几年的军旅生活中, 芸如研制了许多高科技武器, 使得中国军队的武备可以与厄普西隆阵营狡猾的研究成果相抗衡, 甚至还可以和整个盟军部队分庭抗礼.
芸如很小的时候就已经开始展现自己的才华, 并作为最优秀的幼儿被送往保密培训学校. 在她入校的第一天, 校长决定亲自考一考这位被外界奉为 "天才" 的小姑娘.
校长的问题是这样的:
在一个长度为 N 的数字序列 A, 有 Q 组询问, 每组询问给定 l 和 r:l≤r, 请求出 A[l]+A[l+1]+...+A[r] 的值.
由于这个结果可能很大, 最终的结果要对 10007 取模 (即取余数).
输入
多组数据输入, 数据组数不超过 10.
第一行是一个数字 N,Q, 表示序列 A 中元素的个数和询问组数.(0<N,Q≤1e6)
第二行是 N 个整数, 第 i 个整数 A[i] 表示序列 A 中的第 i 个元素, 保证均为非负整数, 且在 INT 范围内.
接下来 Q 行, 每行是两个用空格分隔的整数 l 和 r(保证 l 和 r 不会超出序列 A 下标的范围, 且 l≤r).
注意序列 A 的下标从 1 开始.
输出
对于每组数据, 每个询问输出一行, 为和值.
输入样例
3 1
1 2 3
1 2
输出样例
3
特别说明
对 20% 的数据, N,Q≤100
数据量较大, 读入请勿用过慢读入方式. 该类提示以后上机将不再出现, 请大家多总结相关经验
思路
本题需要用到前缀和的想法. 不知道前缀和的同学请自行百度.
本题为一个很简单的多次查询区间和问题, 只要利用前缀和数组, 在读入数据的时候利用一个 sum 数组对数字累次进行加和, 在查询对应区间的和值的时候, 进行 sum 数组的相减就可以了.
本题需要特别注意的是取模问题. 今后取模都请使用形如 "(a+mod)%mod" 的形式来代替 "a%mod".
参考代码
- #include<stdio.h>
- #define MAXN 1000002
- #define Mod 10007
- int a[MAXN];
- int main()
- {
- int N,Q;//N: 元素个数; Q: 询问组数
- while(scanf("%d%d",&N,&Q) != EOF){
- int i;
- // 输入 + 前缀和数组预处理
- a[0] = 0;
- for(i = 1;i <= N;i++){
- int tmp;
- scanf("%d",&tmp);
- tmp %= Mod;
- a[i] = (tmp + a[i-1])%Mod;
- }
- // 读入查询范围
- for(i = 0;i < Q;i++){
- int l,r;
- scanf("%d%d",&l,&r);
- printf("%d\n",(a[r]-a[l-1]+Mod)%Mod);
- }
- }
- }
来源: http://www.bubuko.com/infodetail-2893751.html