G. Shuffling Songs - 题解

比赛与标签

比赛: Codeforces Round 937 (Div. 4) 标签: bitmasks, dfs and similar, dp, graphs, hashing, implementation, strings 难度: *1900

题目大意喵~

Vladislav小哥有一个包含 n 首歌曲的歌单。每首歌都有自己的风格（genre）和作者（writer）。他想重新排列这些歌曲，得到一个“激动人心”的歌单。

什么是“激动人心”的歌单呢？就是任意两首相邻的歌曲，要么它们的风格相同，要么它们的作者相同（当然两者都相同也行啦）。

但是呢，不一定所有的歌曲都能排进这样一个完美的歌单里。所以，他可以先从歌单里移除一些歌曲，然后再把剩下的歌曲排成“激动人心”的序列。

因为每首歌都是心头肉，Vladislav小哥希望移除的歌曲越少越好。我们的任务就是，帮他计算出最少需要移除多少首歌曲，才能让剩下的歌单变得“激动人心”，的说。

输入会告诉我们歌曲的数量 n，以及每首歌的风格和作者。输出一个整数，表示最少移除的歌曲数量。

解题思路，一探究竟！

看到这道题，首先要转换一下思路呐！题目要求“最少移除的歌曲数量”，这其实等价于求解“最多可以保留多少首歌曲”来组成一个“激动人心”的歌单，对吧？如果我们能找到这个最大数量 max_size，那么答案就是 n - max_size 啦！

那么，怎样才能找到这个 max_size 呢？

第一步：建模成图论问题喵~

我们可以把每首歌曲看作一个图上的节点。如果两首歌曲 i 和 j 可以相邻（即它们的风格相同或作者相同），我们就在节点 i 和节点 j 之间连一条边。

这样一来，一个“激动人心”的歌单就对应着图中的一条路径！因为路径上的任意相邻节点都是有边连接的。而我们的目标，就是在这个图上找到一个节点子集，使得这个子集中的所有节点可以构成一条哈密顿路径（就是一条经过子集中每个节点恰好一次的路径），并且这个子集的大小要尽可能大。简单来说，就是找图中的最长路径！

第二步：祭出状压DP大法！

注意到题目给的 n 非常小（1 <= n <= 16），这是一个超级明显的信号，喵！它在疯狂暗示我们可以使用时间复杂度跟 2^n 相关的算法。对于这种涉及子集的最优化问题，状态压缩动态规划（Bitmask DP） 就是我们的不二之选！

我们来设计一下DP的状态： dp[mask][i]

这个状态表示一个布尔值（true 或 false）。

• mask 是一个整数，它的二进制表示代表了歌曲的子集。如果 mask 的第 j 位是1，就表示歌曲 j 在我们选择的子集中。
• i 表示这个子集构成的路径的终点是歌曲 i。

所以，dp[mask][i] = true 的含义是：存在一条路径，它包含了 mask 所代表的所有歌曲，并且这条路径的终点是歌曲 i。

状态转移方程是什么呢？

要计算 dp[mask][i]，我们可以想，这条以 i 结尾的路径是怎么来的呢？它一定是从一个少一首歌的路径扩展而来的。

假设这条路径的上一个节点是 j。那么在到达 i 之前，我们已经走过了一条包含 mask 中除了 i 以外所有歌曲、并且以 j 结尾的路径。这个“除了 i 以外的子集”可以用 prev_mask = mask ^ (1 << i) 来表示。

因此，只要满足以下两个条件，dp[mask][i] 就可以是 true：

1. 存在一个前置状态 dp[prev_mask][j] = true。
2. 歌曲 j 和歌曲 i 之间可以连接，即它们在图上有边 edge[j][i] = true。

我们的转移方程就是： dp[mask][i] = OR (dp[mask ^ (1 << i)][j]) (对于所有在 mask ^ (1 << i) 中且与 i 有边的 j)

基础情况（Base Case） 当路径只包含一首歌 i 时，这本身就是一条合法的路径。所以，对于任意歌曲 i（从 0 到 n-1），dp[1 << i][i] 都为 true。

最终答案 在计算DP的过程中，我们只需要记录下所有 dp[mask][i] 为 true 的状态中，mask 包含的歌曲数量（即二进制中1的个数，可以用 __builtin_popcount(mask) 快速计算）的最大值。这个最大值就是我们能保留的最多歌曲数 max_size。

最后，n - max_size 就是我们要的答案啦！

一个小优化 题目中的风格和作者是字符串，直接比较会比较慢。我们可以用 std::map 把每个独特的字符串映射成一个整数ID，这样后续比较就变成整数比较，快多啦！

代码实现，喵呜~

下面就是AC代码的完整版啦，我已经加上了详细的注释，方便大家理解每一部分的作用哦！

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

// 使用 __builtin_popcount 需要这个头文件，不过很多编译器内置了
// #include <intrin.h> 

using namespace std;

int main() {
    // 提高cin/cout效率
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<string> genres(n), writers(n);
        for (int i = 0; i < n; i++) {
            cin >> genres[i] >> writers[i];
        }

        // 步骤1：字符串离散化，用map将字符串映射成整数ID，方便比较
        map<string, int> gMap, wMap;
        vector<int> gid(n), wid(n); // 存储每首歌的风格ID和作者ID
        int gcnt = 0, wcnt = 0; // 唯一ID计数器
        for (int i = 0; i < n; i++) {
            if (gMap.find(genres[i]) != gMap.end()) {
                gid[i] = gMap[genres[i]];
            } else {
                gid[i] = gcnt;
                gMap[genres[i]] = gcnt++;
            }
            if (wMap.find(writers[i]) != wMap.end()) {
                wid[i] = wMap[writers[i]];
            } else {
                wid[i] = wcnt;
                wMap[writers[i]] = wcnt++;
            }
        }

        // 步骤2：构建邻接矩阵，表示歌曲之间是否可以相邻
        vector<vector<bool>> edge(n, vector<bool>(n, false));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                // 如果两首歌风格相同或作者相同，则它们之间有边
                if (gid[i] == gid[j] || wid[i] == wid[j]) {
                    edge[i][j] = true;
                }
            }
        }

        // 步骤3：状态压缩DP
        int total_masks = 1 << n;
        
        // 预计算每个mask的popcount(二进制中1的个数)，避免重复计算
        vector<int> pc(total_masks, 0);
        for (int mask = 0; mask < total_masks; mask++) {
            pc[mask] = __builtin_popcount(mask);
        }

        // dp[mask][i] 表示：包含mask中所有歌曲、且以歌曲i结尾的路径是否存在
        vector<vector<bool>> dp(total_masks, vector<bool>(n, false));
        int max_size = 0; // 记录能组成路径的最大歌曲数

        // 初始化DP：任何单曲本身就是一条长度为1的路径
        for (int i = 0; i < n; i++) {
            dp[1 << i][i] = true;
        }

        // 遍历所有可能的歌曲子集(mask)
        for (int mask = 1; mask < total_masks; mask++) {
            // 遍历子集中的每一首歌i，作为当前路径的终点
            for (int i = 0; i < n; i++) {
                // 如果dp[mask][i]为真，说明我们成功构成了一条路径
                if (dp[mask][i]) {
                    // 更新最大路径长度
                    if (pc[mask] > max_size) {
                        max_size = pc[mask];
                    }
                    // 尝试从当前路径(mask, i)扩展到新的歌曲j
                    for (int j = 0; j < n; j++) {
                        // 如果歌曲j不在当前路径中
                        if (!(mask & (1 << j))) {
                            // 并且歌曲i和歌曲j可以相连
                            if (edge[i][j]) {
                                // 那么我们可以构成一条新的、更长的路径
                                int new_mask = mask | (1 << j);
                                dp[new_mask][j] = true;
                            }
                        }
                    }
                }
            }
        }
        
        // 如果一首歌都没有，max_size会是0。但只要有歌，至少能保留1首。
        if (n > 0 && max_size == 0) max_size = 1;
        // 如果n=0，max_size=0, n-max_size=0，正确。
        // 如果n>0，max_size=0，说明没有边，只能保留1首歌，max_size应为1。
        // 不过根据上面的DP逻辑，如果n>0，max_size至少为1，所以这个判断其实可以省略。

        // 最少移除数 = 总数 - 最多保留数
        cout << n - max_size << endl;
    }
    return 0;
}

复杂度分析的说

• 时间复杂度: O(2^n * n^2) 的说。 我们有 2^n 个 mask，对于每个 mask，我们遍历 n 个可能的终点 i，再从 i 尝试扩展到 n 个新的终点 j。所以总的操作次数是 2^n * n * n。再加上预处理建图的 O(n^2) 和字符串映射的时间，DP部分是主导，所以总复杂度是 O(2^n * n^2)。因为 n <= 16，这个复杂度是完全可以接受的！

• 空间复杂度: O(2^n * n) 的说。 主要的开销是 dp 数组，它的大小是 (1 << n) * n。其他如邻接矩阵 edge 是 O(n^2)，也远小于DP表的开销。

知识点与总结，快来记笔记呐！

这道题真是一道状压DP的经典教学题，喵~ 从中我们可以学到很多东西：

1. 逆向思维: "求最少移除" 常常可以转化为 "求最多保留"，这种思路转换在很多最优化问题里都很有用！
2. 图论建模: 学会把问题中的元素和关系抽象成图的节点和边，是解决复杂问题的关键一步。
3. 状态压缩DP: 当你看到数据范围极小（特别是 n <= 20 左右）并且问题与“子集”有关时，一定要立刻想到状压DP！记住它的核心：用一个整数的二进制位来表示一个集合的状态。
4. 路径问题: 在图中找最长路径是一个NP-hard问题，但在点数很少的情况下，状压DP是解决它的有力武器。
5. 预处理与优化: 像本题中用 map 将字符串映射成整数，以及预计算 popcount，都是能有效提升代码效率的好习惯。

希望这篇题解能帮到大家！只要抓住了 n 很小这个关键点，并联想到图论和状压DP，问题就迎刃而解啦！继续加油，探索更多算法的奥秘吧，喵~！