题目解析

题目背景

Bessie 经常在 Farmer John 的课上睡觉，Elsie 负责记录 Bessie 在每堂课上睡觉的次数。Elsie 想通过合并或拆分记录，使得所有记录中的数字都变成某个特定的数 q[i]，并计算最少需要的操作次数。

输入输出

• 输入:
  • 第一行一个整数 N，表示课程数量。
  • 第二行 N 个整数 a[1], a[2], ..., a[N]，表示每堂课 Bessie 睡觉的次数。
  • 第三行一个整数 Q，表示查询的数量。
  • 接下来 Q 行，每行一个整数 q[i]，表示 Bessie 最不喜欢的数字。
• 输出：
  • 对于每个 q[i]，输出将所有记录中的数字都变成 q[i] 所需的最少操作次数。如果无法实现，输出 -1。

主要思路

1. 前缀和:
   • 使用前缀和数组 a 来简化后续的计算。a[i] 表示前 i 堂课 Bessie 睡觉的总次数。
2. 质因数分解:
   • 对最后一堂课的总次数 a[n] 进行质因数分解，得到其所有质因数及其指数。
3. 状态压缩:
   • 使用状态压缩的方法，将每个数表示为质因数的幂次组合，计算每个状态的出现次数。
4. 动态规划:
   • 通过深度优先搜索（DFS）计算每个状态的最优解，并存储在 f 数组中。
5. 查询处理:
   • 对于每个查询 q[i]，检查 a[n] 是否能被 q[i] 整除。如果不能，输出 -1。否则，计算将所有记录中的数字都变成 q[i] 所需的最少操作次数。

代码详细解析

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2e5+5;

// 定义
ll n,q,a[N],pr[N];
int pw[N],cnt,ppw[N];
map<ll,ll>mp;
int f[N];

// 计算状态值
int calc(int*pw){
    int res=0;
    for(int i=1;i<=cnt;i++)res+=pw[i]*ppw[i];
    return res;
}

// 计算逆向值
ll rev(int x){
    ll res=1;
    for(int i=1;i<=cnt;i++){
        int d=x/ppw[i]%(pw[i] + 1);
        for(int j=1;j<=d;j++) res*=pr[i];
    } return res;
}
int fix,cpw[N];

// 深搜
void dfs(int id){
    if(id>cnt){
        int cur=calc(cpw);
        f[cur-ppw[fix]]+=f[cur];
        return;
    }for(int i=pw[id];i>=(id==fix);i--)cpw[id]=i,dfs(id+1);
}

// 检查并计算结果
void check(){
    ll tmp=a[n];
    for(int i=2;i<=1e6;i++)
        if (tmp%i==0){
            pr[++cnt]=i;
            while(tmp%i==0)pw[cnt]++,tmp/=i;
        }
    if(tmp>1e12) return;
    if(tmp>1) pr[++cnt]=tmp,pw[cnt]=1;
    ppw[cnt]=1;
    for(int i=cnt-1;~i;i--) ppw[i]=ppw[i+1]*(pw[i+1]+1);
    for(int i=1;i<n;i++){
        ll tmp=a[i];
        for(int j=1;j<=cnt;j++) {
            int cur=0;
            while(tmp%pr[j]==0) cur++,tmp/=pr[j];
            cpw[j]=min(pw[j],cur);
        }f[calc(cpw)]++;
    }
    for(int i=1;i<=cnt;i++) fix=i,dfs(1);
    for(int i=0;i<ppw[0];i++) mp[rev(i)]=n-1+a[n]/rev(i)-1-f[i]*2;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i],a[i]+=a[i-1];
    check(),cin>>q;
    for(int i=1;i<=q;i++) {
        ll x;cin>>x;
        if(a[n]%x){puts("-1");continue;}
        if(!mp[x]){
            ll ans=0;
            for(int j=1;j<n;j++)ans+=a[j]%x==0;
            mp[x]=n-1+a[n]/x-1-ans*2;
        }
        cout<<mp[x]<<"\n";
    }
    return 0;
}

关键步骤解释

1. 前缀和计算:

for(int i=1;i<=n;i++) cin>>a[i],a[i]+=a[i-1];

• 读取每堂课的睡觉次数，并计算前缀和。

2. 质因数分解:

ll tmp=a[n];
    for(int i=2;i<=1e6;i++)
        if (tmp%i==0){
            pr[++cnt]=i;
            while(tmp%i==0)pw[cnt]++,tmp/=i;
        }
    if(tmp>1e12) return;
    if(tmp>1) pr[++cnt]=tmp,pw[cnt]=1;

• 对 a[n] 进行质因数分解，得到所有质因数及其指数。

3. 状态压缩:

ppw[cnt]=1;
    for(int i=cnt-1;~i;i--) ppw[i]=ppw[i+1]*(pw[i+1]+1);

• 计算每个状态的权重。

4. 动态规划:

for(int i=1;i<n;i++){
        ll tmp=a[i];
        for(int j=1;j<=cnt;j++) {
            int cur=0;
            while(tmp%pr[j]==0) cur++,tmp/=pr[j];
            cpw[j]=min(pw[j],cur);
        }f[calc(cpw)]++;
    }

• 计算每个前缀和的状态，并统计每个状态的出现次数。

5. 深度优先搜索:

for(int i=1;i<=cnt;i++) fix=i,dfs(1);

• 通过 DFS 计算每个状态的最优解

6. 查询处理:

for(int i=1;i<=q;i++) {
        ll x;cin>>x;
        if(a[n]%x){puts("-1");continue;}
        if(!mp[x]){
            ll ans=0;
            for(int j=1;j<n;j++)ans+=a[j]%x==0;
            mp[x]=n-1+a[n]/x-1-ans*2;
        }
        cout<<mp[x]<<"\n";
    }

• 对每个查询 q[i]，检查 a[n] 是否能被 q[i] 整除，计算最少操作次数并输出结果。

总结

通过前缀和、质因数分解、状态压缩和动态规划等方法，我们可以高效地解决这个问题。代码逻辑清晰，能够处理大规模数据。

我看谁不要脸到这种题都抄