题解：CF453B Little Pony and Harmony Chest

Lywh_ddAC · 2025-10-02 17:12:46 · 题解

题目分析

本题要求构造一个长度为 n 的序列 b，使得：

1. 序列中任意两个元素互质
2. 最小化 \sum_{i=1}^{n} |a_i - b_i|

因为 1 \le a_i \le 30，所以针对同位的 b_i 来讲，选 1 一定比选 60 优，所以准确点，对于每个 b_i 其值一定不会超过 59，显然可以想到用二进制来表示已使用的质因子的状态。

别的证明，大佬们的题解不难理解，这里主要备忘一下转移方程。

从别的大佬那里可以知道 \text{dp} 的状态定义为： \text{dp}[i][\text{mask}] 表示考虑前 i 个元素，已使用的质因数集合为 \text{mask}（二进制下）时的最小差和。

以及转移方程：

为什么

对于每一个质因数分解出来使用状态为 \text{mask}（方程中的 \text{table} 数组）的 b[i] 来讲，他的答案只有可能从 \text{dp}[i-1][j] 满足 j \& \text{mask} = 0，即 j 与 \text{mask} 没有交集，传过来（保证互质嘛）。

那么顺序来看，如果当前质数使用情况为 j，枚举到这一位 b 数组可以放 k，那么首先要保证 (j \mid \text{mask}) = j，就是 j 要完全包含 \text{mask} (\text{table}[k])。
然后对于当前 \text{dp}[i][\text{mask}]，可以传递答案的 \text{dp}[i-1] 的质数使用状态中，就不能与 \text{mask} 有交集了，所以答案要从 \text{dp}[i-1][j \oplus \text{mask}] 传过来，这就是转移方程中的：

当然，加上的 |a[i] - k| 就是第 i 个元素选择数字 k 的代价。

转移方程就只有这些，但题目中的输出还有点麻烦。

实现

针对输出，新增一个 \text{pre} 数组，表示对于每个状态 (i, j)，\text{pre}[i][j] 告诉我们为了达到这个状态，第 i 个位置选择了哪个数字，那么现在，在计算完所有的 \text{dp} 值后，可以先枚举一遍所有的 \sum_{i=1}^{n} \text{dp}[n][i] 找出使其最小的 i，于是从 i 递归输出，具体看代码：

#include<bits/stdc++.h>
using namespace std;
#define N 105

int n,ans,cnt;
int a[N],vis[N],c[N],maskk[N],dp[105][1<<17],pre[105][1<<17];

int mask(int k){
    int an=0;
    for(int i=1;i<=cnt;i++){
        if(k%a[i]==0){
            k/=a[i];
            an|=(1<<(i-1));
        }   
        if(k==0)    break ;
    }
    return an;
}

void write(int nn,int ll){
    if(nn==0)   return ;
    write(nn-1,ll^maskk[pre[nn][ll]]);//ll一定是包含maskk的 
    cout<<pre[nn][ll]<<" ";
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>c[i];
    } 
    for(int i=2;i<=58;i++){
        if(!vis[i]) a[++cnt]=i;
        for(int j=1;j<=cnt&&a[j]*i<=58;j++){
            vis[a[j]*i]=1;
            if(i%a[j]==0)   break;
        }
    }
    for(int i=1;i<=58;i++)  maskk[i]=mask(i);
    memset(dp,0x3f,sizeof(dp));
    //dp[i][mask]，考虑前 i个元素，已使用的质因数集合为 mask时的最小差和 
    dp[0][0]=0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=(1<<16)-1;j++){
            for(int k=1;k<=58;k++){
                int mak=maskk[k];
                if((j|mak)!=j)  continue ; //如果j不完全包括mak
                //j^mak把max从j中消除 
                if(dp[i][j]>dp[i-1][j^mak]+abs(k-c[i])){
                    dp[i][j]=dp[i-1][j^mak]+abs(k-c[i]);
                    pre[i][j]=k;
                }
            }
        }  
    }
    ans=0x3f3f3f;
    int ll=0;
    for(int i=0;i<=(1<<16)-1;i++){
        if(ans>dp[n][i]){
            ans=dp[n][i];
            ll=i;
        }
    }
    write(n,ll);
    return 0;
}