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;
}