M_sea

洛谷5020 货币系统
Luogu2018.11.25 upd:突然发现我考场代码好丑。用bitset重写了一遍,吸个氧直接到了66ms,...
扫描右侧二维码阅读全文
21
2018/11

洛谷5020 货币系统

Luogu

2018.11.25 upd:

突然发现我考场代码好丑。

用bitset重写了一遍,吸个氧直接到了66ms,比以前那个3800+ms的代码不知道高到哪去了。

附上代码:

#include <bits/stdc++.h>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

int n;
int a[110];

inline void solve() {
    n=read();
    for (re int i=1;i<=n;++i) a[i]=read();
    stable_sort(a+1,a+n+1);
    bitset<25010> S;
    S[0]=1; int ans=0;
    for (re int i=1;i<=n;++i) {
        if (S[a[i]]) continue;
        ++ans;
        for (re int j=1;j*a[i]<=a[n];++j)
            S|=(S<<a[i]);
    }
    printf("%d\n",ans);
}

int main() {
    int T=read();
    while (T--) solve();
    return 0;
}

以下是原题解。

分析

我太菜了,考场上没看出来是个背包。

但是我发现简化后的系统显然是原系统的子集。

所以可以排个序,把能表示出来的数全部筛掉就好了。

这个能表示出来的数可以用vector记下来。

代码

考场代码,比较繁琐。

#include <bits/stdc++.h>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=100+10;

int n,ans=0;
int a[MAXN],b[MAXN];
int v[MAXN];
int ind[5000010];
int f[5000010];
vector<int> qwq;

inline void init() {
    ans=0;
    memset(v,0,sizeof(v));
    memset(ind,-1,sizeof(ind));
    memset(f,0,sizeof(f));
    qwq.clear();
}

inline void solve() {
    init();
    n=read();
    for (re int i=1;i<=n;++i) b[i]=read();
    stable_sort(b+1,b+n+1);
    int m=0;
    for (re int i=1;i<=n;++i)
        if (b[i]!=b[i-1]) a[++m]=b[i];
    n=m;
    if (n==1) { puts("1"); return; }
    int Max=a[n];
    for (re int i=1;i<=n;++i) ind[a[i]]=i;
    for (re int i=1;i<=n;++i) {
        if (v[i]==1) continue;
        ++ans;
        for (re int j=qwq.size()-1;j>=0;--j) {
            int now=qwq[j]+a[i];
            while (now<=Max) {
                if (ind[now]!=-1) v[ind[now]]=1;
                if (!f[now]) { qwq.push_back(now); f[now]=1; }
                now+=a[i];
            }
        }
        if (!f[a[i]]) { f[a[i]]=1; qwq.push_back(a[i]); }
        int tmp=a[i]+a[i];
        while (tmp<=Max) {
            if (ind[tmp]!=-1) v[ind[tmp]]=1;
            if (!f[tmp]) { qwq.push_back(tmp); f[tmp]=1; }
            tmp+=a[i];
        }
    }
    printf("%d\n",ans);
}

int main() {
    int T=read();
    while (T--) solve();
    return 0;
}
最后修改:2018 年 12 月 02 日 09 : 18 PM

发表评论

1 条评论

  1. smy

    %%%tql