[NOIP 2018 提高组] 货币系统
题目背景:NOIP 2018 提高组 D1 T2
题目描述
在网友的国度中共有 $n$ 种不同面额的货币,第 $i$ 种货币的面额为 $a[i]$,你可以假设每一种货币都有无穷多张。为了方便,我们把货币种数为 $n$、面额数组为 $a[1..n]$ 的货币系统记作 $(n, a)$。
在一个完善的货币系统中,每一个非负整数的金额 $x$ 都应该可以被表示出,即对每一个非负整数 $x$,都存在 $n$ 个非负整数 $t[i]$ 满足 $a[i] \times t[i]$ 的和为 $x$。然而, 在网友的国度中,货币系统可能是不完善的,即可能存在金额 $x$ 不能被该货币系统表示出。例如在货币系统 $n = 3$, $a = [2,5,9]$ 中,金额 $1, 3$ 就无法被表示出来。
两个货币系统 $(n, a)$ 和 $(m, b)$ 是等价的,当且仅当对于任意非负整数 $x$,它要么均可以被两个货币系统表出,要么不能被其中任何一个表出。
现在网友们打算简化一下货币系统。他们希望找到一个货币系统 $(m, b)$,满足 $(m, b)$ 与原来的货币系统 $(n,a)$ 等价,且 $m$ 尽可能的小。他们希望你来协助完成这个艰巨的任务:找到最小的 $m$。
输入格式
输入文件的第一行包含一个整数 $T$,表示数据的组数。
接下来按照如下格式分别给出 $T$ 组数据。 每组数据的第一行包含一个正整数 $n$。接下来一行包含 $n$ 个由空格隔开的正整数 $a[i]$。
输出格式
输出文件共有 $T$ 行,对于每组数据,输出一行一个正整数,表示所有与 $(n, a)$ 等价的货币系统 $(m, b)$ 中,最小的 $m$。
样例 1
样例输入
2
4
3 19 10 6
5
11 29 13 19 17
样例输出
2
5
提示
在第一组数据中,货币系统 $(2, [3,10])$ 和给出的货币系统 $(n, a)$ 等价,并可以验证不存在 $m \lt 2$ 的等价的货币系统,因此答案为 $2$。 在第二组数据中,可以验证不存在 $m < n$ 的等价的货币系统,因此答案为 $5$。
【数据范围与约定】
对于 $100\%$ 的数据,满足 $1 \leqslant T \leqslant 20$,$n, \space a[i] \geqslant 1$。
算法:贪心 + DP
-
首先预置组成的意思 —— 对 $\forall x \in N$,从一个集合 $S$ 里选择一些 $\leqslant x$ 的数 $(s_1, \space s_2, \space …, \space s_k)$ ,有 $x = \sum\limits_{i = 1}^k{t_i \times s_i}$($t_i \gt 0$)。
-
初步思路:把 $(n, \space a)$ 和 $(m, \space b)$ 看作集合 $A$ 和 $B$,根据题目意思,就是对任意 $x$,都要有 $A$ 和 $B$ 能够组成 $x$,否则两个集合都不能组成 $x$;由于题目要求 $B$ 最小,所以可以猜测 $B$ 为 $A$ 的子集。
-
先证一个前置结论:若 $x \in A$,且 $x$ 无法由 $A$ $|$ $x$(即 $A$ 中 $x$ 的补集,下用 $x^c$ 表示)组成,则 $x \in B$。下用反证法,不妨设存在满足上述条件的 $x$,有 $x \notin B$,根据题目条件,$B$ 中没有 $x$,意味着必须有 $(b_1, \space b_2, \space … b_p)$,$\space b_i \in B$,组成 $x$,那么这些元素就至少存在一个 $b_t \notin A$ 且 $b_t$ 不能由 $A$ 组成,否则 所有 $b_i \in A$,那说明 $x$ 是可以由 $x^c$ 组成的,或是 $b_t \notin A$,但 $b_t$ 能由 $A$ 组成,即 $b_t = \sum\limits_{i = 1}^{k’}{t_{n_i} \times a_{n_i}}$($1 \leqslant n_i, \space k’ \leqslant k$),所以可以将 $b_t$ 拆成 $A$ 中元素,同理对其他满足这个性质的 $b_i$ 都拆成 $A$ 中元素,再加上这些元素一定都比 $x$ 小,这样就推导出 $x^c$ 能够组成 $x$,与假设矛盾,所以结论成立。
贪心部分
-
首先需要证明:$B \subset A$。根据子集的定义,$\forall x \in B$,都有 $x \in A$,于是我们用反证法,不妨设 $\exists x \in B$,有 $x \notin A$。根据题目意思,$A$ 中没有 $x$,那就必须有 $(a_1, \space a_2, \space … a_p)$,$\space a_i \in A$,组成 $x$,若其中有一些 $a_i$ 可以被 $a_i^c$ 组成,那么就将其替换为组成 $a_i$ 的 $a_i^c$ 中的元素,这样就可以得到一个由 $A$ 组成 $x$ 的集合 $(a_{n_1}, \space a_{n_2}, \space … a_{n_{k’}})$,这个集合内的每一个元素 $a_{n_i}$ 都不能由 ${a_{n_i}^c}$ 组成,于是由上述的前置结论,一定有 $\forall a_{n_i} \in B$,所以就有 $x^c$ 能够组成 $x$(这里是关于 $B$ 的补集)。再接着推导,就能得到,所有含有 $x$ 的集合,其所能组成的数,将 $x$ 替换为 $x^c$ 中组成 $x$ 的集合的元素,也完全可以,因此整个集合 $B$ 减去一个 $x$ 同样满足题目要求,所以此时的 $B$ 集合不是最小的,与假设矛盾,所以 $\forall x \in B$,都有 $x \in A$,即 $B$ 是 $A$ 的子集成立。
-
接下来开始求解 $B$ 集合。通过上面的推导,我们很容易得出一个猜想:对于 $A$ 中所有不能由 $a_i^c$ 组成的 $a_i$,都应该有 $a_i \in B$。这个证明可以分成两边,一边是往扩大集合的角度,一边是往缩小集合的角度。第一是扩大集合,这个角度很显然地被排除了,因为上述推导 $B \subset A$ 的时候就提到了,如果一个数能被一个集合组成,那就把这个数换成组成它的集合的元素,对结果没有影响,所以 $B$ 数组不需要再扩大了。第二是缩小集合的角度,若 $B$ 数组在上述假设的基础上再扣掉一些 $a_i$,那么这些被扣掉的 $a_i$ 就根本无法由任何 $B$ 的子集组成,因为它们除了自己等于自己以外,无法由任何集合组成,所以 $B$ 数组也无法缩小。由夹逼定理,$B$ 集合就等于 $A$ 中所有不能由 $a_i^c$ 组成的 $a_i$ 的集合。
DP 部分
-
首先根据上述的贪心,我们可以将所有数从小到大排序,接着从前往后扫,因为小的数才有可能作为上述的备选对象,即无法由任何集合组成。
-
设 $f(i, j)$ 为从前 $i$ 个数中选,$f(i, j) = 1$ 表示 $j$ 能被表示出来,$f(i, j) = 0$ 表示 $j$ 无法被表示。
-
于是有状态转移方程 $f(i, j) = f(i, j) \space | \space f(i - 1, j - a[i])$。
-
注意这里要优化掉第一维的话需要像完全背包那样优化,因为每个数都可以无限选。
参考文献:第一篇题解
时间复杂度 $O(T \times n \times m)$ ($m = \max\limits_{1 \leqslant i \leqslant n}{a[i]}$)
C ++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
#define x first
#define y second
#define endl '\n'
#define fup(i, a, b) for (int i = a; i <= b; i ++ )
#define fdn(i, a, b) for (int i = a; i >= b; i -- )
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 110, M = 30010, MOD = 1e9 + 7;
int n, m;
int a[N], f[M];
void solve()
{
cin >> n;
fup(i, 1, n) cin >> a[i];
sort(a + 1, a + n + 1);
memset(f, 0, sizeof f);
f[0] = 1;
int res = 0;
fup(i, 1, n)
{
if (!f[a[i]]) res ++ ;
fup(j, a[i], a[n]) f[j] |= f[j - a[i]];
}
cout << res << endl;
}
int main()
{
int T = 1;
cin >> T;
while (T -- ) solve();
return 0;
}
你这看起来挺厉害的 怎么不去打ACM 杭州群也看到你了^^
我超,事佬😭
我感觉我还是好菜,主要是 cf 打了四场上了个绿后面就没动静了(后面每次在那个时间点都有事,像补作业啥的(尤其是实变函数 和 pde 血妈多),就一直没打),进集训队的日程就一直拖着了(悲),然后想着寒假打到 1500 看看能不能申请进去(好像我记得应该出去打 icpc 的队都是从集训队挑的)😭
cf打个1600就没啥问题了 而且你1200已经可以进集训队了 直接企业微信私聊周晓琳周老师就可以 今年cf 1200多的也有一些大二的学弟打了xcpc 加油 感觉你学的一些算法都很高级 对区域赛来说不需要特别高深的算法 可能更需要的是cf的思维能力 所以直观的看就是你的cf积分 我们学校看这个选拔以及如果你分高的话 后面各种比赛都可以公费
而且好像今年cf 1400的大二学弟学妹都可以打xcpc区域赛 你早上1400就可以体验体验了 从结果上来看也有点可惜 不过明年区域赛还有一年 强的话可以打四场 加油 看好你 努力冲cf 因为咱们学校老师就是看cf选拔出去打比赛的
好的佬😭!