前言
本次选拔赛覆盖我们培训的三个梯队（基础组、提高组、核心组）的知识点，难度比正赛高了一个档次，我听很多人说比赛的后六题连题目都看不懂，其实这是我故意而为之的，我需要让大家明白算法竞赛的真实难度，不能让大家以过于乐观的态度去学习算法竞赛的知识，同时也为了激励大家，让大家看到更高的山，从而有更高的目标。
题解
本次题解仅包含比赛中的 F 到 L 题目，对于其它题目不做展开。
J 题涉及到数据结构“线段树”，由于没人学过，三言两语也讲不清，因此这里同样不对 J 题进行解析。
F. 卢思吕的难题
- 难度：Easy，普及-
- 考点：数论
- 时间复杂度：$O(\sqrt{N})$
能写到这题的人，应该对于基本的输入输出都已经掌握了，我就不对这题的格式化输出做展开，因此实际难点只有一个：给定数字 $n$，如何分解出它的全部质因子。
显然我们有一个方法，枚举从 $1$ 到 $n$ 的全部数字，然后对于每一个数字判断是否为 $n$ 的因数，再判断它是否是素数，显然这么做的时间复杂度至少为 $O(N)$，但是题目的 $n$ 的最大值高达 $10^9$ ，即使我们将判断素数的操作做到了 $O(1)$ 的时间复杂度也必然会 TLE（超时）。
试除法
所以我就要给大家介绍一个方法了，它叫做“试除法”，字如其名，算法的核心操作就是判断一个数字是否能整除当前 $n$ ，如果能就一直让 $n$ 除以这个数，直到这个数字不能整除当前 $n$（ $n$ 在操作中实际上是被改变了的），容易证明这样做得到的数字必然是 $n$ 的质因子（我们从 $2$ 开始试除，相当于把所有 $n$ 的能被 $2$ 整除的因子给除掉了，然后从 $3$ 开始循环这个步骤，显然往后出现的一切能整除当前 $n$ 的数字一定是质数，并且由于能整除 $n$ 因此它一定是 $n$ 的因子，因此它就是 $n$ 的质因子）。
证明1
显然我们枚举的起点是 $2$ ，但是终点应该设为多少呢？如果我们将终点设为 $n$ 的话，显然又一次掉入了时间复杂度陷阱，接下来我们只需要简单证明：$n$ 的质因子中，大于 $\sqrt{n}$ 的最多不会超过一个。采取反证法证明，假设 $n$ 有两个大于 $\sqrt{n}$ 的质因子 $x, y$ ，我们知道一切素数都是互质的，又因为 $x, y$ 是 $n$ 的因子，因此显然有 $n \ge a \times b$，但是又有 $a, b > \sqrt{n}$，显然这个不等式是不可能成立的，因此前提条件不成立，证毕。
证明2
故枚举终点可以设为 $\sqrt{n}$，最后再检查一次 $n$ 是否变成了 $1$，如果 $n$ 没有变成 $1$，它必然就是 $n$ 的一个质因子，这里如果有人不明白，我们也做一个简单证明：显然，我们只需要证明剩下的这个数字必然是一个素数，因为我们刚才的操作显然已经把全部小于等于 $\sqrt{n}$ 的质因子筛完了，因此剩下的这个数字若为合数，则它的因子必定只有大于 $\sqrt{n}$ 的质因子（任何合数都能表示为若干个素数的乘积，因此之前的试除过程实际上已经把这个数的全部合数因子筛完了），刚才已经证明过了一个数最多只有一个质因子能大于这个数的平方根的值，因此这个数字剩下的因子里最多只有一个质因子，显然它必然有至少一个因子，因此它的质因子就是它自己，故证明得到这个数一定为素数。
综上，我们用一长串的数学证明得出了一个时间复杂度为 $O(\sqrt{N})$ 的算法可以找出一个数的全部质因子。
std (C)
#include <stdio.h>
int main()
{
int n;
scanf("%d", &n);
printf("%d =", n);
int first = 1;
for (int i = 2; i * i <= n; ++i)
{
while (n % i == 0)
{
if (first)
{
printf(" %d", i);
first = 0;
}
else
{
printf(" * %d", i);
}
n /= i;
}
}
if (n > 1)
{
if (first)
{
printf(" %d", n);
}
else
{
printf(" * %d", n);
}
}
return 0;
}G. 612的取舍之道
- 难度：Medium，普及-
- 考点：枚举、前缀和
- 时间复杂度：$O(N)$
题目对姚淞议的每次操作的描述看似很复杂，但是由于题目只问最终状态，因此我们根本不需要管中间过程姚淞议做了什么操作，我们只需要知道最后会剩下什么就行，显然题目可以简述为给定数组 $a$，从其左端和右端分别截取一段连续的子数组合并成一个新的数组 $b$，使得数组 $b$ 的长度为 $k$，试问如何最大化操作后的数组 $a, b$ 的 $max(\sum a, \sum b)$。
于是我们容易发现，我们只需要枚举 $b$ 的其中一个截断点的位置，然后通过公式算出另一个截断点的位置，再使用前缀和快速统计操作后的两个数组的和并取其中的 $max$ 记为这次操作的得分，最后取全部枚举点的得分的最值并输出即可。
std (C++)
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
void solve()
{
int n, k;
cin >> n >> k;
vector<ll> a(n);
vector<ll> pref_sum(n + 1);
for (int i = 0; i < n; ++i)
{
cin >> a[i];
pref_sum[i + 1] = pref_sum[i] + a[i];
}
ll ans = 0;
for (int i = n - k; i <= n; ++i)
{
ll sum = pref_sum[i] - pref_sum[i - n + k];
ans = max(ans, max(sum, pref_sum.back() - sum));
}
cout << ans << '\n';
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--)
{
solve();
}
}H. 我想睡觉
- 难度：Medium，普及
- 考点：数学，哈希
- 时间复杂度：$O(n\log n)$
这道题会用到一个很常见的思想：把某个值出现了多少次记录下来，然后在之后快速查询。
这种做法通常被称为哈希。
map 和 unordered_map
在 C++ 中，比较常见的用于记录“某个值出现次数”的容器有 map 和 unordered_map。
例如：
map<int, int> cnt;
cnt[5]++;
cnt[10]++;
cout << cnt[5];这里可以把 cnt[x] 理解为：值 $x$ 出现了多少次。
map 和 unordered_map 都可以完成这种操作，但它们的实现方式不同。
map 的底层通常是红黑树，因此插入和查询的时间复杂度都是
$$
O(\log n)
$$
而 unordered_map 的底层是哈希表，理想情况下插入和查询的平均时间复杂度为
$$
O(1)
$$
看起来 unordered_map 更快，但它存在哈希冲突的问题。
当大量不同的数被映射到相同的位置时，unordered_map 的效率会明显下降，最坏情况下单次操作甚至可能退化到
$$
O(n)
$$
在算法竞赛中，有些特殊数据甚至可以专门构造哈希冲突，使 unordered_map 出现非常严重的退化。
因此，如果没有特殊需求，一般更推荐直接使用 map。虽然理论复杂度多一个 $\log n$，但复杂度稳定，不容易因为特殊数据出现意外问题。
所以在之后的题目中，如果只是需要维护“某个值出现了多少次”，我们默认优先考虑 map。
式子的转化
题目要求统计满足
$$
|a_i-a_j-k|=i-j,\quad j<i
$$
的下标对 $(i,j)$。
因为 $j<i$，所以
$$
i-j>0
$$
接下来考虑把绝对值拆开。
绝对值满足
$$
|x|=y
$$
等价于
$$
x=y
$$
或者
$$
x=-y
$$
因此原式可以分成两种情况。
情况一
当
$$
a_i-a_j-k=i-j
$$
移项得到
$$
a_i-i=a_j+k-j
$$
对于当前的位置 $i$，左边的
$$
a_i-i
$$
已经确定。
所以我们只需要知道，在之前的位置中，有多少个 $j$ 满足
$$
a_j+k-j=a_i-i
$$
于是可以使用一个 map：
map<int, int> cnt1;令
cnt1[x]表示之前有多少个位置 $j$ 满足
$$
a_j+k-j=x
$$
那么当前位置产生的答案就是
cnt1[num - i]情况二
当
$$
a_i-a_j-k=-(i-j)
$$
移项得到
$$
a_i+i=a_j+k+j
$$
同样，对于当前的位置 $i$，我们需要知道之前有多少个 $j$ 满足
$$
a_j+k+j=a_i+i
$$
所以再使用一个 map：
map<int, int> cnt2;令 cnt2[x] 表示之前有多少个位置满足
$$
a_j+k+j=x
$$
那么当前位置产生的贡献就是
cnt2[num + i]因此，从左到右枚举每一个位置 $i$。
首先查询当前位置能够和多少个之前的位置组成答案：
ans += cnt1[num - i] + cnt2[num + i];然后将当前位置的信息加入 map：
cnt1[num + k - i]++;
cnt2[num + k + i]++;这里必须先查询，再插入。
因为题目要求
$$
j<i
$$
在处理位置 $i$ 时，map 中只能保存位置 $1\sim i-1$ 的信息。
std (C++)
#include <bits/stdc++.h>
using i128 = __int128;
using ll = long long;
using ull = unsigned long long;
using de = double;
using ld = long double;
using namespace std;
void solve()
{
int n, k; cin >> n >> k;
map<int, int> cnt1, cnt2;
ll ans = 0;
for (int i = 1; i <= n; ++i)
{
int num; cin >> num;
ans += cnt1[num - i] + cnt2[num + i];
cnt1[num + k - i]++;
cnt2[num + k + i]++;
}
cout << ans;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
while (t--)
{
solve();
}
}使用 map 时，每一次查询和插入的时间复杂度都是 $O(\log n)$，因此总时间复杂度为
$$
O(n\log n)
$$
空间复杂度为
$$
O(n)
$$
不使用 map 能不能做？
实际上，这道题甚至没有必要使用 map。
我们使用 map 的原因，是因为需要记录某个整数出现了多少次，而这些整数看起来可能比较分散。
但这道题中的数值范围其实非常小。
考虑 cnt1 中存储的值：
$$
a_i+k-i
$$
因为
$$
1\le a_i\le n
$$
$$
0\le k\le n
$$
$$
1\le i\le n
$$
所以最小值为
$$
1+0-n=1-n
$$
最大值为
$$
n+n-1=2n-1
$$
因此
$$
1-n\le a_i+k-i\le 2n-1
$$
可以发现，这些数的绝对值最多只是 $O(n)$ 级别。
所以我们完全可以直接开一个数组：
vector<int> cnt1(4 * n + 20);然后让数组下标直接代表某个数出现了多少次。
但是这里存在一个问题：
$$
a_i+k-i
$$
有可能是负数。
例如某个值为 $-3$，显然不能写成：
cnt1[-3]因为数组下标不能是负数。
解决方法也很简单：给所有值统一加上一个偏移量。
例如令
int offset = n + 5;那么原本的值 $x$ 就存放在
cnt[x + offset]中。
例如原来的 $-3$，实际访问的是
$$
-3+(n+5)
$$
这样数组下标就变成了非负数。
这种方法可以理解为一种最简单的“数组哈希”。
再来看 cnt2 中需要存储的值：
$$
a_i+k+i
$$
其最大值为
$$
n+n+n=3n
$$
如果同样加上 offset=n+5，最大下标大约就是
$$
4n
$$
因此开
vector<int> cnt1(4 * n + 20);
vector<int> cnt2(4 * n + 20);就完全足够。
查询时：
ans += cnt1[num - i + offset];
ans += cnt2[num + i + offset];插入时：
cnt1[num + k - i + offset]++;
cnt2[num + k + i + offset]++;于是可以得到不使用 map 的写法：
std (不使用map)
#include <bits/stdc++.h>
using i128 = __int128;
using ll = long long;
using ull = unsigned long long;
using de = double;
using ld = long double;
using namespace std;
void solve()
{
int n, k; cin >> n >> k;
int offset = n + 5;
vector<int> cnt1(4 * n + 20);
vector<int> cnt2(4 * n + 20);
ll ans = 0;
for (int i = 1; i <= n; ++i)
{
int num; cin >> num;
ans += cnt1[num - i + offset];
ans += cnt2[num + i + offset];
cnt1[num + k - i + offset]++;
cnt2[num + k + i + offset]++;
}
cout << ans;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
while (t--)
{
solve();
}
}因为数组可以直接通过下标访问，每一次查询和修改的时间复杂度都是
$$
O(1)
$$
所以这种写法的总时间复杂度可以做到
$$
O(n)
$$
空间复杂度为
$$
O(n)
$$
这种写法的本质就是：
如果需要哈希的值范围本身只有 $O(n)$，就不一定需要使用 map，可以直接利用数组下标记录每个值出现的次数。
如果值可能为负数，就统一加上一个足够大的偏移量，将整个值域平移到非负数范围内。
I. 记忆的残响与约定的彼方
- 难度：Medium，普及
- 考点：数论，质因数分解，计数
- 时间复杂度：$O(\sum \sqrt{a_i}+10^6)$
“如果这些记忆终究会消失，那么至少在它们彻底散去之前，确认它们是否曾经与谁产生过共鸣吧。”
这道题的背景来自《末日时在做什么？有没有空？可以来拯救吗？》，一般也简称《末日三问》。
故事发生在一个已经失去地面的世界，人类早已灭亡，幸存的种族生活在漂浮于天空中的浮空岛上。珂朵莉等黄金妖精作为能够使用圣剑的“兵器”，承担着与“兽”战斗的命运。
而这道题中，我们不需要去面对第六兽，也不需要思考黄油蛋糕到底应该放多少糖。
我们只需要替威廉做一件简单得多的事情：
看看这些散落的数字之间，是否还有共同的部分。
什么叫“共鸣”？
题目规定，如果两个数 $a_i,a_j$ 满足
$$
\gcd(a_i,a_j)>1
$$
那么它们就是“共鸣”的。
例如：
$$
\gcd(6,15)=3
$$
因此 $6$ 和 $15$ 共鸣。
而
$$
\gcd(5,7)=1
$$
所以 $5$ 和 $7$ 不共鸣。
那么问题就变成了：
是否存在两个不同的数，它们拥有至少一个相同的质因子？
这是因为，如果
$$
\gcd(a_i,a_j)>1
$$
那么它们的最大公约数中一定至少包含一个质数。
反过来，如果两个数拥有相同的质因子 $p$，那么
$$
p\mid a_i
$$
并且
$$
p\mid a_j
$$
因此一定有
$$
\gcd(a_i,a_j)\ge p>1
$$
所以这两个条件实际上是完全等价的。
一个最直接的想法
我们当然可以直接枚举所有的 $(i,j)$，然后计算
gcd(a[i], a[j])如果某一对的最大公约数大于 $1$，就输出 YES。
但是一共有
$$
\frac{n(n-1)}{2}
$$
对数。
当
$$
n=10^5
$$
时，显然无法接受。
所以我们不能去问：
“每两个碎片之间有没有共鸣？”
而应该换一个角度：
“每一种质因子，曾经出现在哪些碎片中？”
这样问题就简单很多了。
分解质因数
例如有一个数
$$
60
$$
它可以分解为
$$
60=2^2\times3\times5
$$
我们其实并不关心质因子 $2$ 出现了两次。
因为题目只关心：
有没有另外一个数也包含质因子 $2$？
所以对于每个数，我们只需要记录它有哪些不同的质因子。
例如 $60$ 只需要记录：
$$
2,3,5
$$
不需要记录成：
$$
2,2,3,5
$$
因此我们准备一个数组：
vector<int> cnt(1e6 + 1);其中
cnt[p]表示：
有多少个数组中的数包含质因子 $p$。
例如：
6 10 15分解以后：
$$
6=2\times3
$$
$$
10=2\times5
$$
$$
15=3\times5
$$
那么最后会得到：
cnt[2] = 2
cnt[3] = 2
cnt[5] = 2此时只要发现存在某个质数 $p$ 满足
$$
cnt[p]>1
$$
就说明至少有两个数拥有相同的质因子。
也就说明至少有一对数满足
$$
\gcd(a_i,a_j)>1
$$
答案就是 YES。
否则答案就是 NO。
如何分解一个数
在前面的 F 题中已经展开介绍过“试除法”，若有不懂前往 F 题的题解查看即可。
Lambda 表达式
std 中分解质因数的代码写成了：
auto factor = [&](int num) -> void
{
...
};这种写法叫做 Lambda 表达式。
可以暂时把它理解成：
在一个函数内部临时定义了另一个小函数。
如果以前没有接触过 Lambda，可以把它近似看成下面这种普通函数：
void factor(int num)
{
...
}只不过 Lambda 可以直接写在 solve() 内部，而且能够方便地使用 solve() 中已经定义的变量。
这段代码中：
[&]表示以引用的方式使用外部变量。
因此 Lambda 内部可以直接修改：
cnt例如：
cnt[i]++;这里修改的就是 solve() 中真正的 cnt。
接下来：
(int num)就是参数列表，和普通函数没有区别。
而：
-> void表示这个 Lambda 没有返回值。
最后：
factor(a[i]);就和调用普通函数一样。
所以：
auto factor = [&](int num) -> void
{
...
};完全可以简单理解为：
定义了一个叫
factor的小函数，用来分解num的质因子，并把结果记录到cnt中。
如果暂时不熟悉 Lambda，也不影响理解这道题的核心算法。
整体过程
对于每一个数 $a_i$：
- 对 $a_i$ 进行质因数分解；
- 找出它所有不同的质因子；
- 对每一个质因子 $p$ 执行
cnt[p]++。
全部处理完成以后，再检查：
cnt[p] > 1是否对某个 $p$ 成立。
如果成立，说明至少有两个数同时包含质因子 $p$，输出：
YES否则所有数之间都不存在共同质因子，输出：
NO就像那些正在逐渐消失的记忆一样，我们并不需要知道每一块碎片完整的过去。
只需要确认：
是否有某一种相同的东西，曾经同时存在于两块碎片之中。
在这道题里，这个“相同的东西”就是共同的质因子。
复杂度分析
对于每一个 $a_i$，我们最多枚举到 $\sqrt{a_i}$，因此质因数分解部分的复杂度可以写成
$$
O\left(\sum_{i=1}^{n}\sqrt{a_i}\right)
$$
由于
$$
a_i\le10^6
$$
所以
$$
\sqrt{a_i}\le1000
$$
在本题的数据范围内完全可以通过。
最后还需要枚举一次 cnt：
for (int i = 2; i <= 1e6; ++i)因此单组数据的复杂度可以写成
$$
O\left(\sum_{i=1}^{n}\sqrt{a_i}+10^6\right)
$$
空间复杂度为
$$
O(10^6)
$$
std (C++)
#include <bits/stdc++.h>
using i128 = __int128;
using ll = long long;
using ull = unsigned long long;
using de = double;
using ld = long double;
using namespace std;
void solve()
{
int n; cin >> n;
vector<int> a(n); for (int i = 0; i < n; ++i) cin >> a[i];
vector<int> cnt(1e6 + 1);
auto factor = [&](int num) -> void
{
for (int i = 2; i * i <= num; ++i)
{
if (num % i == 0)
{
cnt[i]++;
while (num % i == 0) num /= i;
}
}
if (num > 1) cnt[num]++;
};
for (int i = 0; i < n; ++i)
{
factor(a[i]);
}
bool ans = false;
for (int i = 2; i <= 1e6; ++i)
{
if (cnt[i] > 1)
{
ans = true;
break;
}
}
cout << (ans ? "YES\n" : "NO\n");
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
cin >> t;
while (t--)
{
solve();
}
}K. 群星：策展人的交易
- 难度：Hard，普及+/提高−
- 考点：子集枚举，贪心，背包，二进制拆分
- 时间复杂度：Subtask 1 为 $O(31\cdot2^n)$，满分做法在 $\sum p_i\le10^5$ 时主要为 $O(n\sum p_i)$
策展人的交易中枢最麻烦的地方并不是“钱够不够”。
它要求的是：
支付金额必须和商品总价完全相等。
例如我们有 $100$ 能量币，但如果只能凑出 $0,8,16,24,\dots$，那么一件价格为 $7$ 的商品照样买不了。
同时，题目允许我们把很多件商品合并成一次订单。
所以真正需要判断的是：
能不能选择若干件商品，使它们的价格总和恰好能够被现有的能量币凑出来？
这道题被放在 Hard，主要原因是满分做法需要根据不同的数据范围选择不同算法。
不过对于目前的学习阶段，最重要的是把 Subtask 1 完全弄明白。
后面的 Subtask 涉及背包和二进制拆分，如果暂时看不懂并没有关系，只需要知道整体思路即可。相比于强行追求满分，把前 $20$ 分对应的算法真正理解清楚更加重要。
Subtask 1：$n\le20$
Subtask 1 的限制为：
$$
n\le20
$$
商品的价格虽然可能非常大：
$$
p_i\le10^9
$$
但是商品数量非常少。
看到
$$
n\le20
$$
应该首先想到一个非常重要的复杂度：
$$
2^n
$$
因为
$$
2^{20}=1048576
$$
大约只有一百万。
这意味着，我们可以直接枚举：
到底购买哪些商品。
用二进制表示选择方案
假设有 $4$ 件商品。
我们可以用一个四位二进制数表示选择情况。
例如：
0000表示一件商品都不买。
0101表示购买第 $1$ 件和第 $3$ 件商品。
1111表示全部购买。
对于 $n$ 件商品，一共有
$$
2^n
$$
种不同的选择方案。
因此，只需要枚举：
for (int mask = 1; mask < (1 << n); ++mask)然后求出这个方案购买了多少件商品，以及商品总价格是多少。
接下来只剩下一个问题：
这个总价格能不能用我们的能量币精确凑出来？
如何判断一个金额能不能精确支付？
题目有一个非常特殊的条件：
所有能量币的面额都是
$$
2^x
$$
也就是：
$$
1,2,4,8,16,32,\dots
$$
这是一个非常强的性质。
假设现在需要支付金额 $s$。
我们可以从最大的面额开始考虑。
如果现在有若干枚面额为 $2^i$ 的能量币，那么最多可以使用：
$$
\left\lfloor\frac{s}{2^i}\right\rfloor
$$
枚，否则金额就会超过 $s$。
所以实际使用数量为：
$$
\min\left(c_i,\left\lfloor\frac{s}{2^i}\right\rfloor\right)
$$
直接尽可能多地使用当前最大的面额即可。
代码就是：
for (int i = 30; i >= 0; --i)
{
ll v = 1LL << i;
ll take = min(coin[i], s / v);
s -= take * v;
}最后如果：
s == 0说明可以精确支付。
否则就不能。
为什么可以贪心？
这里最关键的是：
$$
2^i=2\times2^{i-1}
$$
每一种面额都恰好是下一种面额的两倍。
假设存在一个合法方案，但是它没有尽可能多地使用某个较大的面额 $2^i$。
既然总金额仍然能够凑出来，那么少使用的这一枚 $2^i$，就一定需要用若干枚更小的 $2$ 的幂来补上。
而这些较小面额的总价值恰好为：
$$
2^i
$$
因此我们完全可以把这一部分较小面额替换成一枚 $2^i$。
换句话说：
如果一个金额存在合法支付方案，那么一定存在一个方案，使得它从大到小尽可能多地使用每一种面额。
所以从大面额到小面额贪心不会错。
这也是题目把面额限制为 $2^x$ 的真正意义。
如果面额是随便给的，例如：
$$
1,3,4
$$
那么这种贪心就不一定成立。
保存每种能量币
因为：
$$
0\le x_i\le30
$$
所以根本不需要 map。
直接开一个长度为 $31$ 的数组：
array<ll, 31> coin{};如果输入：
3 5表示有 $5$ 枚面额为：
$$
2^3=8
$$
的能量币。
于是：
coin[3] = 5;这样之后判断某个金额时，从 $30$ 枚举到 $0$ 即可。
枚举商品子集
最容易理解的方法，是对于每一个 mask 再枚举一次所有商品：
ll sum = 0;
int cnt = 0;
for (int i = 0; i < n; ++i)
{
if (mask >> i & 1)
{
sum += p[i];
cnt++;
}
}这样可以通过 Subtask 1。
复杂度为：
$$
O(n2^n)
$$
因为 $n\le20$，完全可以接受。
不过 std 中使用了一个稍微更快的写法。
对于一个状态：
mask我们找到它最低位的一个 $1$。
可以使用：
int bit = __builtin_ctz(mask);__builtin_ctz(mask) 会返回 mask 二进制末尾连续有多少个 $0$，也就等价于最低位的 $1$ 在第几位。
然后通过：
int pre = mask & (mask - 1);删掉最低位的这个 $1$。
于是当前状态可以从 pre 转移而来：
s[mask] = s[pre] + p[bit];
cnt[mask] = cnt[pre] + 1;其中：
s[mask]表示这个商品集合的总价格。
而：
cnt[mask]表示购买了多少件商品。
这样每一个状态都可以在 $O(1)$ 的时间内计算出来。
Subtask 1 完整思路
枚举每一种商品集合：
for (int mask = 1; mask < (1 << n); ++mask)计算：
- 购买商品的数量；
- 商品价格总和。
假设总价格为 $s$。
然后从最大的能量币开始贪心判断：
check(s)如果能够精确支付，那么这个集合就是合法的。
更新答案：
ans = max(ans, cnt[mask]);最终得到最多可以购买多少件商品。
Subtask 1 代码 (C++)
#include <bits/stdc++.h>
using i128 = __int128;
using ll = long long;
using ull = unsigned long long;
using de = double;
using ld = long double;
using namespace std;
void solve()
{
int n, m; cin >> n >> m;
vector<ll> p(n);
for (int i = 0; i < n; ++i) cin >> p[i];
array<ll, 31> coin{};
for (int i = 0; i < m; ++i)
{
int x;
ll c;
cin >> x >> c;
coin[x] = c;
}
auto check = [&](ll s) -> bool
{
for (int i = 30; i >= 0; --i)
{
ll v = 1LL << i;
ll take = min(coin[i], s / v);
s -= take * v;
}
return s == 0;
};
int lim = 1 << n;
vector<ll> s(lim);
vector<int> cnt(lim);
int ans = 0;
for (int mask = 1; mask < lim; ++mask)
{
int bit = __builtin_ctz(mask);
int pre = mask & (mask - 1);
s[mask] = s[pre] + p[bit];
cnt[mask] = cnt[pre] + 1;
if (check(s[mask]))
{
ans = max(ans, cnt[mask]);
}
}
cout << ans << '\n';
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
while (t--)
{
solve();
}
}Subtask 1 时间复杂度：$O(31\cdot2^n)$
Subtask 1 空间复杂度：$O(2^n)$
对于 $n\le20$：
$$
2^n\le2^{20}\approx10^6
$$
所以可以顺利通过。
如果目前能够独立想到：
$n\le20\Rightarrow$ 枚举所有子集
并且能够理解：
面额全部为 $2^x\Rightarrow$ 可以从大到小贪心判断能否精确支付
那么这道题最值得掌握的部分就已经完成了。
剩余 Subtask
接下来的内容明显比 Subtask 1 更难。
如果目前还没有系统学习过背包问题，这一部分知道思路即可，不要求现在就能够独立写出来。
这道 Hard 题本身就是用来拉开分数差距的，没有必要为了拿满分而强行提前学习大量超出当前阶段的内容。
先把 Subtask 1 的 $20$ 分稳稳拿到，比看懂一份自己还无法独立实现的满分代码更有意义。
当 $\sum p_i\le10^5$
后两个 Subtask 给出了一个非常重要的条件：
$$
\sum p_i\le10^5
$$
这一次商品数量可能达到：
$$
n=1000
$$
所以显然不能再枚举：
$$
2^n
$$
种商品集合。
但是总价格非常小。
于是可以换一个角度：
不再记录“选择了哪些商品”，而是记录“凑出价格 $s$ 最多可以买多少件商品”。
定义：
dp[s]表示：
商品价格总和恰好为 $s$ 时，最多能够选择多少件商品。
初始：
dp[0] = 0;对于每一个商品价格 $p_i$，进行一次 01 背包：
dp[s + p[i]] = max(dp[s + p[i]], dp[s] + 1);由于每件商品只能购买一次，所以需要从大到小枚举金额。
这样就能够知道：
对于每一个可能的总价格 $s$，最多可以买多少件商品。
能量币也做背包
另一边，我们还需要知道：
哪些金额能够被当前拥有的能量币精确支付？
定义：
can[s]表示金额 $s$ 是否能够被凑出。
问题在于一种能量币可能有：
$$
10^5
$$
枚。
显然不能真的把十万枚硬币一枚一枚做背包。
这里会使用一个比较常见的技巧：
二进制拆分。
例如有 $13$ 枚相同的硬币，可以拆成：
$$
1+2+4+6=13
$$
于是原本的 $13$ 枚相同硬币，被拆成了四组。
每一组只能选择一次，就可以转化成 01 背包。
std 中利用 bitset：
can |= can << w;快速维护能够凑出的金额。
这一部分如果第一次接触，看懂“把很多枚相同物品拆成若干组，再做 01 背包”的思想即可。
暂时不要求熟练掌握 bitset 的这种写法。
最后合并答案
商品背包得到：
dp[s]表示总价恰好为 $s$ 时最多可以买多少件。
能量币背包得到：
can[s]表示金额 $s$ 能否被精确支付。
所以最后只需要枚举所有金额：
if (can[s])
{
ans = max(ans, dp[s]);
}即可得到答案。
为什么满分代码需要分情况？
如果直接对金额做背包，那么需要依赖：
$$
\sum p_i\le10^5
$$
但是 Subtask 1 并没有这个限制。
在 Subtask 1 中：
$$
n\le20
$$
但是：
$$
p_i\le10^9
$$
所以可能出现：
$$
\sum p_i\approx2\times10^{10}
$$
显然不可能开这么大的 DP 数组。
因此两种数据范围实际上在提示两种完全不同的算法：
当：
$$
n\le20
$$
使用：
子集枚举。
当：
$$
\sum p_i\le10^5
$$
使用：
按金额背包。
这也是为什么做题时不能只看 $n$，而要把所有数据范围都认真读完。
有时候 Subtask 本身就在告诉你算法应该从哪里突破。
满分 std (C++)
下面给出完整代码。
这一部分如果暂时看不懂，不需要强行掌握。现阶段重点仍然是前面的 Subtask 1。
#include <bits/stdc++.h>
using i128 = __int128;
using ll = long long;
using ull = unsigned long long;
using de = double;
using ld = long double;
using namespace std;
const int MAXS = 100000;
void solve()
{
int n, m; cin >> n >> m;
vector<ll> p(n);
ll sum = 0;
for (int i = 0; i < n; ++i)
{
cin >> p[i];
sum += p[i];
}
array<ll, 31> coin{};
for (int i = 0; i < m; ++i)
{
int x;
ll c;
cin >> x >> c;
coin[x] = c;
}
auto check = [&](ll s) -> bool
{
for (int i = 30; i >= 0; --i)
{
ll v = 1LL << i;
ll take = min(coin[i], s / v);
s -= take * v;
}
return s == 0;
};
if (sum <= MAXS)
{
bitset<MAXS + 1> can;
can[0] = 1;
for (int i = 0; i <= 30; ++i)
{
ll c = coin[i];
ll v = 1LL << i;
for (ll k = 1; c > 0; k <<= 1)
{
ll take = min(k, c);
c -= take;
ll w = take * v;
if (w <= sum) can |= can << w;
}
}
vector<int> dp(sum + 1, -1);
dp[0] = 0;
int cur = 0;
for (ll val : p)
{
int x = val;
for (int s = cur; s >= 0; --s)
{
if (dp[s] != -1)
{
dp[s + x] = max(dp[s + x], dp[s] + 1);
}
}
cur += x;
}
int ans = 0;
for (int s = 0; s <= sum; ++s)
{
if (can[s])
{
ans = max(ans, dp[s]);
}
}
cout << ans << '\n';
}
else
{
int lim = 1 << n;
vector<ll> s(lim);
vector<unsigned char> cnt(lim);
int ans = 0;
for (int mask = 1; mask < lim; ++mask)
{
int bit = __builtin_ctz(mask);
int pre = mask & (mask - 1);
s[mask] = s[pre] + p[bit];
cnt[mask] = cnt[pre] + 1;
if (cnt[mask] > ans && check(s[mask]))
{
ans = cnt[mask];
}
}
cout << ans << '\n';
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
while (t--)
{
solve();
}
}满分思路：根据数据范围分别使用子集枚举与背包。
当 $n\le20$ 时：使用 $O(31\cdot2^n)$ 的子集枚举。
当 $\sum p_i\le10^5$ 时：使用商品 01 背包 + 能量币二进制拆分背包。
这道题真正希望掌握的，不只是某一种具体算法，而是看到不同限制时能够意识到：
$$
n\text{ 很小}\Rightarrow 2^n
$$
而：
$$
\sum p_i\text{ 很小}\Rightarrow \text{按总和设计 DP}
$$
这两种观察在后面的题目中都会反复出现。
L. 苏菲的炼金工坊
- 难度：Hard，普及+/提高−
- 考点：图论建模，最短路，广度优先搜索
- 时间复杂度：$O(nS\log A)$，其中 $S$ 为实际访问到的不同 gcd 状态数，$A=\max a_i$
这道题最后一题的重点并不是 gcd 本身，也不是 BFS 模板，而是一个非常重要的能力：
把原问题建模成一张图，再把“最少操作次数”转化成最短路问题。
很多图论题的题面里并不会直接告诉你“这里有一张图”。
有时没有点，没有边，甚至完全看不到图论的影子。
这道题就是一个很典型的例子。
从一次炼金操作开始
假设我们现在已经得到了一块杂质浓度为 $x$ 的矿石。
如果选择一块原始矿石 $a_i$ 与它进行融合，那么新的杂质浓度会变成：
$$
\gcd(x,a_i)
$$
同时，我们进行了一次操作。
也就是说：
如果当前状态是 $x$，那么经过一次操作，可以到达状态 $\gcd(x,a_i)$。
写成：
$$
x\rightarrow\gcd(x,a_i)
$$
这就是本题最关键的一步。
图论建模
我们把：
当前能够得到的矿石杂质浓度
看成图上的一个点。
例如：
1
2
3
4
5
...都可以是图上的状态。
对于一个状态 $x$，我们可以选择任意一块原始矿石 $a_i$ 进行融合。
于是存在一条边：
$$
x\rightarrow\gcd(x,a_i)
$$
例如原数组中存在：
6 10 15那么从状态 $6$ 出发：
$$
6\rightarrow\gcd(6,6)=6
$$
$$
6\rightarrow\gcd(6,10)=2
$$
$$
6\rightarrow\gcd(6,15)=3
$$
所以图中就存在：
6 -> 6
6 -> 2
6 -> 3其中自环：
6 -> 6显然不会让答案变优，可以直接忽略。
建模之后，问题变成最短路
题目要求：
最少进行多少次操作，才能得到杂质浓度为 $1$ 的矿石？
而我们建立的图中：
每经过一条边，就恰好代表进行一次炼金操作。
因此：
$$
\text{操作次数}=\text{经过的边数}
$$
于是原问题被转化成：
从初始状态出发，到达节点 $1$ 的最短路是多少？
这一步非常重要。
题目中的：
最少操作次数
在完成图论建模以后，就变成了图论中经典的：
最短路问题。
完整的思考过程就是：
炼金操作
↓
状态转移
↓
建立图
↓
最少操作次数
↓
最短路到这里以后，这道炼金题就已经变成一道标准的图论题。
为什么使用 BFS？
我们已经知道要求的是最短路。
接下来观察边权。
从：
$$
x
$$
转移到：
$$
\gcd(x,a_i)
$$
需要进行一次融合操作。
所以每一条边的代价都是：
$$
1
$$
也就是说，这是一张所有边权均为 $1$ 的图。
对于无权图或者所有边权相同的图，求最短路最经典的方法就是：
广度优先搜索 BFS。
因此这道题最终的算法就是：
图论建模 + 最短路 + BFS。
这里也可以记住一个非常重要的关系：
$$
\text{边权全部为 }1\Rightarrow\text{最短路可以使用 BFS}
$$
起点在哪里？
普通最短路一般只有一个起点。
但是这道题一开始就已经拥有：
$$
a_1,a_2,\dots,a_n
$$
这些矿石。
所以不需要进行任何操作，就已经可以得到浓度：
$$
a_i
$$
因此：
$$
dist[a_i]=0
$$
所有的 $a_i$ 都是起点。
所以这并不是普通的单源最短路，而是：
多源最短路。
对应到 BFS 中，就是一开始把所有起点同时放入队列：
for (int i = 0; i < n; ++i)
{
cin >> a[i];
dist[a[i]] = 0;
q.push(a[i]);
}这种写法称为：
多源 BFS。
可以把它理解成：
同时从所有初始矿石出发，寻找最快到达 $1$ 的路线。
dist 数组表示什么？
定义：
dist[x]表示：
从任意一块初始矿石出发，得到浓度恰好为 $x$ 的矿石，最少需要多少次融合。
开始时：
$$
dist[a_i]=0
$$
因为这些矿石本来就存在。
其余状态还没有访问过，所以初始化成一个很大的数：
vector<int> dist(1e5 + 1, 1e9);最终我们要求的就是：
dist[1]也就是到节点 $1$ 的最短距离。
BFS 的转移
假设当前从队列中取出了状态：
u说明我们已经能够用：
dist[u]次操作得到浓度 $u$。
现在选择任意一块原始矿石：
$$
a_i
$$
进行融合。
新的浓度为：
$$
\gcd(u,a_i)
$$
所以：
int num = gcd(a[i], u);这相当于从节点：
$$
u
$$
走了一条边，到达：
$$
num
$$
因为经过了一条边，也就是进行了一次操作，所以：
int cost = dist[u] + 1;如果这个距离比之前更短：
if (cost < dist[num])就进行更新：
dist[num] = cost;
q.push(num);完整转移为：
for (int i = 0; i < n; ++i)
{
int num = gcd(a[i], u);
int cost = dist[u] + 1;
if (cost < dist[num])
{
dist[num] = cost;
q.push(num);
}
}如果把 gcd 暂时忽略，这其实就是最普通的最短路转移：
for (所有从 u 出发的边)
{
int v = ...
int cost = dist[u] + 1;
if (cost < dist[v])
{
dist[v] = cost;
q.push(v);
}
}区别只在于：
这张图没有提前建立邻接表，而是通过 $\gcd(u,a_i)$ 现场计算出邻接点。
用样例理解这张图
考虑：
6 10 15 30开始时：
$$
dist[6]=0
$$
$$
dist[10]=0
$$
$$
dist[15]=0
$$
$$
dist[30]=0
$$
也就是有四个最短路起点。
假设 BFS 处理节点 $6$。
选择矿石 $10$：
$$
\gcd(6,10)=2
$$
所以图中存在一条边：
$$
6\rightarrow2
$$
因此：
$$
dist[2]=dist[6]+1=1
$$
接下来 BFS 处理节点 $2$。
选择矿石 $15$：
$$
\gcd(2,15)=1
$$
所以：
$$
2\rightarrow1
$$
得到：
$$
dist[1]=dist[2]+1=2
$$
对应的最短路就是：
$$
6\rightarrow2\rightarrow1
$$
一共经过两条边。
所以需要：
$$
2
$$
次操作。
这和题目中的炼金过程完全对应：
6 和 10 融合 -> 2
2 和 15 融合 -> 1为什么只记录 gcd 状态？
这里还有一个重要的问题。
我们在状态中只记录了：
当前浓度却没有记录：
之前到底用了哪些矿石为什么这样不会出错？
假设当前状态 $u$ 是通过若干块矿石不断取 gcd 得到的。
那么对于任何已经参与过融合的矿石 $a_i$，一定有：
$$
u\mid a_i
$$
所以：
$$
\gcd(u,a_i)=u
$$
如果再次使用这块已经参与过的矿石，只会得到：
$$
u\rightarrow u
$$
也就是一个自环。
状态完全不会改变。
因此：
重复使用已经参与过的矿石，不可能让我们更快得到 $1$。
所以没有必要记录：
哪些矿石已经使用只记录：
当前 gcd就足够描述对于答案有意义的信息。
这也是图论建模中非常重要的一点：
状态中只保留会影响后续决策的信息。
为什么第一次得到 1 就可以结束？
BFS 是按距离从小到大扩展状态的。
也就是说，它会依次处理：
距离 0 的状态
距离 1 的状态
距离 2 的状态
距离 3 的状态
...所以一旦：
dist[1] != 1e9说明节点 $1$ 已经被最短路访问到了。
此时：
dist[1]就是最少操作次数。
因此 std 中可以直接：
if (dist[1] != 1e9)
{
cout << dist[1] << '\n';
return;
}如果一开始就有 1 呢？
如果某个：
$$
a_i=1
$$
那么初始化的时候：
dist[1] = 0;也就是说：
不需要进行任何操作，就已经拥有绝对纯净结晶。
所以答案自然是：
0多源 BFS 会自然处理这种情况，不需要单独特判。
为什么题目保证一定有解？
题目保证：
$$
\gcd(a_1,a_2,\dots,a_n)=1
$$
而 gcd 满足结合律：
$$
\gcd(a_1,a_2,a_3)
=
\gcd(\gcd(a_1,a_2),a_3)
$$
推广以后：
$$
\gcd(a_1,a_2,\dots,a_n)
=
\gcd(\cdots\gcd(\gcd(a_1,a_2),a_3),\dots,a_n)
$$
所以只要不断进行融合，最终一定能够得到：
$$
1
$$
因此题目不存在无解情况。
这道题真正需要掌握的东西
这道题被放在 Hard，并不是因为 BFS 很难。
真正困难的是：
从题目操作中发现隐藏的图。
完整整理一次思考过程。
题目告诉我们：
$$
x\rightarrow\gcd(x,a_i)
$$
于是：
第一步：定义点
把每一个可能的杂质浓度 $x$ 看成一个点。
第二步：定义边
进行一次炼金操作：
$$
x\rightarrow\gcd(x,a_i)
$$
就是一条边。
第三步：发现边权
每次融合恰好消耗一次操作，所以：
$$
w=1
$$
第四步：转化目标
原问题要求：
最少操作多少次到达 $1$。
建图以后就是：
从所有初始节点 $a_i$ 到节点 $1$ 的最短路。
第五步：选择算法
因为所有边权都是 $1$：
$$
\text{最短路}\Rightarrow\text{BFS}
$$
又因为存在多个初始节点：
$$
\text{多源最短路}\Rightarrow\text{多源 BFS}
$$
所以整道题最终可以浓缩成：
$$
\boxed{
\text{炼金问题}
\rightarrow
\text{图论建模}
\rightarrow
\text{最短路}
\rightarrow
\text{多源 BFS}
}
$$
这才是这道题最重要的知识点。
如何判断一道题能不能建模成最短路？
以后看到：
最少操作次数
最少变化次数
最少移动次数
最少经过多少步
这一类描述时，可以尝试按照下面的顺序思考。
先问：
一个局面能不能表示成一个状态？
再问：
一次操作能不能让一个状态转移到另一个状态？
如果可以，那么：
一个状态就是一个点，一次操作就是一条边。
接下来如果题目要求的是：
最少操作次数
那么很自然就会转化成：
最短路。
最后再根据边权决定算法：
边权全部为 1
-> BFS
边权只有 0 和 1
-> 01 BFS
边权非负
-> Dijkstra这就是图论建模题中非常常见的一条思考链。
复杂度分析
设 BFS 实际访问到的不同 gcd 状态数量为 $S$。
对于每个状态 $u$，需要枚举全部 $n$ 个原始矿石：
gcd(u, a[i])一次 gcd 的复杂度为：
$$
O(\log A)
$$
其中：
$$
A=\max a_i
$$
因此总时间复杂度可以表示为：
$$
O(nS\log A)
$$
由于：
$$
1\le a_i\le10^5
$$
所有 gcd 状态也一定满足：
$$
1\le u\le10^5
$$
所以：
$$
S\le10^5
$$
空间主要由 dist 和 BFS 队列组成，因此为：
$$
O(A)
$$
std (C++)
#include <bits/stdc++.h>
using i128 = __int128;
using ll = long long;
using ull = unsigned long long;
using de = double;
using ld = long double;
using namespace std;
void solve()
{
int n; cin >> n;
queue<int> q; vector<int> dist(1e5 + 1, 1e9), a(n);
for (int i = 0; i < n; ++i) cin >> a[i], dist[a[i]] = 0, q.push(a[i]);
while (!q.empty())
{
if (dist[1] != 1e9)
{
cout << dist[1] << '\n';
return;
}
int u = q.front();
q.pop();
for (int i = 0; i < n; ++i)
{
int num = gcd(a[i], u);
int cost = dist[u] + 1;
if (cost < dist[num])
{
dist[num] = cost;
q.push(num);
}
}
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
cin >> t;
while (t--)
{
solve();
}
}这道题最值得记住的是：
$$
\boxed{x\rightarrow\gcd(x,a_i)}
$$
把当前 gcd 看成点，把一次融合看成边。
随后：
$$
\boxed{\text{最少操作次数}=\text{最短路长度}}
$$
又因为每条边的代价都是 $1$，最终使用多源 BFS 求最短路。