题解：P12160 [蓝桥杯 2025 省 Java B] 2 的幂

· · 题解

首先，读题！

形式化题意

给出一个长 n 的数组 a 和一个数 k，设有一个长 n 的数组 p 满足 2^k\mid\prod^n_{i=1}(a_i+p_i) 并且 a_i+p_i\le10^5，求 \sum^n_{i=1}p_i，如果数组 p 不存在，输出 -1。

思路

考虑用 dp 解题。

定义 dp_{i,j} 表示使得 2^j\mid\prod^i_{k=1}(a_k+p_k) 的最小 \sum^i_{k=1}p_k 的值，设最小的比 x 大的 2^y 的倍数减去 x 的值为 f(x,y)。

于是用瞪眼法（？）可以得出 dp_{1,i}=f(1,i)。

可以发现，对于 dp_{i,j} 可以枚举 a_i 要分担的 2 的个数，设 a_i 要分担 x 个 2，则状态转移方程可以写为 dp_{i,j}=\min_{0\le x\le j}\{dp_{i-1,j-x}+f(i,x)\}。

可是这是三重循环，会超时，考虑优化。

可以发现，当 x 过大时，因为 a_i+p_i\le 10^5 的限制，f(i,x)+dp_{i-1,j-x} 便不符合条件，因此只用从 0 枚举到 \min\{\lfloor\log_2(10^5)\rfloor,j\} 即可。

于是状态转移方程变为 dp_{i,j}=\min_{0\le x\le \min\{\lfloor\log_2(10^5)\rfloor,j\}}\{dp_{i-1,j-x}+f(i,x)\}。

虽然这还是三重循环，但因为 2^x 增长很快，所以第三重循环的时间复杂度是常数。

接下来回头再考虑 f(x,y) 如何实现。

当 x\le 2^y 时，显然可得 f(x,y)=2^y-x。

当 x>2^y 时，f(x,y)=2^y\times\lceil\frac{x}{2^y}\rceil。

代码

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

int n,k,a[505],dp[505][5005],f[505][5005];

int pow2(int a){return 1<<a;}

int find(int x,int k)//函数f(x,y) 
{
    if(k>=ceil(log2(1e5)))return 1e8;//2^k大于1e5，无解
    int r=ceil(log2(x));
    if(r<k)return pow2(k)-x;
    else
    {
        int a=ceil(1.0*x/pow2(k));
        if(pow2(k)*a>1e5)return 1e8;//答案大于1e5，无解
        return pow2(k)*a-x;
    }
}

int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=k;j++)dp[i][j]=1e8,f[i][j]=find(a[i],j);//预处理 
    }
    for(int i=0;i<=k;i++)dp[1][i]=f[1][i];//初始状态 
    for(int i=2;i<=n;i++)//dp过程
    {
        for(int j=0;j<=k;j++)
        {
            for(int l=0;l<=min((int)floor(log2(1e5)),j);l++)dp[i][j]=min(dp[i][j],dp[i-1][j-l]+f[i][l]);
        }
    }
    printf("%d",dp[n][k]==1e8? -1:dp[n][k]);//注意无解的情况 
    return 0;//代码后加return 0;是好习惯 
}

性能分析

时间复杂度：O(nk)。

空间复杂度：O(nk)。

可以通过本题。