本技术文章探讨如何高效解决一个技能辅导匹配问题。假定存在 N 名学生和 S 项不同的技能，这些技能用 1 到 S 的整数表示。每位学生 i 掌握 c_i 项技能，其中 1 ≤ c_i ≤ 5。如果学生 i 掌握某项学生 j 不具备的技能，则称学生 i 可以辅导学生 j。我们的目标是计算满足此条件的所有有序学生对 (i, j) 的总数量。

问题分析与转化

直接计算所有满足"学生 i 可以辅导学生 j"的对数可能比较复杂。我们可以转而计算其补集：即学生 i 不能辅导学生 j 的对数，然后用总的可能对数 N * N 减去这个补集的数量。学生 i 不能辅导学生 j 的条件是：学生 i 掌握的所有技能，学生 j 也全部掌握。换言之，学生 i 的技能集合是学生 j 技能集合的子集。

考虑到问题的对称性，计算"学生 i 技能集是学生 j 技能集子集"的对数，与计算"学生 j 技能集是学生 i 技能集子集"的对数是等价的。因此，我们可以选择计算后者，即统计所有有序对 (i, j)，使得学生 j 的技能集是学生 i 技能集的子集。最终的答案就是 N * N 减去这个统计值。

关键约束与优化思路

• 学生总数 N 最高可达 5 × 10^4。
• 技能总数 S 最高可达 1000。
• 每位学生掌握的技能数量 c_i 非常小，仅为 1 到 5。这是解决此问题的关键。
• 时间限制：20秒，内存限制：1GB。

由于 c_i 的上限非常小，每个学生的技能集合的非空子集数量非常有限 (最多 2^5 - 1 = 31 个)。这启发我们可以对每个学生的技能集合及其子集进行有效处理。

初始实现（效率较低）

一种直观的方法是：

1. 首先，读取所有学生的技能集合，对每个集合内部的技能进行排序。
2. 使用 std::map<std::vector<int>, int> 来统计每种独特技能集合出现的频率。
3. 遍历每位学生 P_i (0 到 N-1)，获取其技能集合 S_i。
4. 生成 S_i 的所有非空子集 T。
5. 对于每个子集 T，查询 std::map 中有多少学生的技能集合恰好是 T。将这些数量累加到 total_subset_pairs 变量中。这个变量将累加所有 (i, j) 对，使得 S_j 是 S_i 的非空子集。由于 c_j ≥ 1，S_j 总是非空的，所以此计数涵盖了所有 S_j 是 S_i 子集的情况。
6. 最终结果是 N * N - total_subset_pairs。

然而，这种方法在处理大量数据时效率低下。主要瓶颈在于 std::map 的键是 std::vector<int> 类型。每次对 map 的访问（插入或查找）都需要对 vector 进行比较，其时间复杂度取决于 vector 的大小。尽管 vector 大小上限为 5，但 N 值很大，导致大量的 vector 比较操作使得总体运行时间过长。

#include <iostream>
#include <vector>
#include <algorithm> // For std::sort
#include <map>       // For std::map

// 解决单个测试用例的函数
void solve_case_slow() {
    int num_people, total_skill_types;
    std::cin >> num_people >> total_skill_types;

    std::vector<std::vector<int>> all_person_skills;
    std::map<std::vector<int>, int> skill_set_frequencies;

    // 读取所有学生的技能集合，并统计频率
    for (int i = 0; i < num_people; ++i) {
        int skills_count;
        std::cin >> skills_count;
        std::vector<int> current_person_skills(skills_count);
        for (int j = 0; j < skills_count; ++j) {
            std::cin >> current_person_skills[j];
        }
        std::sort(current_person_skills.begin(), current_person_skills.end()); // 排序内部技能
        all_person_skills.push_back(current_person_skills);
        skill_set_frequencies[current_person_skills]++; // 统计该技能集合的频率
    }

    long long total_pairs_j_subset_of_i = 0; // 统计 (i, j) 对，其中 S_j 是 S_i 的子集

    // 遍历每个学生 i
    for (int i = 0; i < num_people; ++i) {
        int current_skills_size = all_person_skills[i].size();
        // 枚举学生 i 的技能集合 S_i 的所有非空子集
        // c_i ≥ 1 保证 current_skills_size ≥ 1
        // submask 从 1 开始，保证子集非空
        for (int submask = 1; submask < (1 << current_skills_size); ++submask) {
            std::vector<int> current_subset_skills;
            for (int j = 0; j < current_skills_size; ++j) {
                if ((submask >> j) & 1) { // 如果第 j 位技能在子集中
                    current_subset_skills.push_back(all_person_skills[i][j]);
                }
            }
            // 统计有多少学生的技能集合恰好等于 current_subset_skills
            total_pairs_j_subset_of_i += skill_set_frequencies[current_subset_skills];
        }
    }

    long long result = (long long)num_people * num_people - total_pairs_j_subset_of_i;
    std::cout << result << std::endl;
}

int main() {
    // 启用快速I/O
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int T_test_cases;
    std::cin >> T_test_cases;
    for (int t = 1; t <= T_test_cases; ++t) {
        // 如果竞赛平台要求特定输出格式，例如 "Case #1: "，可以在此处添加
        // std::cout << "Case #" << t << ": ";
        solve_case_slow();
    }
    return 0;
}

优化方案

为了提高效率，我们可以避免使用 std::map 进行频率统计和查找，转而利用 std::vector 的排序和二分查找功能：

1. 将所有学生的技能集合（已内部排序）收集到一个 std::vector<std::vector<int>> 中。
2. 对这个包含所有技能集合的 vector 进行整体排序。这样，相同的技能集合会相邻排列。
3. 当需要统计某个特定子集 T 出现的频率时，我们可以使用 std::lower_bound 和 std::upper_bound 在已排序的 vector 中高效地查找 T 的出现范围，从而获得其频率。这种查找的时间复杂度为 O(C_max log N)，其中 C_max 是技能集合的最大大小（此处为 5）。
4. 在数据读取阶段，可以预先为 std::vector<std::vector<int>> 分配好空间，以避免频繁的内存重新分配。

这个优化方案将 map 查找的对数比较操作替换为 std::vector 的二分查找，显著提升了性能。

#include <iostream>
#include <vector>
#include <algorithm> // For std::sort, std::lower_bound, std::upper_bound
#include <utility>   // For std::move (C++11 and later)

// 解决单个测试用例的优化函数
void optimized_solve_case() {
    int num_students, total_skill_types;
    std::cin >> num_students >> total_skill_types;

    // 预分配空间，避免频繁的内存重新分配
    std::vector<std::vector<int>> all_student_skill_sets(num_students);

    // 读取所有学生的技能集合并排序
    for (int i = 0; i < num_students; ++i) {
        int student_skill_count;
        std::cin >> student_skill_count;
        // 使用局部变量 temp_skills 存储当前学生的技能，然后通过移动语义赋值
        std::vector<int> temp_skills(student_skill_count);
        for (int j = 0; j < student_skill_count; ++j) {
            std::cin >> temp_skills[j];
        }
        std::sort(temp_skills.begin(), temp_skills.end());
        all_student_skill_sets[i] = std::move(temp_skills); // (1) 优化点：使用移动赋值
    }

    // 对所有学生的技能集合进行整体排序，以便后续进行二分查找
    std::sort(all_student_skill_sets.begin(), all_student_skill_sets.end());

    long long count_j_subset_of_i = 0; // 统计 (i, j) 对，其中 S_j 是 S_i 的子集

    // 遍历每个学生 i
    for (int i = 0; i < num_students; ++i) {
        int current_student_skills_size = all_student_skill_sets[i].size();
        // 遍历当前学生 S_i 的所有非空子集
        // 题目限制 c_i ≥ 1，所以 current_student_skills_size ≥ 1。
        // 子集 submask 从 1 开始，确保生成的子集 generated_subset_skills 也非空。
        for (int submask = 1; submask < (1 << current_student_skills_size); ++submask) {
            std::vector<int> generated_subset_skills;
            for (int k = 0; k < current_student_skills_size; ++k) {
                if ((submask >> k) & 1) { // 检查位 k 是否被设置
                    generated_subset_skills.push_back(all_student_skill_sets[i][k]);
                }
            }
            // 使用二分查找统计有多少学生的技能集合与 generated_subset_skills 完全相同
            auto range_start = std::lower_bound(all_student_skill_sets.begin(), all_student_skill_sets.end(), generated_subset_skills);
            auto range_end = std::upper_bound(all_student_skill_sets.begin(), all_student_skill_sets.end(), generated_subset_skills);
            count_j_subset_of_i += std::distance(range_start, range_end);
        }
    }

    // 总对数减去不能辅导的对数，即为可辅导的对数
    long long total_tutoring_pairs = (long long)num_students * num_students - count_j_subset_of_i;
    std::cout << total_tutoring_pairs << std::endl;
}

int main() {
    // 启用快速I/O
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int T_test_cases;
    std::cin >> T_test_cases;
    for (int t = 1; t <= T_test_cases; ++t) {
        // 如果竞赛平台要求特定输出格式，例如 "Case #1: "，可以在此处添加
        // std::cout << "Case #" << t << ": ";
        optimized_solve_case();
    }
    return 0;
}

关于 C++ 移动语义 (1)

在优化代码的 (1) 处，我们使用了 all_student_skill_sets[i] = std::move(temp_skills);。这旨在通过移动构造而非拷贝构造来提高效率。如果写成 all_student_skill_sets[i] = temp_skills;，编译器是否会选择调用 std::vector<int> 的移动赋值运算符，取决于具体的编译器版本、优化级别以及 temp_skills 是否被认为是"将亡值 (rvalue)"。

• 在 C++11 及更高版本中，如果编译器能够确定 temp_skills 在赋值后不再使用，并且启用了足够的优化级别（如 -O2 或 -O3），它可能会尝试进行返回值优化 (RVO) 或命名返回值优化 (NRVO)。然而，这主要发生在函数返回时。
• 对于局部变量赋值给另一个对象，编译器一般不会自行推断并执行移动操作，除非显式使用 std::move。
• 因此，显式使用 std::move(temp_skills) 更能保证调用移动赋值运算符，尤其是在赋值后 temp_skills 确实不再需要的情况下。这是一种良好的实践，可以减少内存拷贝开销，提高程序性能。