✅ 春招备战指南 ✅

💡 学习建议：

• 先尝试独立解题
• 对照解析查漏补缺

🧸 题面描述背景等均已深度改编，做法和题目本质基本保持一致。

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

🌸 目前本专栏已经上线200+套真题改编解析，后续会持续更新的

春秋招笔试机考招合集 -> 互联网必备刷题宝典🔗

滴滴-2026.03.15-第二套

滴滴-2026.03.15-第二套

这套题前后衔接很顺。第一题是小状态压缩预处理，关键在于把“覆盖询问”转成“超集最小值”；第二题是标准的二分答案加贪心判定，想清楚 MEX >= x 等价条件以后就很直接。

题目一：小基 的配色礼盒

看起来像多次集合覆盖，真正能做是因为颜色种数只有 15。先做 OR 型 0/1 DP 求精确并集最优值，再补一层超集最小值，询问就能做到近似查表。

难度：中等

题目二：小基 的分段质检

题目本质是最大化所有分段 MEX 的下界。判定某个答案时，只要从左到右尽量早切，数能不能凑齐 0..x-1 就足够了，整体是很标准的二分可行性。

难度：中等

小基 的配色礼盒

问题描述

小基 正在为一份礼盒挑选装饰花材。

花店里一共有 种花，所有花涉及的颜色总数不超过 。第 种花自带一个颜色集合。若从中选出若干种花放进礼盒，那么礼盒最终呈现出的颜色集合，就是这些花颜色集合的并集。

现在 小基 预设了 个目标配色方案。对于每个方案，需要求出最少选择多少种花，才能让礼盒颜色集合覆盖这个方案中的所有颜色。也就是说，目标配色必须是最终并集的子集。

如果某个方案无论怎么选都无法满足，输出 -1。

输入格式

第一行输入两个整数 ，分别表示花的种类数和颜色总类上限。

接下来 行描述每种花：

• 每行先输入一个整数 ，表示这朵花包含的颜色数。
• 再输入 个互不相同的字符串，表示对应的颜色名。

然后输入一个整数 ，表示询问个数。

接下来 行描述目标配色：

• 每行先输入一个整数 。
• 再输入 个互不相同的字符串，表示该目标方案需要覆盖的颜色。

输出格式

对于每个询问输出一行一个整数：

• 若存在可行方案，输出最少需要选的花数。
• 否则输出 -1。

样例输入

4 3
1 Red
1 Orange
1 Yellow
2 Red Yellow
2
3 Red Orange Yellow
4 Red Orange Yellow Green

样例输出

2
-1

数据范围

• 
• 
• 
• 
• 颜色字符串长度满足

题解

这题看起来像是“多次最小集合覆盖”，如果按每个询问单独做搜索，肯定撑不住。

真正能做的关键只有一个：颜色总类数很小，只有 。这意味着任何颜色集合都可以压成一个二进制状态。

一、把颜色集合压成掩码

先给花店里出现过的颜色编号，编号范围是 。

• 一种花对应一个掩码 mask。
• 一个询问也对应一个掩码 target。

比如某种花同时带有第 1、3、4 号颜色，那么它的掩码就是这三位为 1 的二进制数。

二、先求“恰好并成某个集合”最少要几朵花

设 dp[s] 表示：

选若干种花后，颜色并集恰好等于状态 s 时，需要的最少花数。

初始只有空集合：

• dp[0] = 0
• 其他状态初始化为无穷大。

然后枚举每一种花的掩码 f，做一次 0/1 的 OR 型转移：。

这里每种花只会被转移一次，所以天然就是 0/1 选择。

有个细节很实用：如果两种花的颜色集合完全相同，那么保留一份就够了，因为多一朵同掩码的花不会扩展新的颜色，反而只会让答案更大。先把花掩码去重，可以明显减少常数。

三、询问要求的是“覆盖”，不是“恰好等于”

dp 求出来的是“并集恰好为 s”的最优值，但题目问的是：

并集只要是 target 的超集就行。

所以还要再做一遍超集最小值 DP。

设 best[s] 表示：

选花后得到的并集是 s 的某个超集时，所需最少花数。

初始令 best = dp，然后从高维状态往低维状态转移。转移可以写成：。做完以后，best[target] 就是覆盖 target 的最优答案。

四、为什么这样一定正确

第一步的 dp 已经穷尽了所有“选哪些花”的可能，并且记录的是某个确切并集的最优答案。

而任意一个询问，只关心最终并集是否覆盖目标集合。换句话说，只要最终状态是 target 的任意超集，都合法。

于是对所有超集取最小值，恰好就是这个询问的答案。这就是第二步超集 DP 的含义。

五、边界处理

如果询问中出现了一种从未在花店里出现过的颜色，那么这个询问直接无解，输出 -1。

这是唯一需要在预处理之前就特判的地方。

六、复杂度分析

设有效颜色数为 ，则 ，状态数是 。

• 预处理 OR-DP：，其中 是去重后的花掩码种数，且 。
• 超集最小值 DP：。
• 每个询问只需要把颜色转成掩码后查表，复杂度是 。

总空间复杂度为 。

参考代码

• Python

import sys

input = lambda: sys.stdin.readline().strip()


def solve() -> None:
    n, _ = map(int, input().split())
    idx = {}
    fls = []

    # 先把每种花转成掩码。
    for _ in range(n):
        parts = input().split()
        cnt = int(parts[0])
        mask = 0
        for i in range(1, cnt + 1):
            col = parts[i]
            if col not in idx:
                idx[col] = len(idx)
            mask |= 1 << idx[col]
        fls.append(mask)

    # 相同掩码的花重复出现没有收益，去重即可。
    fls = list(set(fls))
    m = len(idx)
    lim = 1 << m
    inf = 10**9

    # dp[s]：并集恰好为 s 时的最少花数。
    dp = [inf] * lim
    dp[0] = 0
    for fm in fls:
        ndp = dp[:]
        for s in range(lim):
            if dp[s] == inf:
                continue
            ns = s | fm
            if dp[s] + 1 < ndp[ns]:
                ndp[ns] = dp[s] + 1
        dp = ndp

    # best[s]：并集覆盖 s 时的最少花数。
    best = dp[:]
    for b in range(m):
        bit = 1 << b
        for s in range(lim):
            if s & bit:
                continue
            if best[s | bit] < best[s]:
                best[s] = best[s | bit]

    q = int(input())
    out = []
    for _ in range(q):
        parts = input().split()
        cnt = int(parts[0])
        tar = 0
        ok = True
        for i in range(1, cnt + 1):
            col = parts[i]
            if col not in idx:
                ok = False
            else:
                tar |= 1 << idx[col]

        if not ok or best[tar] == inf:
            out.append("-1")
        else:
            out.append(str(best[tar]))

    sys.stdout.write("\n".join(out))


if __name__ == "__main__":
    solve()

• Cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, mLimit;
    cin >> n >> mLimit;

    unordered_map<string, int> id;
    vector<int> flowers;

    for (int i = 0; i < n; ++i) {
        int k;
        cin >> k;
        int mask = 0;
        for (int j = 0; j < k; ++j) {
            string col;
            cin >> col;
            if (!id.count(col)) {
                id[col] = (int)id.size();
            }
            mask |= 1 << id[col];
        }
        flowers.push_back(mask);
    }

    sort(flowers.begin(), flowers.end());
    flowers.erase(unique(flowers.begin(), flowers.end()), flowers.end());

    int m = (int)id.size();
    int lim = 1 << m;
    const int INF = 1e9;

    // dp[s]：并集恰好为 s 时的最少花数。
    vector<int> dp(lim, INF);
    dp[0] = 0;

    for (int fm : flowers) {
        vector<int> ndp(dp);
        for (int s = 0; s < lim; ++s) {
            if (dp[s] == INF) continue;
            int ns = s | fm;
            ndp[ns] = min(ndp[ns], dp[s] + 1);
        }
        dp.swap(ndp);
    }

    // best[s]：并集覆盖 s 时的最少花数。
    vector<int> best(dp);
    for (int b = 0; b < m; ++b) {
        int bit = 1 << b;
        for (int s = 0; s < lim; ++s) {
            if (s & bit) continue;
            best[s] = min(best[s], best[s | bit]);
        }
    }

    int q;
    cin >> q;
    while (q--) {
        int k;
        cin >> k;
        int tar = 0;
        bool ok = true;
        for (int i = 0; i < k; ++i) {
            string col;
            cin >> col;
            auto it = id.find(col);
            if (it == id.end()) {
                ok = false;
            } else {
                tar |= 1 << it->second;
            }
        }

        if (!ok || best[tar] == INF) {
            cout << -1 << '\n';
        } else {
            cout << best[tar] << '\n';
        }
    }

    return 0;
}

• Java

import java.io.*;
import java.util.*;

public class Main {
    static class FastScanner {
        private final InputStream in = System.in;
        private final byte[] buf = new byte[1 << 16];