JZOJ 5682 数字

Description

两个数字$x$和$y$，它们需要满足$x∨y=T$，且$Lx≤x≤Rx$ ,$Ly≤y≤Ry$，求$x∧y$有多少种可能的不同的取值。

Data Constraint

$0<=T,Lx,Rx,Ly,Ry<2^{61}$

Code

Ps.没开long long炸剩暴力分。
先考虑一下如果没有上下界的限制，那答案为显然为$2^{bits(T)}$，其中$bits(T)$表示二进制下$1$的个数。

考虑暴力。
暴力枚举可能的$x∧y$，从高往低位枚举$x∧y$，假设当前枚举到第$i$位，$x∧y$的前i位和枚举出来的前$i$位的($x$,$y$)一定有很多对，我们将$x$分成四种，分别是$x$的前$i$位卡上界，卡下界，上下界都卡，上下界都不卡，同样的$y$也分成四种，那么这些二元组最多能分成$16$种。

当递归到某个状态(设当前递归到了第$i$位)发现发现存在一个二元组它的$x$和$y$都不卡上下界，那显然剩下的位置可以乱填，因为前i位上下界都不卡的话那后面无论填什么都不可能出上下界了，答案加上$2^{\sum_{j=i+1}^wT_j}$，其中$w$是$T$在二进制下的位数。

递归的时候顺便带上一个$2^{16}$级别的二进制数表示到当前状态下$16$种中的每种二元组是否存在，转移到下个状态的话随便分类讨论下就好了，加上个记忆化就能很好地保证复杂度了，时间复杂度$O(2^{16}w)$，然而我没加记忆化都能虐暴标程。

Code

/*记忆化什么的不存在的*/
#include
#include
#include
#include#define fo(i,j,l) for(int i=j;i<=l;++i)
#define fd(i,j,l) for(int i=j;i>=l;--i)using namespace std;
typedef long long ll;
const ll N=80;int w[N];
ll q1[2][N],q2[2][N],p1[2][N],p2[2][N],f[N];
ll d[N][3],m2[N],oo;
int qq[3],pp[3];
ll ans,T,lx,rx,ly,ry;inline int max(int a,int b)
{return a>b?a:b;}inline bool ok1(int po,ll op)
{return (q1[1][po]<=op)&&(q2[1][po]>=op);}inline bool oo1(int po,ll op)
{return (q1[1][po]<op)&&(q2[1][po]>op);}inline bool ok2(int po,ll op)
{return (p1[1][po]<=op)&&(p2[1][po]>=op);}inline bool oo2(int po,ll op)
{return (p1[1][po]<op)&&(p2[1][po]>op);}inline ll judge(ll p)
{return p<0?-1:p;}void dg(int o)
{if(o==0){ans=ans+1; return;}ll v[N][3]; int k=oo;fo(i,1,oo)v[i][1]=d[i][1],v[i][2]=d[i][2];if(w[o]==0){oo=0;fo(i,1,k)if((ok1(o,v[i][1]<<1)||v[i][1]==-1)&&(ok2(o,v[i][2]<<1)||v[i][2]==-1)){d[++oo][1]=judge(v[i][1]*2); d[oo][2]=judge(v[i][2]*2);}if(oo)dg(o-1);}else{oo=0;fo(i,1,k){if((ok1(o,(v[i][1]<<1)^1)||v[i][1]==-1)&&(ok2(o,v[i][2]<<1)||v[i][2]==-1))d[++oo][1]=judge((v[i][1]*2)+1),d[oo][2]=judge(v[i][2]*2);if((ok1(o,v[i][1]<<1)||v[i][1]==-1)&&(ok2(o,(v[i][2]<<1)^1)||v[i][2]==-1))d[++oo][1]=judge(v[i][1]*2),d[oo][2]=judge((v[i][2]*2)+1);}int ok=0;fo(i,1,oo){if(oo1(o,d[i][1]))d[i][1]=-1;if(oo2(o,d[i][2]))d[i][2]=-1;if(d[i][1]+d[i][2]==-2){ok=1; break;}}if(ok==1)ans=ans+m2[f[o-1]];else if(oo)dg(o-1);ok=oo=0;fo(i,1,k)if((ok1(o,(v[i][1]<<1)^1)||v[i][1]==-1)&&(ok2(o,(v[i][2]<<1)^1)||v[i][2]==-1))d[++oo][1]=judge((v[i][1]*2)+1),d[oo][2]=judge((v[i][2]*2)+1);fo(i,1,oo){if(oo1(o,d[i][1]))d[i][1]=-1;if(oo2(o,d[i][2]))d[i][2]=-1;if(d[i][1]+d[i][2]==-2){ok=1; break;}}if(ok==1)ans=ans+m2[f[o-1]];else if(oo)dg(o-1);}oo=k;fo(i,1,oo)d[i][1]=v[i][1],d[i][2]=v[i][2];
}int main()
{cin>>T>>lx>>rx>>ly>>ry;
    m2[0]=1;
    fo(i,1,61)m2[i]=m2[i-1]<<1;
    ll x=T;
    for(;x;x>>=1)w[++w[0]]=x&1;
    x=lx;
    for(;x;x>>=1)q1[0][++qq[1]]=x&1;
    x=rx;
    for(;x;x>>=1)q2[0][++qq[2]]=x&1;
    x=ly;
    for(;x;x>>=1)p1[0][++pp[1]]=x&1;
    x=ry;
    for(;x;x>>=1)p2[0][++pp[2]]=x&1;
    int ws=max(w[0],qq[1]); ws=max(ws,qq[2]); 
    ws=max(ws,pp[1]); ws=max(ws,pp[2]);
    fo(i,1,ws)f[i]=f[i-1]+w[i];
    fd(i,ws,1){
        q1[1][i]=(q1[1][i+1]<<1)^q1[0][i];
        q2[1][i]=(q2[1][i+1]<<1)^q2[0][i];
        p1[1][i]=(p1[1][i+1]<<1)^p1[0][i];
        p2[1][i]=(p2[1][i+1]<<1)^p2[0][i];
    }
    oo=1;
    d[1][1]=d[1][2]=0;
    dg(ws);
    cout<
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！