专栏文章

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

WWonderStone_
P12316题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min63f8n
此快照首次捕获于
2025/12/01 21:10
3 个月前
此快照最后确认于
2025/12/01 21:10
3 个月前
查看原文

循环位运算

题目大意

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

思路分析

注意到每个数最大只是二进制 3232 位数（不然 int 也存不下），因此时间完全支持我们把每个数“左循环”的所有结果全部预处理出来，而第 ii 次“左循环”所得的结果就需要花费 ii 次“操作次数”（因此不妨把原来的数当做第 00 个数）。\\ 于是接下来问题就变成了：对于每一个数，都从一堆预处理得到的数中选一个，并记一花费值（即“左循环”次数）与价值（即“左循环”若干次后的数值），求最多 mm 次花费可获得的最大价值。
是的，依旧背包改一点点。
所以一点点是哪一点？还记得经典的 0101 背包吗？与此题目唯一不同的是，前者每次只考虑当前物品选不选，而后者必须考虑当前物品在若干个预处理所得的数（包括原数）中选哪一个。\\ 因此此题目只需要在经典 0101 背包的双层循环（ii 从 11 到 nn 表示将在前 ii 个物品中选取，jj 从 00 到 mm 表示背包空间为 jj 时的结果）中在套入一层循环，枚举 kk 从 00 到 jj 表示第 ii 个数左移 kk 次时的结果（即在第 ii 个数上花费 kk 时的结果），而转移方程几乎不变。
最后统计答案，由于题目要求不超过 mm 次操作而不是恰好 mm 次操作，因此答案在 dpn,i(0≤i≤m)dp_{n,i} (0 \le i \le m) 中选取最大值即可。

代码详解

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

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...