題意：求用若干個（至少一個）[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; }

　　

轉載于:https://www.cnblogs.com/Serene-shixinyi/p/9077134.html

總結

以上是生活随笔為你收集整理的agc015D A or...or B Problem的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。