E. Anya and Cubes - 题解

比赛与标签

比赛: Codeforces Round 297 (Div. 2) 标签: binary search, bitmasks, brute force, dp, math, meet-in-the-middle 难度: *2100

题目大意喵~

你好呀，指挥官！ Anya 小姐姐有一堆写着数字的方块，还有一些带感叹号的贴纸。我们的任务是帮她解决一个有趣的组合问题，喵~

具体来说，我们有 n 个方块，每个上面都有一个数字 a[i]。我们还有 k 张感叹号贴纸。对于每个方块，我们可以有三种选择：

不选它，把它丢在一边。
选择它，把它上面的数字 a[i] 加入我们的总和。
选择它，并贴上一张贴纸，把它上面的数字变成阶乘 a[i]!，然后加入总和。当然，贴纸不能超过 k 张哦。

我们的目标是，找出有多少种不同的选择方块和贴贴纸的方式，能让最终的总和恰好等于给定的目标值 S 呢？

输入:

第一行是三个整数 n, k, S。
第二行是 n 个方块上的数字。

输出:

一个整数，表示能凑出总和 S 的方案数。

解题思路，开动脑筋啦！

看到 n <= 25 这个数据范围，是不是感觉很微妙呀？直接暴力搜索的话，每个方块有3种状态（不选、选、选并阶乘），总的复杂度会是 O(3^n)。当 n=25 时，3^25 是一个天文数字，肯定会超时的说！(つд⊂)

这种 N 比较小，但指数级复杂度又无法接受的情况，通常都在暗示我们一个非常强大的技巧——折半搜索 (Meet-in-the-Middle)！

它的核心思想就是“分而治之，中间相遇”，喵~

分割问题: 我们把 n 个方块分成两半。比如说，前 n/2 个方块是第一组，剩下的 n - n/2 个是第二组。
暴力搜索第一半: 我们对第一组方块进行一次深度优先搜索（DFS）。我们会枚举出所有可能的组合方式（不选、选、选并阶乘），并记录下每种组合得到的 <总和, 使用的贴纸数>。为了方便后续查找，我们可以用一个 map 数组来存储这些结果。sums1[i] 是一个 map，它记录了使用 i 张贴纸时，可以凑出的各种总和以及对应的方案数。
- map<ll, ll> sums1[k+1]
- sums1[贴纸数][总和] = 方案数
一个小小的剪枝: 阶乘增长得非常快！20! 就已经超过了 10^18，比 S 的最大值还要大。所以，如果一个方块上的数字 a[i] 大于等于 21，我们根本不需要考虑给它贴贴纸，因为它一定会超出 S。我们可以在计算阶乘时预处理一下，超过 S 的都记为一个特殊的超大值就好啦。
搜索第二半并合并结果: 接下来，我们对第二组方块也进行一次 DFS。对于第二组的每一种组合，假设我们得到了一个总和 sum2 并使用了 k2 张贴纸。那么，为了让最终总和等于 S，我们需要在第一组中找到一个总和为 sum1 = S - sum2 的组合。同时，两组使用的总贴纸数不能超过 k。也就是说，第一组使用的贴纸数 k1 必须满足 k1 + k2 <= k，即 k1 <= k - k2。所以，对于一个 (sum2, k2)，我们就在 sums1 中查找：
- 在 sums1[0] 中，S - sum2 的方案数有多少？
- 在 sums1[1] 中，S - sum2 的方案数有多少？
- ...
- 在 sums1[k - k2] 中，S - sum2 的方案数有多少？把这些方案数全部加起来，就是与当前第二组的 (sum2, k2) 组合配对的方案总数啦！

通过这种方式，我们将一个 O(3^n) 的问题，拆解成了两个 O(3^(n/2)) 的问题，复杂度大大降低，变得可以接受了呢！这就是折半搜索的魔法之处啦！

代码实现喵~

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

cpp

#include <iostream>
#include <vector>
#include <numeric>
#include <map>

using namespace std;
typedef long long ll;

int n, k;
ll S;
vector<ll> a;
ll fact[21]; // 预处理阶乘，最多到20!

// sums1[i] 是一个 map，存储使用 i 个贴纸时，{sum -> count} 的映射
// 也就是第一半搜索的结果
map<ll, ll> sums1[26]; 

// 递归函数，用于生成第一半方块的所有可能和
// idx: 当前处理的方块索引
// end_idx: 第一半的结束索引
// current_sum: 当前累加的和
// stickers_used: 当前已使用的贴纸数
void generate_sums1(int idx, int end_idx, ll current_sum, int stickers_used) {
    // base case: 当处理完第一半的所有方块
    if (idx == end_idx) {
        sums1[stickers_used][current_sum]++; // 记录方案
        return;
    }

    // 决策1: 不选择当前的方块 a[idx]
    generate_sums1(idx + 1, end_idx, current_sum, stickers_used);

    // 决策2: 选择当前的方块 a[idx]，不贴贴纸
    if (a[idx] <= S - current_sum) { // 剪枝：如果加上后会超，就不必继续了
        generate_sums1(idx + 1, end_idx, current_sum + a[idx], stickers_used);
    }

    // 决策3: 选择当前的方块 a[idx]，并贴上贴纸
    // 条件：a[idx] < 21 (否则阶乘太大), 还有贴纸可用
    if (a[idx] < 21 && stickers_used < k) {
        if (fact[a[idx]] <= S - current_sum) { // 剪枝：阶乘和不能超
            generate_sums1(idx + 1, end_idx, current_sum + fact[a[idx]], stickers_used + 1);
        }
    }
}

ll total_ways = 0; // 最终答案

// 递归函数，用于搜索第二半，并与第一半的结果匹配
// idx: 当前处理的方块索引
// end_idx: 第二半的结束索引 (即 n)
// current_sum: 当前累加的和
// stickers_used: 当前已使用的贴纸数
void find_matches(int idx, int end_idx, ll current_sum, int stickers_used) {
    // base case: 当处理完第二半的所有方块
    if (idx == end_idx) {
        ll remaining_sum = S - current_sum; // 计算第一半需要凑出的和
        if (remaining_sum >= 0) {
            // 遍历第一半可能使用的贴纸数 k1
            for (int k1 = 0; k1 <= k - stickers_used; ++k1) {
                // 在 sums1[k1] 中查找是否存在需要的和
                auto it = sums1[k1].find(remaining_sum);
                if (it != sums1[k1].end()) {
                    total_ways += it->second; // 加上对应的方案数
                }
            }
        }
        return;
    }

    // 决策1: 不选择当前的方块 a[idx]
    find_matches(idx + 1, end_idx, current_sum, stickers_used);
    
    // 决策2: 选择当前的方块 a[idx]，不贴贴纸
    if (a[idx] <= S - current_sum) {
        find_matches(idx + 1, end_idx, current_sum + a[idx], stickers_used);
    }
    
    // 决策3: 选择当前的方块 a[idx]，并贴上贴纸
    if (a[idx] < 21 && stickers_used < k) {
        if (fact[a[idx]] <= S - current_sum) {
            find_matches(idx + 1, end_idx, current_sum + fact[a[idx]], stickers_used + 1);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> k >> S;
    a.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    // 预计算阶乘，处理溢出情况
    fact[0] = 1;
    for (int i = 1; i < 21; ++i) {
        ll temp;
        // 使用 __builtin_mul_overflow 防止乘法溢出，或者如果阶乘已经大于S，也没必要算了
        if (__builtin_mul_overflow(fact[i-1], i, &temp) || temp > S) {
            fact[i] = S + 2; // 用一个比S大的哨兵值表示 "无效"
        } else {
            fact[i] = temp;
        }
    }

    // 将方块分成两半，mid 是第二半的起始点
    int mid = n / 2;
    generate_sums1(0, mid, 0, 0);
    find_matches(mid, n, 0, 0);

    cout << total_ways << endl;

    return 0;
}

复杂度分析

时间复杂度: O(3^(n/2) * n) 的说。
- 我们把 n 个元素分成了两半，每半大约 n/2 个。
- generate_sums1 函数对第一半进行搜索，其状态数最多为 3^(n/2)。每次操作涉及到 map 的插入，复杂度为 log(map.size())，map 的大小也最多是 3^(n/2)。所以这部分的复杂度大约是 O(3^(n/2) * log(3^(n/2))) = O(3^(n/2) * n/2)。
- find_matches 函数对第二半进行搜索，状态数也是 3^(n/2)。在每个叶子节点，我们需要循环 k 次（k <= n）并在 map 中查找，所以这部分的复杂度大约是 O(3^(n/2) * k * n/2)。
- 综合来看，总的时间复杂度就是 O(3^(n/2) * n) 级别，对于 n=25 来说是完全可以接受的！
空间复杂度: O(3^(n/2)) 的说。
- 主要的空间开销来自于存储第一半搜索结果的 sums1 数组。在最坏情况下，map 中会存储 3^(n/2) 个不同的和，所以空间复杂度就是 O(3^(n/2))。

知识点与总结

这道题真是一道非常经典的 Meet-in-the-Middle 教学题呢，喵~

核心算法 - 折半搜索 (Meet-in-the-Middle): 当你遇到一个问题，它的 N 不大（通常在 25 到 40 之间），而暴力解法的复杂度是指数级（如 2^N, 3^N, C(N, k) 等）时，一定要想想能不能把问题劈成两半解决！
深度优先搜索 (DFS): 无论是生成第一半的和，还是搜索第二半的组合，我们都用了 DFS 来遍历所有可能性。这是暴力枚举组合的常用手段。
剪枝: 在搜索过程中，如果当前的和已经超过了目标 S，或者阶乘值太大，就没必要继续往下搜索了。有效的剪枝能极大地提高程序的效率。
数据结构 std::map: map 在这里起到了关键作用，它能高效地存储和查询 <sum, count> 对，是实现折半搜索中“相遇”步骤的利器。

希望这篇题解能帮到你！遇到难题不要怕，拆解它，分析它，总能找到突破口的！加油哦，指挥官！喵~ (ฅ'ω'ฅ)

E. Anya and Cubes - 题解 ​

比赛与标签 ​

题目大意喵~ ​

解题思路，开动脑筋啦！ ​

代码实现喵~ ​

复杂度分析 ​

知识点与总结 ​