Loading... # 题目描述 在他最喜欢的咖啡馆里，Kmes再次想要尝试鱼子沙拉。以前，这对他来说并不困难，但是这家咖啡馆最近推出了一项新的购买政策。 现在，为了购买，Kmes需要解决以下问题：他面前摆放着$n$张价格不同的卡片，在第$i$张卡片上有一个整数$a_i$，在这些价格中没有一个整数$x$。 要求Kmes将这些卡片分成最少数量的坏段(使得每张卡片恰好属于一个段)。如果无法选择一个乘积等于$x$的卡片子集，则将一个段视为坏段。Kmes将卡片分成的所有段必须是坏段。 具体来说，如果段$(l, r)$是坏的，那么就没有索引$i_1 < i_2 < \ldots < i_k$，满足$l \le i_1, i_k \le r$，且$a_{i_1} \cdot a_{i_2} \ldots \cdot a_{i_k} = x$。 帮助Kmes确定为了享受他最爱的美食，最少需要多少坏段。 # 输入 **输入** 第一行包含一个整数 $t$ ($1 \le t \le 10^3$) — 测试用例的数量。 每组输入数据的第一行给出了 $2$ 个整数 $n$ 和 $x$ ($1 \le n \le 10^5, 2 \le x \le 10^5$) — 卡片的数量和整数。 每组输入数据的第二行包含了 $n$ 个整数 $a_i$ ($1 \le a_i \le 2 \cdot 10^5, a_i \neq x$) — 卡片上的价格。 保证所有测试数据中 $n$ 的总和不超过 $10^5$。 # 输出 **输入** 第一行包含一个整数 $t$ ($1 \le t \le 10^3$) — 测试用例的数量。 每组输入数据的第一行给出了 $2$ 个整数 $n$ 和 $x$ ($1 \le n \le 10^5, 2 \le x \le 10^5$) — 卡片的数量和整数。 每组输入数据的第二行包含了 $n$ 个整数 $a_i$ ($1 \le a_i \le 2 \cdot 10^5, a_i \neq x$) — 卡片上的价格。 保证所有测试数据中 $n$ 的总和不超过 $10^5$。 # 解题思路 本题有一个很明显的贪心的思路是： - 对于当前遍历到的$a[i]$， 优先将$a[i]$归结到上一个$[l, r]$ - 当$a[i]$无法归结到上一个$[l, r]$时，开一个新段 如此， 对于外层的遍历只需要执行$n$次 下一个要解决的问题是如何求得$a[i]$是否可以归结到上一个$[l, r]$： - 使用布尔数组$dp[k]$, 表示在$[l, r]$段中是否有元素相乘的结果等于$k$ - 初始化：$dp[x]$一定为真， 因为不能出现元素相乘等于$x$的情况 - 如果$x \% a[i] == 0$， 则要根据$dp[x / a[i]]$的真值分情况讨论： - 如果为真：则证明$a[i]$不可以属于这一段， 需要单开一段， 所以要清空状态信息$dp$并重新初始化 - 如果为假：则证明$a[i]$可以属于这一段，并对于所有$dp[k] == true$的$k$， 更新$dp[k * a[i]] = true$ 再不做优化的情况下， 便利的时间复杂度为$O(n^2)$， 因此需要对时间复杂度进行下面的优化： 注意到题目中的定义为$i_1 < i_2 < \ldots < i_k$，满足$l \le i_1, i_k \le r$，且$a_{i_1} \cdot a_{i_2} \ldots \cdot a_{i_k} = x$, **因此有$a_{i_1}, a_{i_2},..., a_{i_k}$只可能是$x$的因数** 所以可以对$x$做因数分解， 对于不属于$x$因数的$a[i]$可以不用考虑， 不会对坏段产生影响 # AC代码 ```cpp #include <cstdio> #include <cstdlib> #include <iostream> #include <vector> #include <algorithm> #define endl '\n' using namespace std; const int N = 2e5 + 10; int t; int n, x; int a[N]; bool dp[N]; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> t; while(t --) { cin >> n >> x; vector<int> factor; for(int i = 1; i <= x / i; i ++) { if(x % i == 0) { factor.push_back(i); if(i * i != x) factor.push_back(x / i); } } sort(factor.begin(), factor.end(), greater<int>()); for(auto t : factor) dp[t] = false; dp[1] = true; int ans = 1; for(int i = 1; i <= n; i ++) { cin >> a[i]; if(x % a[i]) continue; if(dp[x / a[i]]) { for(auto t : factor) dp[t] = false; dp[1] = dp[a[i]] = true; ans ++; } else { for(auto t : factor) { if(x % (t * a[i]) == 0) dp[t * a[i]] |= dp[t]; } } } cout << ans << endl; } return 0; } ``` 最后修改：2025 年 01 月 11 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏