P5020 货币系统 题解

博客园同步

原题链接

简要题意：

寻找一个与给定货币系统等值的最短货币系统。确定这个货币系统的最小规模。等价的具体定义请参考题目内容。

本文可能用到一些集合论，请放心食用。

算法一

n=2 时，只需判断两个数的倍数关系。有倍数关系则答案为 1，否则为 2.

时间复杂度：O(T \times n).

实际得分：15pts.

算法二

n=3 时，首先，如果两个数都是另一个数的倍数，那么答案为 1.

否则，如果仍存在倍数关系，则答案为 2.

其余的情况，只需要考虑，最小的数和次小的数能否表示出最大的数。

能则为 2，否则为 3.

这里有很多种方法判断。比如：

暴力，用桶直接来，O(\max a_i).

考虑解方程，用 \texttt{exgcd} 写，O(\log \max a_i).

总之，时间复杂度为 O(T \times n \times (\max a_i)). （无需优化，因为没有必要）

实际得分：30pts.

算法三

首先，假设给出 S，答案为 T. 则必有：

T \in S

下面来证明这个结论。

如果 T \not \in S，则考虑取出 x = \min (i \in S)，y = \min(i \in T).

如果 x，则 x 无法被表示。

如果 y>x，则 y 无法被表示。

如果 x=y，那么不断递归下去，得证。

所以，我们只需要在给出的货币系统中寻找答案即可。

这里我们枚举选的答案，然后一一验证。

时间复杂度：O(2^n \times n \times (\max a_i) \times T)，可以通过。

实际得分：65pts.

算法四

注释：设n=25。经过一番思考后发现没有找到能够在时间复杂度为O(2^n \times T)的情况下解决该问题的有效策略。这表明在当前难度设置下，该题目的分数可能主要针对一些非正式解法或错误思路的设计。

你发现不需要一一枚举。首先你排序一下。

你只要用当前已有的数，判断当前正在决策的这个数能否被表示出。

能，那么说明这个数没有必要，把它抛弃。

除此之外，则必须选择它。主要原因在于，在这种情况下：
其数值无法直接表示出来，
同样地，则也无法直接显示出来。
只有它本身能够直接显示自身的情况，
因此不得不选择它。

那么，这样我们可以唯一确定一个数是否被选。（排序后从小到大选）

如何判断？

我们发现，每次新加入一个数 x ，我们需要维护能判断出的桶。

在此时，在原有的桶上能够实现的是对每一个能够表示为k的数，在其基础上依次加上x、2x、3x……无限延伸下去的所有数都被标记为可判定的状态。这显然是如此的。

至于 \infty 的上限，只要标到 \max a_i 即可，因为后面的数没有用了。

时间复杂度：O(n \times T \times (\max a_i)).

实际得分：100pts.

    #pragma GCC optimize(2)
    #include<bits/stdc++.h>
    using namespace std;
    
    const int N=5e4+1;
    
    inline int read(){char ch=getchar();int f=1;while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}
    	int x=0;while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}
    
    int T,n,a[N];
    int cnt=0;
    int maxi; bool h[N];
    
    int main(){
    	T=read(); while(T--) {
    		n=read(); maxi=0; cnt=0;
    		memset(h,0,sizeof(h)); //初始化
    		for(int i=1;i<=n;i++) a[i]=read(),maxi=max(maxi,a[i]);
    		sort(a+1,a+1+n); //排序
    		for(int i=1;i<=n;i++)
    			if(!h[a[i]]) { //不能被表示
    				h[a[i]]=1; cnt++;
    				for(int j=1;j<=maxi;j++)
    					if(h[j]) {
    						for(int k=a[i];j+k<=maxi;k+=a[i])
    							h[j+k]=1;
    					} //维护能被表示的桶
    			} printf("%d\n",cnt);
    	}
    	return 0;
    }