首页 > 代码库 > 2017蓝桥杯第十题(k倍区间)

2017蓝桥杯第十题(k倍区间)

 1 #include<iostream>
 2 #include<stdio.h>
 3 using namespace std;
 4 const int N = 10010;
 5 int n,c[N*3],a[N];
 6 int lowbit(int n){
 7   return n&(-n);
 8 }
 9 void change(int k,int pos){
10   while(pos<=n){
11     c[pos]+=k;
12     pos+=lowbit(pos);
13   }
14 }
15 int SUM(int pos){
16   int sum=0;
17   while(pos>0){
18     sum+=c[pos];
19     pos-=lowbit(pos);
20   }
21   return sum;
22 }
23 int QSUM(int begin,int end){
24   return SUM(end)-SUM(begin-1);
25 }
26 int main(){
27   int k;
28   cin>>n>>k;
29   for(int i=1;i<=n;i++){
30     cin>>a[i];
31     change(a[i],i);
32   }
33   int sum=0;
34   for(int i=1;i<=n;i++){
35     for(int j=i;j<=n;j++){
36       if((QSUM(i,j))%k==0){
37         sum++;
38       }
39     }
40   }
41   cout<<sum<<endl;
42 }

大家看看可行不可行  若有错误欢迎指正!!!!

2017-04-09

2017蓝桥杯第十题(k倍区间)