复赛3:求和

洛谷:P2671

方法一:暴力(40分)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using namespace std;
int a[100005],b[100005];
int main(){
   int c,d,sum=0;
   cin>>c>>d;
   for (int i = 1; i <=c; i++){
    cin>>a[i];
   }
   for (int i = 1; i <=c; i++){
    cin>>b[i];
   }
   
   for (int i = 1; i <=c; i++){
      for (int j = i+2; j <=c; j+=2){
        if(b[i]==b[j])
        sum=sum+(i+j)*(a[i]+a[j]);
       if(sum>10007)sum=sum%10007;
      }
       
   }
   cout<<sum%10007;
}

方法二:分组合并(100分)

把每个颜色分为一组,再在每个颜色中按奇偶分组,所以一共有2m组,事先把各组的和都计算好。然后乘。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>

using namespace std;
int a[100005],color[100005];
int sum_color[100005][2], sum_color_number[100005][2]; 
//两维数组[2]主要是区别同一颜色的奇偶两种情况
int main(){
   int n,m,ans=0;
   cin>>n>>m; //m没什么用
   for (int i = 1; i <=n; i++){
    cin>>a[i];
   }
   for (int i = 1; i <=n; i++){
    cin>>color[i];
    sum_color[color[i]][i%2]++;//求color在奇数和偶数下的和
    sum_color_number[color[i]][i%2]=(sum_color_number[color[i]][i%2]+a[i])%10007;
   }
   
   for (int i = 1; i <=n; i++){
      ans=(ans+i*((sum_color[color[i]][i%2]-2)*a[i]%10007+sum_color_number[color[i]][i%2]))%10007;
      //依次然后代入,注意,也要mod10007
      //a[i]应该乘本种颜色(或奇或偶)对应number[i]的数量,即sum_color[color[i][i%2]]-1,
      //因为sum_color_number[color[i][i%2]]已经有一个了,所以是a[i]*(sum_color[color[i]][i%2]-2)
      }
       

   cout<<ans;
}
Scroll to Top