复赛三：求和

 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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

/**************************************************************** 
 * Description:  2015_J_semi_3  求和   得分：40分
 * Author: Alex Li
 * Date: 2023-10-30 11:48:33
 * LastEditTime: 2024-09-18 17:20:02
****************************************************************/

#include <iostream>
using namespace std;

// 定义数组 a 和 b，分别存储每个格子上的数字 number_i 和颜色 color_i
int a[100005], b[100005];

int main() {
    int c, d, sum = 0;
    cin >> c >> d; // 读取纸带上格子的个数 n（c）和颜色种类数 m（d）
    
    // 读取每个格子上写的数字 number_i，存入数组 a
    for (int i = 1; i <= c; i++) {
        cin >> a[i];
    }

    // 读取每个格子上的颜色 color_i，存入数组 b
    for (int i = 1; i <= c; i++) {
        cin >> b[i];
    }
    
    // 枚举所有可能的 x 和 z，满足 x < z，且 z - x 为偶数
    for (int i = 1; i <= c; i++) { // 遍历 x
        for (int j = i + 2; j <= c; j += 2) { // 遍历 z，z 从 i+2 开始，步长为 2，保证 z - x 为偶数
            // 计算 y = (x + z) / 2，y 一定是整数，且满足 x < y < z
            // 判断颜色是否相同，即 color_x == color_z
            if (b[i] == b[j])
                // 计算当前三元组的分数并累加到 sum
                sum = sum + (i + j) * (a[i] + a[j]);
            // 为防止 sum 超过 10007，进行取模运算
            if (sum > 10007) sum = sum % 10007;
        }
    }
    
    // 输出结果，对 sum 再取模 10007
    cout << sum % 10007;
}

 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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

/**************************************************************** 
 * Description: 2015_J  复赛第三题，求和  满分
 * Author: Alex Li
 * Date: 2023-10-30 14:51:02
 * LastEditTime: 2024-09-18 18:13:18
****************************************************************/
#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; // 读取格子数 n，颜色种类数 m（在本程序中 m 实际未被使用）

    // 读取每个格子上的数字 number_i，存入数组 a
    for (int i = 1; i <= n; i++){
        cin >> a[i];
    }

    // 读取每个格子的颜色 color_i，存入数组 color
    // 并统计同一种颜色在奇数和偶数位置上的数量和数字之和
    for (int i = 1; i <= n; i++){
        cin >> color[i];

        // sum_color[c][p] 统计颜色为 c，位置奇偶性为 p（p=0 表示偶数，p=1 表示奇数）的格子数量
        sum_color[color[i]][i % 2]++;
        
        // sum_color_number[c][p] 统计颜色为 c，位置奇偶性为 p 的数字之和
        sum_color_number[color[i]][i % 2] = (sum_color_number[color[i]][i % 2] + a[i]) % 10007;
    }
    
    // 计算答案
    for (int i = 1; i <= n; i++){
        // 对于位置 i，我们计算其对答案的贡献
        // 只考虑与位置 i 具有相同颜色和奇偶性的格子，因为只有它们才能形成合法的三元组

        // 计算与位置 i 具有相同颜色和奇偶性的格子数量，减去自身
        int count = sum_color[color[i]][i % 2] - 1;

        // 计算这些格子上数字的总和，减去自身的数字 a[i]
        int sum_numbers = (sum_color_number[color[i]][i % 2] - a[i] + 10007) % 10007;

        // 位置 i 对答案的贡献为：
        // ans += i * ((count * a[i] * 2) % 10007 + sum_numbers)
        // 其中：
        // - count * a[i] * 2 表示位置 i 与其他格子的组合对答案的贡献
        // - sum_numbers 表示其他格子的数字对答案的贡献

        ans = (ans + i * ((count * a[i] * 2 % 10007 + sum_numbers) % 10007)) % 10007;
    }

    // 输出结果
    cout << ans;
}