宝石项链问题解析

问题理解

我们需要计算宝石项链的美丽值，对于每种颜色的宝石：

• 美丽值 = 颜色值 × 所有该颜色宝石编号的异或和
• 总美丽值 = 所有颜色美丽值的总和

关键概念

异或运算（XOR）：

• 符号：$\oplus$
• 性质：相同为0，不同为1
• 连续异或：$a \oplus b \oplus c \oplus ...$

算法思路

1. 按颜色分组：使用哈希表（unordered_map）将相同颜色的宝石编号进行异或累积
2. 计算美丽值：对于每种颜色，用颜色值乘以编号的异或和
3. 求和：将所有颜色的美丽值相加

代码实现

#include<bits/stdc++.h>  // 包含常用标准库
using namespace std;

int main(){
    int n;  // 宝石数量
    cin >> n;  // 读取宝石数量
    
    // 使用哈希表存储每种颜色的编号异或和
    // key: 颜色值, value: 该颜色所有宝石编号的异或结果
    unordered_map<int, int> m;
    
    // 读取每个宝石的颜色并处理（编号从1开始）
    for(int i = 1; i <= n; i++) {
        int a;  // 当前宝石的颜色
        cin >> a;  // 读取颜色值
        
        // 将当前编号i异或到该颜色的累积值中
        m[a] ^= i;
    }
    
    long long s = 0;  // 总美丽值，使用long long防止溢出
    
    // 遍历哈希表中的所有颜色
    for(auto& [c, x] : m) {
        // 计算该颜色的美丽值并累加：颜色值c × 编号异或和x
        s += 1LL * c * x;  // 1LL确保使用long long类型计算
    }
    
    cout << s;  // 输出总美丽值
    return 0;
}

算法分析

1. 时间复杂度：$O(n)$
   • 读取和处理 $n$ 个宝石：$O(n)$
   • 遍历哈希表：最坏情况 $O(n)$，平均 $O(n)$
2. 空间复杂度：$O(n)$
   • 哈希表最多存储 $n$ 个键值对

数学解释

对于颜色 $c$，假设有 $k$ 个宝石，编号分别为 $i_1, i_2, ..., i_k$，则：

• 异或和：$x = i_1 \oplus i_2 \oplus ... \oplus i_k$
• 美丽值：$c \times x$

总美丽值：$\sum_{\text{所有颜色 } c} (c \times (\oplus_{i \in \text{颜色c的宝石}} i))$

样例验证

输入：6 和 3 6 3 6 6 3

颜色3的宝石：编号1, 3, 6

• 异或和：$1 \oplus 3 \oplus 6 = 4$
• 美丽值：$3 \times 4 = 12$

颜色6的宝石：编号2, 4, 5

• 异或和：$2 \oplus 4 \oplus 5 = 3$
• 美丽值：$6 \times 3 = 18$

总美丽值：$12 + 18 = 30$ ✓

注意事项

• 使用 long long 防止整数溢出（颜色值最大 $10^9$，异或和最大约 $2 \times 10^5$，乘积最大约 $2 \times 10^{14}$）
• 使用 unordered_map 提高查找效率
• 编号从1开始，符合题目要求