题解：P12316 [蓝桥杯 2024 国 C] 循环位运算

· · 题解

循环位运算

题目大意

对于含有 n 个 32 位非负整数的 a 数组，每次操作可以选其任意一个数，将其“左循环”一次，即把此数的最高位（第 32 位）取出并放入最低位，同时将原来的其余位均左移一次来“让位”。\\ 最多只能操作 m 次，求那时 n 个数的和的最大值。

思路分析

注意到每个数最大只是二进制 32 位数（不然 int 也存不下），因此时间完全支持我们把每个数“左循环”的所有结果全部预处理出来，而第 i 次“左循环”所得的结果就需要花费 i 次“操作次数”（因此不妨把原来的数当做第 0 个数）。\\ 于是接下来问题就变成了：对于每一个数，都从一堆预处理得到的数中选一个，并记一花费值（即“左循环”次数）与价值（即“左循环”若干次后的数值），求最多 m 次花费可获得的最大价值。

是的，依旧背包改一点点。

所以一点点是哪一点？还记得经典的 01 背包吗？与此题目唯一不同的是，前者每次只考虑当前物品选不选，而后者必须考虑当前物品在若干个预处理所得的数（包括原数）中选哪一个。\\ 因此此题目只需要在经典 01 背包的双层循环（i 从 1 到 n 表示将在前 i 个物品中选取，j 从 0 到 m 表示背包空间为 j 时的结果）中在套入一层循环，枚举 k 从 0 到 j 表示第 i 个数左移 k 次时的结果（即在第 i 个数上花费 k 时的结果），而转移方程几乎不变。

最后统计答案，由于题目要求不超过 m 次操作而不是恰好 m 次操作，因此答案在 dp_{n,i} (0 \le i \le m) 中选取最大值即可。

代码详解

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,dp[1005][1005],t[1005][1005],ans;
//t[i][j]表示第i个数左循环j次后的结果
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>t[i][0]; //原数自然不需要操作（即左循环0次）
        //执行预处理
        int now=t[i][0];
        for(int j=1;j<=m;j++){
            now<<=1ll; //整体左循环一次
            int p=(now>>32)&1ll; //取出最高位
            now+=p; //将最高位加到最低位
            now-=p<<32; //原最高位左移后的位置归零
            t[i][j]=now;
        }
    }
    //背包（状态定义详见上文）
    for(int i=1;i<=n;i++)
        for(int j=0;j<=m;j++)
            for(int k=0;k<=j;k++)
                dp[i][j]=max(dp[i][j],dp[i-1][j-k]+t[i][k]); //第i个数在j的背包容量下取左循环k次的结果时，更新dp[i][j]
    //计算答案（详见上文）
    for(int i=0;i<=m;i++) ans=max(ans,dp[n][i]);
    cout<<ans;
    return 0;
}