codeforces-1734C - Removing Smallest Multiples

题目 Removing Smallest Multiples

题目大意

给由0和1组成的字符串 T ，字符串长度为 n ，0表示该数字被删去，1表示存在，即T=010011的意思就是数字1~6中删去了数字1 3 4。
定义一种操作：每操作一次，就删去一个数字（该数字为 字符串中 k 的最小公倍数。）
将每次操作的 k 值相加，求和的最小值

题意解释

如果字符串 T 中 x个0，那么就是需要操作 x 次。
eg；n=8，T=10010101
那么就需要删去2 3 5 7

1. 如果 k=1，1的最小公倍数是1，1会被删去，因此 k 不能为1；
   如果 k=2，2的最小公倍数是2，2会被删去，符合我们的需求。因此第一次操作，k 取2。
2. 如果 k=1，1的最小公倍数是1，1会被删去，因此 k 不能为1；
   如果 k=2，字符串中2的最小公倍数是4，4会被删去，因此 k 不能为2。
   如果 k=3，3的最小公倍数是3，3会被删去，符合我们的需求。因此第二次操作，k 取3。
3. 如果 k=1，1的最小公倍数是1，1会被删去，因此 k 不能为1；
   如果 k=2，字符串中2的最小公倍数不存在，因此 k 不为2。
   如果 k=3，字符串中3的最小公倍数是6，6会被删去，因此 k 不为3。
   如果 k=4，4的最小公倍数是4，4会被删去，因此 k 不为4。
   如果 k=5，5的最小公倍数是5，5会被删去，符合我们的需求。因此第三次，k 取5。
4. 同理，第四次操作，k 取7。

总共花费 2+3+5+7=17

超时代码

这是我自己最开始写的，超时了，

#include
#include
#include
#include
#define N 100000
using namespace std;
long long t,n;
string s;

long long sum; 
int a[N];//记录k不可以使用的值

void f(long long  x) {
	long long  k=1;
	while(k<=sqrt(x) ){
		if(x%k==0){
			a[k]=1;
			a[x/k]=1;}
		k++;
	}
}
void solve() {
	sum=0; 
	long long  sum=0;
	memset(a,0,sizeof(a));//初始化
	for(long long  i=1; i<=n; i++) {
		long long k=1;
		if(s[i-1]=='1') { //不需要删去，因此k不能等于这个数字 也不能等于该数字的因子
			f(i);//数组a i的因子全部为1
			continue;
		} else { //需要删     
			while(1) {
				if(i%k==0 && a[k]==0)
					break;//如果k是其因子且k可以取值为这个，说明找到了最小值k
				k++;
			}
			sum+=k;
		}
	}
	cout<<sum<<"\n";
}
int main() {
	cin>>t;
	while(t--) {
		cin>>n;
		cin>>s;
		solve();
	}
}

AC 代码

考虑如何选取一个

#include
#include
#include
#define INF 100000000
using namespace std;
long long t,n;
string s;

void solve() {
	vector<int> a(n,INF);//存储位置j的可以的k值
	for(int i=n; i>=1; i--) {//k的可能取值范围（1~n）  从大到小排 
		for(int j=i-1; j<n; j=j+i) {//找寻是k的倍数位置，由近及远
			if(s[j]=='1')//如果该位置(j)是1 则该位置(j)不能取该值i 
				break;
			a[j]=min(i,a[j]);//如果是0，则说明该位置（j）的k值可以为 i 
		}
	}
	long long ans=0;
	for(int i=0; i<n; i++)
		if(s[i]=='0')
			ans+=a[i];
	cout<<ans<<"\n";
}

int main() {
	cin>>t;
	while(t--) {
		cin>>n;
		cin>>s;
		solve();
	}
}