F. Valuable Cards - 题解

比赛与标签

比赛: Codeforces Round 957 (Div. 3) 标签: brute force, dp, greedy, number theory, two pointers 难度: *1900

题目大意喵~

喵哈~！主人 sama，欢迎来到 Kmes 的咖啡馆！这次我们的任务是帮 Kmes 解决一个卡片难题，这样他才能享用他最爱的美食呐！

事情是这样的：我们有一排 n 张卡片，每张卡片上有一个数字 a_i。还有一个目标数字 x。我们需要把这一排卡片切分成几段，目标是让分出来的段数最少。

但是有一个规则哦！每一段都必须是 “坏” 的。一个段是 “坏” 的，意思是说，我们 不能 从这个段里选出任意数量的卡片，让它们的乘积正好等于 x。反过来说，如果一个段里可以凑出乘积 x，那它就是 “好” 的，是不被允许的。

所以，我们的任务就是：找到一种切分方法，使得所有段都是 “坏” 的，并且总段数最少。这其实就是要我们把每一段都尽可能地拉长，直到再加一个数就会变 “好” 的前一刻，果断切开，开始新的段！明白了吗喵？

解题思路，开动脑筋喵！

这个问题看起来有点复杂，但别怕，我们一步步来分析，肯定能解决的，的说！

贪心是我们的好朋友！

要想让段数最少，一个非常自然的想法就是 贪心！我们希望每一段都尽可能地长。所以，我们可以从左到右遍历所有卡片，试着把它们一个个加入当前的段。只要当前的段还是 “坏” 的，我们就继续加。直到我们发现，加入下一张卡片 a[i] 之后，这个段就变 “好” 了（也就是可以凑出 x 了），那我们该怎么办呢？

很简单！我们不能加入 a[i]。当前的段就只能到 a[i-1] 为止。我们在这里切一刀，完成了一个 “坏” 段。然后，从 a[i] 开始，我们开启一个全新的段，继续这个过程。这个贪心策略是正确的，因为当前段的结束不会影响后续段的最优选择，喵~

如何判断一个段是不是“坏”的？

现在核心问题来了：对于一个正在构建的段，我们要怎么快速判断，加入一个新的数 a[i] 之后，它会不会变 “好” 呢？

这本质上是一个 子集乘积问题。我们需要知道在当前段 a[l...r] 中，所有可能的子集乘积。如果 x 在这些乘积中，那这个段就是 “好” 的。

一个直接的想法是用动态规划（DP）。我们可以维护一个集合，存放当前段能凑出来的所有乘积。每当来一个新的数 a[i]，我们就用它去乘集合里已有的所有数，把得到的新乘积再加入集合。

关键优化：数字论的魔法！

直接用 DP 的话，乘积可能会变得非常大，集合也会变得巨大无比，肯定会超时的说！但是，这里有一个超级重要的性质，是解题的关键喵！

如果一堆数的乘积等于 x，那么这一堆数里的每一个数，以及它们任意组合的中间乘积，都必须是 x 的因数！

比如说，2 * 3 * 4 = 24。那么 2, 3, 4 都是 24 的因数，中间乘积 2*3=6，2*4=8，3*4=12 也都是 24 的因数。

这个发现太棒了！这意味着，在我们的 DP 过程中：

1. 如果一张卡片 a[i] 本身就不是 x 的因数，那它根本不可能参与构成 x 的乘积。我们可以直接把它加入当前段，因为它没有任何 “危险性”。
2. 我们在计算新乘积时，如果 旧乘积 * a[i] 的结果不是 x 的因数，那它也绝无可能再乘上别的数得到 x。这种中间结果我们也可以直接扔掉！

这样一来，我们 DP 状态集合里需要维护的数，就只剩下 x 的因数了。一个数 x (最大 10^5) 的因数数量是很少的（最多一百多个），这样我们的 DP 状态就不会爆炸啦！

最终的算法流程

所以，我们的完整策略是：

1. 预处理：先把 x 的所有因数找出来，存到一个 set 里，方便后面快速查询。
2. 初始化：我们准备一个 dp_set，用来存放当前段能凑出的所有乘积（它们必须是 x 的因数）。一开始，段是空的，只有一个“空集”乘积，也就是 1。所以 dp_set = {1}。我们还需要一个计数器 segments，初始为 0。
3. 遍历卡片：从左到右处理每张卡片 a[i]。
   • 首先判断 a[i] 是否是 x 的因数。如果不是，它很安全，直接跳过，对我们 dp_set 的状态没有影响。
   • 如果是 x 的因数，我们就遍历 dp_set 中已有的所有乘积 d。计算新乘积 nxt = d * a[i]。
   • 如果 nxt 也是 x 的因数，就把它加入一个临时的 new_set。
   • 在加入过程中，如果发现 nxt 恰好等于 x，就说明出问题了！加入 a[i] 会让当前段变 “好”。
   • 触发切割：一旦发现能凑出 x，我们就必须切割。segments 加一，然后重置 dp_set，开启一个新段。新段从 a[i] 开始，所以新段能凑出的乘积集合就是 {1, a[i]}。
   • 安全扩展：如果没有凑出 x，说明加入 a[i] 是安全的。我们就用包含新乘积的 new_set 来更新我们的 dp_set，然后继续处理下一张卡片。
4. 收尾工作：当所有卡片都处理完后，我们手中正在构建的最后一段也需要被算上。所以最终答案是 segments + 1。

这样，我们就能用最少的段数把所有卡片分完啦，喵~

代码实现，看我的魔法！

#include <iostream>
#include <vector>
#include <set>
#include <cmath>

using namespace std;

void solve() {
    int n, x;
    cin >> n >> x;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    // 喵~ 先把 x 的所有因数都找出来，存到一个 set 里，方便我们快速查找！
    // 这样就不用每次都做取模运算了。
    vector<int> divisors;
    int sqrt_x = sqrt(x);
    for (int i = 1; i <= sqrt_x; i++) {
        if (x % i == 0) {
            divisors.push_back(i);
            if (i != x / i) {
                divisors.push_back(x / i);
            }
        }
    }
    set<int> D_set(divisors.begin(), divisors.end());

    int segments = 0;
    // dp_set 记录了在当前这个“坏”段里，我们能凑出来的所有乘积。
    // 当然，这些乘积都得是 x 的因数才有意义。
    set<int> dp_set;
    // 一开始，一个数都不选，乘积就是 1 啦。
    dp_set.insert(1);

    // 遍历每一张卡片~
    for (int i = 0; i < n; i++) {
        // 如果 a[i] 连 x 的因数都不是，那它肯定没法参与构成 x，
        // 对我们构不成威胁，可以安全地留在当前段，不用更新 dp_set。
        // （注意：原题中 a[i] != x，但它可能是 x 的因数）
        if (x % a[i] != 0) {
            continue;
        }

        set<int> new_set = dp_set;
        bool formed_x = false;

        // 看看把 a[i] 加进来，会产生什么新的乘积。
        // 遍历当前段已经能凑出的所有乘积 d。
        for (int d : dp_set) {
            // 这是一个小优化，防止乘法溢出，也避免了不必要的计算。
            if (d > x / a[i]) {
                continue;
            }
            int nxt = d * a[i];
            
            // 新的乘积 nxt 也必须是 x 的因数才有用哦。
            if (D_set.count(nxt)) {
                new_set.insert(nxt);
                // 哇！我们凑出 x 了！
                if (nxt == x) {
                    formed_x = true;
                }
            }
        }
        
        // 如果凑出了 x...
        if (formed_x) {
            // 这说明当前这张卡片 a[i] 不能再呆在旧的段里了，它太“危险”了。
            // 所以我们切一刀，段数+1。
            segments++;
            // 然后开启一个全新的段。
            // 新段的初始状态是只包含一个空集，乘积为 1。
            dp_set = set<int>{1};
            
            // 这个新段从 a[i] 开始，所以要把 a[i] 的影响加进去。
            // 新段能凑出的乘积就是 {1, a[i]} (如果 a[i] 是 x 的因数)。
            // 这部分代码实现了这个逻辑。
            set<int> temp_set = dp_set;
            if (a[i] <= x && D_set.count(a[i])) {
                temp_set.insert(a[i]);
            }
            dp_set = temp_set;

        } else {
            // 如果没凑出 x，太好了！这个段还是“坏”的。
            // 我们就用包含了新乘积的 new_set 更新 dp_set，继续扩展这个段。
            dp_set = new_set;
        }
    }

    // 别忘了最后正在处理的那个段也要算上哦！
    segments++;
    cout << segments << '\n';
}

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

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

复杂度分析，算算账喵！

• 时间复杂度: O(N * d(x) * log(d(x))) 的说。

  • N 是卡片数量。
  • d(x) 是 x 的因数个数。对于 x <= 10^5，d(x) 是一个很小的数（最大为128）。
  • 在遍历 N 张卡片时，对于每一张卡片，我们都要遍历 dp_set。dp_set 的大小不会超过 d(x)。每次向 set 中插入元素需要 log(d(x)) 的时间。
  • 预处理所有因数的时间是 O(sqrt(x))。
  • 总的来说，这个复杂度对于本题的数据范围是完全可以接受的！

• 空间复杂度: O(d(x)) 的说。

  • 我们主要的空间开销是存储 x 的因数的 D_set 和动态规划状态的 dp_set。它们的大小都不会超过 d(x)。

知识点与总结，小猫咪的智慧锦囊！

这道题真有趣，融合了好几种思想呢！

1. 核心思想：贪心。首先要想到，要使段数最少，就得让每段尽可能长。这个贪心策略是解题的大方向。
2. 关键优化：数论性质。利用 “乘积为 x 的所有因子都必须是 x 的因数” 这一性质，极大地缩小了 DP 的状态空间，是本题能通过的命门所在！以后遇到乘积类的题目，一定要多往因数、质因数分解这些方向想一想哦。
3. 实现工具：DP + Set。用动态规划的思想来维护“当前可凑出的乘积集合”，并用 std::set 这个数据结构来存储，既能自动去重，又能快速查找，非常方便。
4. 注意边界：最后一段。这种分段问题，要特别小心最后一段的处理。我们的循环逻辑是在“段的末尾”进行计数，所以循环结束后，正在进行中的最后一段需要手动加上。

希望这篇题解能帮到主人 sama！解题就像寻宝一样，只要有耐心和正确的方法，总能找到答案的！加油喵~！