Codeforces Round #822 (Div. 2) C Removing Smallest Multiples

Problem - C - Codeforces

题意：

给定两个集合S，T，S为1到n，T为S的子集

有这样一种操作：

选取一个数k，可以删掉k的最小倍数

每次删的代价是k

问最少需要多少代价能使S变为T

思路：

我们已知了要删的是哪些数

这些数被删掉的手段是被它的因子删掉

我们要让代价最小，就是让因子最小

对于一个待删数x，我们凭空无法确定被x的哪个因子删掉，也无法确定倍数是多少

因此我们去枚举因子1到n，然后去枚举倍数

如果枚举出来的倍数是待删除的，那么就把这个待删除的删了，维护以下代价继续去枚举倍数

如果倍数不是待删除的，如果是在S集合中的，那么直接break掉，继续去枚举因子，因为后面再去枚举倍数的话，就算是待删除的，也不是最小倍数了

Code：

#include <bits/stdc++.h>
using namespace std;
const int mxn=1e6+10;
#define int long long
string s;
int n;
int a[mxn],b[mxn];
void init(){
	for(int i=0;i<=n;i++){
		a[i]=b[i]=0;
	}
}
void solve(){
	s.clear();
	cin>>n>>s;
	init();
	s=" "+s;
	for(int i=1;i<=n;i++){
		if(s[i]=='0') b[i]=1;
		else a[i]=1;
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		for(int j=i;j<=n;j+=i){
			if(b[j]) ans+=i,b[j]=0;
			else{
				if(a[j]) break;
			}
		}
	}
	cout<<ans<<'\n';
}
signed main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int T;
	cin>>T;
	while(T--)solve();
	return 0;
}

总结：

当无法确定因子和倍数时，我们去枚举因子和倍数