agc015D A or...or B Problem

题意：求用若干个（至少一个）[A,B]中的数进行or操作能得到多少本质不同的数

$1 \leq A \leq B < 2^{60}$

一直在想数位dp，看了题解之后感觉自己就是个sb

我们先把$A,B$前面(高位)相同的二进制位忽略掉，反正无论怎么或都是一样的

那么我们找到一个最大的$p$使得$A>>p \& 1 \ne B>>p \& 1$

下面的$A,B$都是把$p+1$位之后忽略掉(看作0)之后的。

令$T=1<<p$，我们把$[A,B]$看作两部分，$X=[A,T)$和$Y=[T,B]$

我们可以分为三种情况：

1、只选$X$里面的数，最后或出来的数的范围是$[A,T)$

2、只选$Y$里面的数。

令$k$是$B$里面最高位的1的位置(除了$p$这一位)

最后或出来的数的范围就是$[T,T+(1<<k+1)-1]$

3、两个集合里面的数都要选，最后或出来的数的范围是$[T+A,2*T-1]$，就是选$T$和一个$X$里面的数

注意第二种情况和第三种情况有重叠部分。

我怎么把题解翻译了一遍……

这么低的复杂度也让我有点惊讶呢

这种题特点在于，集合里面数是连续的，然后或起来也就是几段连续的。

//Serene

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#include<cmath>

using namespace std;

#define ll long long

#define db double

#define For(i,a,b) for(int i=(a);i<=(b);++i)

#define Rep(i,a,b) for(int i=(a);i>=(b);--i)

#define lc son[pos][0]

#define rc son[pos][1]

const int W=60;

ll n,m,ans;

char cc;ll ff;

template<typename T>void read(T& aa) {

	aa=0;ff=1; cc=getchar();

	while(cc!='-'&&(cc<'0'||cc>'9')) cc=getchar();

	if(cc=='-') ff=-1,cc=getchar();

	while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();

	aa*=ff;

}

int lb(ll x) {int rs=0;while(x) rs++,x>>=1;return rs;}

int main() {

	read(n); read(m);

	ll p=W,x;

	while(p>=0&&((n>>p)&1)==((m>>p)&1)) p--;

	if(p>=0) {

		n&=(1LL<<p+1)-1;

		m&=(1LL<<p)-1;

		ans+=(1LL<<p)-n;

		x=lb(m);

		ans+=(1LL<<x);

		n=max(n,1LL<<x);

		ans+=(1LL<<p)-n;

	}

	else ans=1;

	printf("%lld\n",ans);

	return 0;

}

巴特西

agc015D A or...or B Problem

最新文章

热门文章