CF1497E2. Square-free division
题目描述
数组 a 由 n 个正整数构成。你需要将它们分割成最小数量的连续子段,使得每一个子段中的任意两个数(不同位置)的乘积不为完全平方数。
除此之外,你被允许在分割之前进行最多 k 次修改操作。
在一次修改操作中,你可以选择数组中的某个位置的数,将该位置的数变为任意正整数。
请问连续子段的最小数量是多少(在最多 k 次操作后)?
Solution
先考虑如果 a[i] 的因子中包含完全平方数,那么先用 a[i] 除掉这样的完全平方数(寒假做过一道题跟这个一样)
那么就将问题转化成了,每个子段中不能出现相同的数。
考虑预处理 left_{i,j} ,表示一个尽量靠左的 l 。这个 l 需要满足在最多修改 j 次后 ,能使得 [l,i] 可以连成一个子段。
由于对于每个 j 而言,左端点 left_{i,j} 都会随 i 的增加而单调不减。所以我们可以对每个 j 用双指针去维护出 left_{i,j} 。
for(int k = 0; k <= kk ; ++k){
int l = n + 1 , now = 0 ;
for(int i = n ; i ; --i){
while( l-1>=1 && now + (cnt[a[l-1]] > 0) <= k){
now += cnt[a[l-1]] > 0 ;
cnt[a[l-1]] ++;
l--;
}
left[i][k] = l ;
now -= cnt[a[i]] > 1 ;
cnt[a[i]]-- ;
}
}
然后就 dp ,令 dp_{i,j} 表示到 i 修改了 j 次后最小的答案,方程很好列出。
#include<bits/stdc++.h>
const int N = 1e7 + 10;
const int M = 2e5 + 10;
int f[N],pri[N],a[M],tot;
int t,n,kk;
int left[M][21];
int cnt[N];
int dp[M][21];
void init(){
for(int i=2 ; i < N ; ++i){
if(!f[i]) pri[++tot] = i , f[i] = i;;
for(int j=1; j<=tot&&pri[j]*i<N;++j ){
f[pri[j]*i] = pri[j];
if(i%pri[j]==0)
break;
}
}
}
int main(){
init();
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&kk);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
int tt = a[i] , ss = 1;
while(tt!=1){
if(tt%(1ll*f[tt]*f[tt])==0) tt/=1ll*f[tt]*f[tt];
else{
ss*=f[tt];
tt/=f[tt];
}
}
a[i] = ss;
}
for(int k = 0; k <= kk ; ++k){
int l = n + 1 , now = 0 ;
for(int i = n ; i ; --i){
while( l-1>=1 && now + (cnt[a[l-1]] > 0) <= k){
now += cnt[a[l-1]] > 0 ;
cnt[a[l-1]] ++;
l--;
}
left[i][k] = l ;
now -= cnt[a[i]] > 1 ;
cnt[a[i]]-- ;
}
}
memset(dp,0x3f,sizeof(dp));
dp[0][0] = 0 ;
for(int i=1;i<=n;++i){
for(int k1 = 0 ; k1 <= kk ; ++k1){
for(int k2 = 0; k2 <= k1; ++k2){
dp[i][k1] = std::min(dp[i][k1],dp[left[i][k2]-1][k1-k2]+1);
}
}
}
printf("%d\n",dp[n][kk]);
}
return 0;
}
0 条评论