NOPI2018 货币系统 bool完全背包 bitset优化转移

NOPI2018 货币系统 bool完全背包 bitset优化转移

题意

给你n种货币的面值，成为A货币系统，让你求出一个货币系统B，使得B系统的货币种类不超过A系统且最小，并且A系统能凑出的面值B系统也能凑出，A系统不能凑出的面值B系统也不能凑出。

[1 leq n leq 100\ a_i leq 25000 ]

分析

当某个货币可以被这个系统中的其他货币表示出来的时候，这个货币就不必存在。

根据这个思路我们发现问题就转化为了bool完全背包。某个货币(x)能够被表示当且仅当(x - k_{a_i})能够被表示

我们用之前bitset刷表的思想，“刷”(x + a_i,x+2a_i...)表示为true，容易发现类似二进制拆分的原理，我们只需要“刷”二的幂次。

所以复杂度又降了一个(log)

我们之所以能刷表，其实是利用了bitset左移仅需要(O（1）)时间，把bitset看成桶的话，其实做了一次所有存在的值域的数左移了一部分，因此对于bool背包等问题常常可以用bitset来优化。

代码

const int maxn = 2e5 + 5;

bitset<maxn> st;

int main(){
	int T = rd();
	while(T--){
		st.reset();
		int n = rd();
		vector<int> v(n);
		st[0] = 1;
		for(int i = 0;i < n;i++)
			v[i] = rd();
		sort(v.begin(),v.end());
		int ans = 0;
		for(int i = 0;i < n;i++){
			if(!st.test(v[i])) {
				ans++;
				int x = v[i];
				while(x <= v.back()) {
					st |= st << x;
					x <<= 1;
				}
			}
		}
		printf("%d
",ans);
	}	
}