货币系统

题面查看

一道很好的思维题，在考场上的想法其实是YY出来的，没有严格的数学证明，这里就补证一下

首先，对于题目给出的货币系统\((n,a)\)我们把它看成集合\(A\)，然后就是要做一个化简，把不必要的数字\(x(x \in A)\)去掉，变成集合\(B(m,b)\)，使得\(B\)中的任意一个元素，都是不能被其他元素组成的

所以我们可以猜测\(B \subseteq A\)，然后我们运用反证法证明

我们假设\(\forall x \in B,x \notin A\)

那么就是说\(x\)可以被\(A\)中元素组成，这些元素不能被\(A\)集合中其他元素组成(如果\(\forall a_i\)可以被其他元素组成，那么它必然可以被\(a_1,a_2,...,a_j\)代替)

证到这里就发现还需要一个结论，不能被其他元素组成的\(x(x \in A)\)必然有\(x \in B\)

我们同样用反证法

假设\(\forall x \in A,x \notin B,x\)不能被\(a_i\)组成\((a_i \in A)\)

那么说明\(B\)集合必然有元素\(a_j\)可以组成\(x\)，那么\(a_j \notin A\)且\(a_j\)不能被\(A\)集合中的元素表示出，这与题目中的 当且仅当对于任意非负整数 \(x\)，它要么均可以被两个货币系统表示出，要么不能被其中任何一个表示出 矛盾。

综上所述，不能被其他元素组成的\(x(x \in A)\)必然有\(x \in B\)

然后就可以愉快的继续证明了

那么就是说这些元素都存在于\(B\)集合中，那就是说，\(x\)可以被存在于\(B\)集合的这些元素组成，那么也就是说即便去掉\(x\)，也依旧满足条件，与\(B\)集合的定义矛盾

综上所述，对于任意一个元素，都存在于集合\(A,B\)中，也就是\(B \subseteq A\)

那么做这道题仅仅只需要最后一个证明了，在 \(A\) 集合中能被其它数组成的数必然不在 \(B\) 集合内

依然是用反证法，\(\forall x \in A,x \in B ,x可以被a_1,a_2,a_i \in A组成\)

那么\(a_1,a_2,a_i \in B\)，就是说\(x\)可以被表示出，与\(B\)集合定义矛盾

综上所述，在 \(A\) 集合中能被其它数组成的数必然不在 \(B\) 集合内，证毕。

我们知道对于一个\(x\)只能被比自己小，而不能被比自己大的数字组成。也就是说当我们进行排序之后，如果\(x\)能被前\(i\)个数组成且组成\(x\)的数当中包含\(a_i\)那么\((x-a_i)\)也必然能被前\(i\)个数组成，能被组成就要，不被组成就放进\(B\)集合里

我们定义\(f(x)\)为\(x\)是否被组成

\[ f(x)=f(x)|f(x-a[i]) \]

这题就解决了，然后附上代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxx = 25005;
const int maxn = 105;
int a[maxn], f[maxx];
int T, n, ans;
int main()
{
    cin >> T;
    while (T--)
    {
        memset(f, 0, sizeof(f));
        cin >> n;
        ans = n;
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        sort(a + 1, a + 1 + n);
        f[0] = 1;
        for (int i = 1; i <= n; i++)
        {
            if (f[a[i]])
            {
                ans--;
                continue;
            }
            for (int j = a[i]; j <= a[n]; j++)
                f[j] = f[j] | f[j - a[i]];
        }
        cout << ans << endl;
    }
}

洛谷 P5020 货币系统

原文：https://www.cnblogs.com/AntonioYAO/p/11729833.html