例题引入 P13008

题目描述

给定一个非负整数

x

，你要经过若干次以下操作将其变成

y

，求最小代价：

选择一个 $0\leq i\leq k$ ，花费 $a_i$ 代价将 $x$ 加或减 $2^i$ 。

注意：你在操作时不需要保证 $x$ 为非负整数。

思路分析

取

d=|x-y|

，因为每次操作相当与在二进制的一位上加一，所以考虑将

d

按二进制进行数位 DP，这道题和做菜一样难点在于进味（进位）。

Solution

因为

a

数组可能有冗余，所以先对它去除冗余元素

a_i=\min(a_{i-1}*2,a_i)

。
用

dp_{i,c}

表示已经处理完

i

位，再是否向

i+1

进位，具体转移见代码中。
可以发现只须要枚举到

d

的二进制位数加一即可，因为再往后不可能再产生更优解了，~~我可以证明这个结论，但是我必须去喂猫了~~，这个结论很显然。

Code

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=40;
int a[N],dp[N][2];

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int T;
	cin>>T;
	for(;T--;)
	{
		int x,y,k;
		memset(a,127,sizeof a);
		memset(dp,63,sizeof dp);
		cin>>x>>y>>k;
		int d=abs(x-y),m=0;
		for(int i=d;i;m++) i>>=1;
		for(int i=0;i<=k;i++) cin>>a[i];
		for(int i=1;i<=m;i++) a[i]=min(a[i-1]<<1,a[i]);
		if(d&1) dp[0][0]=dp[0][1]=a[0];
		else dp[0][0]=0;
		for(int i=1;i<=m;i++)
		{
			if((d>>i)&1)
			{
				dp[i][0]=dp[i-1][0]+a[i];
				dp[i][1]=min(dp[i-1][1],dp[i-1][0]+a[i]);
			}
			else
			{
				dp[i][0]=min(dp[i-1][0],dp[i-1][1]+a[i]/*将这一位减一*/);
				dp[i][1]=dp[i-1][1]+a[i];
			}
		}
		cout<<dp[m][0]<<'\n';
	}
	return 0;
}

总结

当发现操作是与

2

的幂有关时，可以考虑按二进制位进行操作。

例题引入 P8019

题目描述

给定一个长度为

n

的序列

a_1, a_2, \cdots, a_n

，请将它划分为

m

段连续的区间，设第

i

段的费用

c_i

为该段内所有数字的异或和，则总费用为

c_1 \operatorname{or} c_2 \operatorname{or} \cdots \operatorname{or} c_m

。请求出总费用的最小值。

思路分析

涉及区间的异或和，我们考虑维护前缀异或和。要总费用尽可能的小，就贪心的让分的每一段的高位尽可能为零，那就要考虑把每一位拆开进行处理。

Solution

从高位到地位枚举。

如果这一位的这个数的前缀异或和的零的个数少于 $m$ ，那么可以证明这一位不可能为零。
如果这一位的最后一个数的前缀疑惑和，那么不可能存在一种方案使得这一位为零。
因为低位要在符合高位为零的情况下为零，所以如果这一位的这个数为零但是这个数不能作为高位的隔断，那么这个零无法起到隔断作用，即这个零无效不统计在内。

Code

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+10;
int n,m,a[N],maxv,s,ans;
bool vis[N];

signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		maxv=max(maxv,a[i]);
		a[i]^=a[i-1];
	}
	for(;maxv;s++) maxv>>=1;
	for(int i=s-1;i>=0;i--)
	{
		int d=0;
		for(int j=1;j<=n;j++) d+=(!((a[j]>>i)&1)&&!vis[j]);//这个数的这一位为零且能作为之前高位的隔断才有效
		if(d<m||(a[n]>>i)&1)
		{
			ans+=1ll<<i;
			continue;
		}
		for(int j=1;j<=n;j++) vis[j]=((a[j]>>i)&1||vis[j]);//如果这一位为一那么就不能作为隔断
	}
	cout<<ans;
	return 0;
}

总结

涉及位运算的操作或者计算时，可以考虑拆位进行操作。

位运算常见题型及解法

文章操作

例题引入 P13008

题目描述

思路分析

Solution

Code

总结

例题引入 P8019

题目描述

思路分析

Solution

Code

总结

相关推荐

评论

位运算常见题型及解法