💻 ACM金牌团队🏅️ | 多次AK大厂笔试 ｜ 大厂实习经历

👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸

✨ 合集传送们 -> 🧷学长刷题笔记

🍒 本专栏已收集 140+ 套题 🍄 题面描述等均已改编，如果和你实际看到的题面描述不一样请理解，做法和题目本质基本不变。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力 💞

🍥 本次题目难度不是很大，比较常规

1️⃣ 比较简单的数数题

2️⃣ 前缀和预处理，比较容易想

🍧 01.彩虹糖果工厂

问题描述

LYA 是一家彩虹糖果工厂的老板。工厂生产两种颜色的糖果：红色和蓝色。每天，工厂会生产 个糖果，每个糖果都有一个特定的甜度值。

为了保证产品的多样性，LYA 决定将一个红色糖果和一个蓝色糖果组合成一对，作为一个套装出售。她想知道所有可能的红蓝糖果组合的甜度总和是多少。

甜度总和的计算方法是将每对红蓝糖果的甜度值相乘，然后将所有组合的结果相加。由于结果可能非常大，LYA 只需要知道总和对 取模后的结果。

输入格式

第一行包含一个整数 ，表示糖果的总数。

第二行包含 个整数 ，表示每个糖果的甜度值。

第三行包含一个长度为 的字符串，由 'R' 和 'B' 组成，表示每个糖果的颜色（'R' 表示红色，'B' 表示蓝色）。

输出格式

输出一个整数，表示所有可能的红蓝糖果组合的甜度总和对 取模后的结果。

样例输入

3
1 2 3
RBR

样例输出

8

数据范围

题解

本题的核心思路是利用数学技巧来避免暴力枚举所有组合。我们可以分别计算红色糖果和蓝色糖果的甜度总和，然后利用乘法分配律快速得到结果。具体步骤如下：

1. 遍历所有糖果，分别计算红色和蓝色糖果的甜度总和。
2. 再次遍历糖果，对于每个蓝色糖果，将其甜度与红色糖果的总甜度相乘并累加到结果中。
3. 注意在每一步计算中都要对 取模，以避免溢出。

这种方法的时间复杂度为 ，空间复杂度为 ，能够高效处理大规模数据。

参考代码

• Python

# 读取输入
n = int(input())
sweetness = list(map(int, input().split()))
colors = input()

MOD = 10**9 + 7

# 计算红色糖果的总甜度
red_sum = sum(s for s, c in zip(sweetness, colors) if c == 'R') % MOD

# 计算结果
result = 0
for s, c in zip(sweetness, colors):
    if c == 'B':
        result = (result + s * red_sum) % MOD

print(result)

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取输入
        int n = scanner.nextInt();
        int[] sweetness = new int[n];
        for (int i = 0; i < n; i++) {
            sweetness[i] = scanner.nextInt();
        }
        String colors = scanner.next();
        
        final int MOD = 1000000007;
        
        // 计算红色糖果的总甜度
        long redSum = 0;
        for (int i = 0; i < n; i++) {
            if (colors.charAt(i) == 'R') {
                redSum = (redSum + sweetness[i]) % MOD;
            }
        }
        
        // 计算结果
        long result = 0;
        for (int i = 0; i < n; i++) {
            if (colors.charAt(i) == 'B') {
                result = (result + (long)sweetness[i] * redSum % MOD) % MOD;
            }
        }
        
        System.out.println(result);
    }
}

• Cpp

#include <iostream>
#include <vector>
#include <string>

using namespace std;

const int MOD = 1e9 + 7;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    // 读取糖果甜度
    vector<int> sweetness(n);
    for (int& s : sweetness) {
        cin >> s;
    }
    
    // 读取糖果颜色
    string colors;
    cin >> colors;
    
    // 计算红色糖果的总甜度
    long long red_sum = 0;
    for (in