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
- 如果 k=1，1的最小公倍数是1，1会被删去，因此 k 不能为1；
如果 k=2，2的最小公倍数是2，2会被删去，符合我们的需求。因此第一次操作，k 取2。 - 如果 k=1，1的最小公倍数是1，1会被删去，因此 k 不能为1；
如果 k=2，字符串中2的最小公倍数是4，4会被删去，因此 k 不能为2。
如果 k=3，3的最小公倍数是3，3会被删去，符合我们的需求。因此第二次操作，k 取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。 - 同理，第四次操作，k 取7。
总共花费 2+3+5+7=17
超时代码
这是我自己最开始写的，超时了，
#include<iostream>
#include<string.h>
#include<vector>
#include<math.h>
#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<iostream>
#include<string.h>
#include<vector>
#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();
}
}