Pair

题意

给出A B C，问x取值[1,A]和y取值[1,B]存在多少组pair<x,y>满足以下最小一种条件，\(x \& y >c\),\(x\) xor \(y<c\)

分析

有关二进制位运算的操作肯定是和要联想到和位的关系的，我们可以考虑枚举每一位计数，但这样会复杂度爆炸，枚举每一位有没有想到什么？数位dp,我们可以考虑把题目条件装化，全集好求，那么求他的补集，求所有\(x \& y <=c\)并且\(x\) xor \(y>=c\)，然后用全集A×B减去就是答案了。

这里的数位dp状态为dp[位数][A枚举上界][B枚举上界][是否满足x and y< c ][是否满足x xor y>c][A是否取了不为0的数][B是否取了不为0的数]

这里有一个关键点，状态中[是否满足x and y< c ][是否满足x xor y>c] 没有取等号，为什么不取等号呢，因为如果条件相反大于的时候我们会直接continue，那么状态就只剩下了到目前位置等于c,和不等于c的相应条件了，这是两种不同的状态，但是都是合法的，所以要记录下来。

刚开始写的时候状态为dp[位数][是否满足x and y< c ][是否满足x xor y>c][A是否取了不为0的数][B是否取了不为0的数] ，即把两个limit没有放到状态里面，就T了。因为常规的写法数位dp是求两个区间之间的值，所以dp的状态要对两个数通用，如果加了limit的话，对于我们的状态定义来说，同一个状态定义对两个不同的数实际上是有不同的，而limit没限制的条件居多，所以之前写的数位dp题状态都是没有limit1的情况，这些情况都暴力解决了，当然也可以在这些数位dp的题目中加上limit的状态，但是这样就要每次求之前memset dp数组了。而在本题中，因为只进行一次操作，并且都是01串，两个limit1的情况也是非常多的，如果不记录这两个状态的话，就会导致超时了T_T

第一份AC 第二份状态少了T

#include<bits/stdc++.h>

#define pb push_back

#define F first

#define S second

#define pii pair<int,int>

#define mkp make_pair

typedef long long ll;

using namespace std;

const int maxn=5e5+5;

int abit[35],bbit[35],cbit[35];

const int mod=1e9+7;

int n,q;

ll dp[35][3][3][3][3][3][3];

ll dfs(int dep,bool limit1,bool limit2,bool ok1,bool ok2,bool ling1,bool ling2){

    if(dep==0){

        return ling1&&ling2;

    }

    if(dp[dep][ok1][ok2][ling1][ling2][limit1][limit2]!=-1)return dp[dep][ok1][ok2][ling1][ling2][limit1][limit2];

    ll ans=0;

    int up1=limit1?abit[dep]:1;

     int up2=limit2?bbit[dep]:1;

    for(int i=0;i<=up1;i++){

        for(int j=0;j<=up2;j++){

            if(!ok1&&(i&j)>cbit[dep])continue;

            if(!ok2&&(i^j)<cbit[dep])continue;

            ans+=dfs(dep-1,limit1&&i==up1,limit2&&j==up2,ok1||((i&j)<cbit[dep]),ok2||((i^j)>cbit[dep]),ling1||i!=0,ling2||j!=0);

        }

    }

    return dp[dep][ok1][ok2][ling1][ling2][limit1][limit2]=ans;

}

ll solve(int a,int b,int c){

    memset(dp,-1,sizeof(dp));

    for(int i=1;i<=30;i++){

        abit[i]=a&1;

        bbit[i]=b&1;

        cbit[i]=c&1;

        a>>=1;

        b>>=1;

        c>>=1;

    }

    return dfs(30,1,1,0,0,0,0);

}

int main(){

    int t;

    scanf("%d",&t);

    int a,b,c;

    while(t--){

        scanf("%d%d%d",&a,&b,&c);

        printf("%lld\n",1ll*a*b-solve(a,b,c));

    }

    return 0;

}

#include<bits/stdc++.h>

#define pb push_back

#define F first

#define S second

#define pii pair<int,int>

#define mkp make_pair

typedef long long ll;

using namespace std;

const int maxn=5e5+5;

int abit[35],bbit[35],cbit[35];

const int mod=1e9+7;

int n,q;

ll dp[35][3][3][3][3];

ll dfs(int dep,bool limit1,bool limit2,bool ok1,bool ok2,bool ling1,bool ling2){

    if(dep==0){

        return ling1&&ling2;

    }

    if(!limit1&&!limit2&&dp[dep][ok1][ok2][ling1][ling2]!=-1)return dp[dep][ok1][ok2][ling1][ling2];

    ll ans=0;

    int up1=limit1?abit[dep]:1;

     int up2=limit2?bbit[dep]:1;

    for(int i=0;i<=up1;i++){

        for(int j=0;j<=up2;j++){

            if(!ok1&&(i&j)>cbit[dep])continue;

            if(!ok2&&(i^j)<cbit[dep])continue;

            ans+=dfs(dep-1,limit1&&i==up1,limit2&&j==up2,ok1||((i&j)<cbit[dep]),ok2||((i^j)>cbit[dep]),ling1||i!=0,ling2||j!=0);

        }

    }

    return dp[dep][ok1][ok2][ling1][ling2]=ans;

}

ll solve(int a,int b,int c){

    memset(dp,-1,sizeof(dp));

    for(int i=1;i<=30;i++){

        abit[i]=a&1;

        bbit[i]=b&1;

        cbit[i]=c&1;

        a>>=1;

        b>>=1;

        c>>=1;

    }

    return dfs(30,1,1,0,0,0,0);

}

int main(){

    int t;

    scanf("%d",&t);

    int a,b,c;

    while(t--){

        scanf("%d%d%d",&a,&b,&c);

        printf("%lld\n",1ll*a*b-solve(a,b,c));

    }

    return 0;

}

巴特西

牛客多校第七场H Pair 数位dp理解

Pair

题意

分析

最新文章

热门文章