Day1 T2 货币系统
原题面：
在网友的国度中共有 n种不同面额的货币，第 i 种货币的面额为 (a_i)，你可以假设每一种货币都有无穷多张。为了方便，我们把货币种数为 n，面额数组为 (a_{1..n}) 的货币系统记作 (n,a)。
在一个完善的货币系统中，每一个非负整数的金额 xx 都应该可以被表示出，即对每一个非负整数 x，都存在 n个非负整数 (t_i)满足 (sum t_i*a_i)的和为 xx。然而， 在网友的国度中，货币系统可能是不完善的，即可能存在金额 x 不能被该货币系统表示出。例如在货币系统 n=3, a=[2,5,9]中，金额 1,3 就无法被表示出来。
两个货币系统 (n,a) 和 (m,b) 是等价的，当且仅当对于任意非负整数 x，它要么均可以被两个货币系统表出，要么不能被其中任何一个表出。
现在网友们打算简化一下货币系统。他们希望找到一个货币系统 (m,b)，满足 (m,b) 与原来的货币系统 (n,a) 等价，且 m 尽可能的小。他们希望你来协助完成这个艰巨的任务：找到最小的 m。
看上去好难……
才怪嘞但是只需要稍加思考就可以把题目转换成这样：
给定n个数，让你从中选出m个数，使之可以将原本的n个数全部表示出来
要求最小化m。
话说我考场想这个结论想了1h
然后就很简单了。
考场上我打的是理论80分，实际玄学分的筛～～
不难发现，若(a_ileq a_j) 则(a_j) 不可能表示出(a_i)
所以，给A序列从小到大排一个序，然后用(vis[i])表示i这个数能否被目前所选的数表示出来。
从小到大枚举(a_i)若(vis[a_i]=0)则说明(a_i)这个数不可以被表示，所以我们必须要将(a_i)选入，然后更新所有数的vis值。
具体更新方法请看代码。
复杂度：O((sum ans*Maxa^2div ln(Maxa)))
洛谷数据水，水了95分。
Code
#include<bits/stdc++.h>
using namespace std;
int read(){
int res=0,fl=1;
char r=getchar();
for(;!isdigit(r);r=getchar())if(r=='-')fl=-1;
for(;isdigit(r);r=getchar())res=(res<<3)+(res<<1)+r-48;
return res*fl;
}
const int Maxm=25000+10,Maxn=300;
int a[Maxm],ans,n,Maxa;
bool ch[Maxm],bk[Maxm];
int main(){
freopen("money.in","r",stdin);
freopen("money.out","w",stdout);
int t=read();
while(t--){
n=read();
ans=0;
Maxa=0;
memset(ch,0,sizeof(ch));
for(int i=1;i<=n;++i){
a[i]=read();
Maxa=max(a[i],Maxa);
}
sort(a+1,a+1+n);
for(int i=1;i<=n;++i){
if(!ch[a[i]]){
ans++;
ch[a[i]]=1;
for(int k=Maxa;k>=a[1];--k){
if(!ch[k]){
bool fl=0;
for(int j=a[i];j<=k;j+=a[i]){
if(ch[k-j]){fl=1;break;}
}
ch[k]=fl;
}
}
}
}
printf("%d
",ans);
}
return 0;
}
正解部分
思路和之前一摸一样，只是筛的过程中只要枚举一个k，若k在之前可以被表示出来，那么在添加了一个数(a_i)后(k+a_i)也一定能被表示出来。
Code
#include<bits/stdc++.h>
using namespace std;
int read(){
int res=0,fl=1;
char r=getchar();
for(;!isdigit(r);r=getchar())if(r=='-')fl=-1;
for(;isdigit(r);r=getchar())res=(res<<3)+(res<<1)+r-48;
return res*fl;
}
const int Maxm=25000+10,Maxn=300;
int a[Maxm],ans,n,Maxa;
bool ch[Maxm],bk[Maxm];
int main(){
freopen("money.in","r",stdin);
freopen("money.out","w",stdout);
int t=read();
while(t--){
n=read();
ans=0;
Maxa=0;
memset(ch,0,sizeof(ch));
for(int i=1;i<=n;++i){
a[i]=read();
Maxa=max(a[i],Maxa);
}
sort(a+1,a+1+n);
for(int i=1;i<=n;++i){
if(!ch[a[i]]){
//printf("%d
",a[i]);
ans++;
ch[a[i]]=1;
for(int k=1;k<=Maxa;++k){
if(ch[k]){
ch[k+a[i]]=1;
// printf("%d ",k+a[i]);
}
}
}
}
printf("%d
",ans);
}
return 0;
}
复杂度：O（(sum ans*Maxa)）
据说这道题也是原题，佩服CCF