实验一：鱼与熊掌兼得问题 - 数据结构与算法实验报告

问题描述

题目背景

《孟子·告子上》有名言："鱼，我所欲也，熊掌，亦我所欲也；二者不可得兼，舍鱼而取熊掌者也。" 但这世界上还是有一些人可以做到鱼与熊掌兼得的。

给定 n 个人对 m 种物品的拥有关系。对其中任意一对物品种类（例如"鱼与熊掌"），请你统计有多少人能够兼得？

输入格式

• 第一行：n（≤10⁵）和 m（2≤m≤10⁵）
• 接下来 n 行：每行描述一个人的物品清单
• 格式：K M[1] M[2] ... M[K]
• 最后：查询总数 Q（≤100）
• Q 行查询：每行两个物品编号

输出格式

对每次查询，输出同时拥有两种物品的人数。

问题分析

这是一个典型的集合交集统计问题，需要高效处理多次查询。

关键观察

• 每个人拥有的物品可以用集合表示
• 查询本质是求集合交集的个数
• 需要处理多次查询，考虑缓存优化
• 物品数量较大，需要高效的数据结构

数据规模

• n ≤ 10⁵（人数）
• m ≤ 10⁵（物品种类）
• Q ≤ 100（查询次数）
• K ≤ 10³（每人物品数）

算法设计

核心思路

使用bitset存储每人的物品集合

位运算快速计算集合交集

哈希表缓存查询结果

数据结构选择

bitset<MAXM+1>：存储每人的物品集合
unordered_map：缓存查询结果
位运算：test() 和 AND 操作

优化策略

缓存机制：避免重复计算
位运算：O(1) 集合操作
内存优化：紧凑的数据表示

算法步骤

读取输入，为每个人创建 bitset 集合
对每个物品编号，在对应位置设置为 1
处理查询时，首先检查缓存
如果缓存未命中，遍历所有人计算交集
将结果存入缓存并返回

代码实现

#include <iostream>
#include <vector>
#include <bitset>
#include <unordered_map>
using namespace std;

const int MAXM = 100000;

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    
    // 使用 bitset 存储每个人的物品集合
    vector<bitset<MAXM+1>> people(n);
    
    // 读取每个人的物品清单
    for (int i = 0; i < n; i++) {
        int k;
        scanf("%d", &k);
        for (int j = 0; j < k; j++) {
            int item;
            scanf("%d", &item);
            people[i].set(item);  // 在对应位置设置为1
        }
    }
    
    int q;
    scanf("%d", &q);
    
    // 使用哈希表缓存查询结果
    unordered_map<long long, int> cache;
    
    while (q--) {
        int a, b;
        scanf("%d %d", &a, &b);
        
        // 生成唯一的缓存键
        long long key = (long long)a * (m + 1) + b;
        if (cache.count(key)) {
            printf("%d\n", cache[key]);
            continue;
        }
        
        // 计算同时拥有物品 a 和 b 的人数
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (people[i].test(a) && people[i].test(b)) {
                count++;
            }
        }
        
        // 缓存结果
        cache[key] = count;
        printf("%d\n", count);
    }
    
    return 0;
}

关键代码解析

bitset<MAXM+1>：高效的位集合
people[i].set(item)：设置物品位
people[i].test(a)：检查物品位
unordered_map：O(1) 查询缓存

优化亮点

位运算替代集合操作
缓存机制避免重复计算
紧凑的内存使用
快速的查询响应

复杂度分析

时间复杂度

预处理阶段

O(n × K)

读取并设置每个人的物品集合

查询阶段

O(Q × n) (最坏情况)

每次查询遍历所有人，有缓存优化

空间复杂度

主要存储

O(n × m/8)

bitset 紧凑存储，每位1bit

缓存存储

O(Q)

哈希表存储查询结果

性能优势

8倍

内存压缩率

O(1)

位操作复杂度

缓存

避免重复计算

测试用例分析

输入样例

4 8
3 4 1 8
4 7 1 8 4
5 6 5 1 2 3
4 3 2 4 8
3
2 3
7 6
8 4

输出结果

2
0
3

详细分析

人员	拥有物品	物品2	物品3	物品7	物品6	物品8	物品4
人员1	{4, 1, 8}	❌	❌	❌	❌	✅	✅
人员2	{7, 1, 8, 4}	❌	❌	✅	❌	✅	✅
人员3	{6, 5, 1, 2, 3}	✅	✅	❌	✅	❌	❌
人员4	{3, 2, 4, 8}	✅	✅	❌	❌	✅	✅

查询 (2,3): 人员3和人员4同时拥有 → 答案: 2

查询 (7,6): 无人同时拥有 → 答案: 0

查询 (8,4): 人员1、2、4同时拥有 → 答案: 3

优化思路

当前优化

✓

bitset优化：
使用位运算替代集合操作，内存压缩8倍
✓

缓存机制：
哈希表存储查询结果，避免重复计算
✓

内存对齐：
bitset自动优化内存对齐和访问

进阶优化

+

并行处理：
多线程并行处理查询，提升吞吐量
+

预计算：
预计算热门物品对的交集结果
+

分块优化：
将人员分块，利用局部性原理

性能对比

方法	时间复杂度	空间复杂度	优缺点
朴素方法	O(Q × n × K)	O(n × K)	慢，内存大
bitset方法	O(Q × n)	O(n × m/8)	快，内存优化
bitset+缓存	O(Q + unique × n)	O(n × m/8 + Q)	最优解

实验总结

核心收获

• 掌握了 bitset 的高效使用方法
• 理解了位运算在集合操作中的优势
• 学会了缓存机制优化重复查询
• 体验了内存与时间的权衡策略

技术亮点

• 位运算实现 O(1) 集合操作
• 哈希表提供 O(1) 查询缓存
• 紧凑数据结构节省内存空间
• 算法复杂度从 O(nK) 降至 O(n)

本实验展示了如何通过合理的数据结构选择和算法优化，
将看似简单的问题转化为高效、优雅的解决方案。

目录导航

实验一

鱼与熊掌兼得问题