2019牛客暑期多校训练营（第七场）-H Pair（数位dp）

题目链接：https://ac.nowcoder.com/acm/contest/887/H

题意：给定A,B,C，求有多少对(x,y)满足x&y>C或者x^y<C，其中1<=x<=A,1<=y<=B。

思路：首先逆向考虑，求有多少对(x,y)满足x&y<=C且x^y>=C，然后用A*B去减它即可。然后就是数位dp模板题，用dp[pos][la][lb][land][lxor]表示到第pos位的个数，la位表示是否是A的上限，lb表示是否是B的上限，land表示与的上限是否是C，lxor表示异或的下限是否是C，因为该dp表示的值与输入的A,B,C有关，所以每次都要memset置-1。因为dfs存在x或y为0的情况，而x、y最小是1，所以要减掉x或y为0的情况。x为0的个数有max(0,B-C+0)，即y>=C;同理，y为0有max(0,A-C+0)种。

AC代码：

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

typedef long long LL;

LL dp[][][][][],A,B,C,ans;

int T,a[],b[],c[];

void init(){

    memset(a,,sizeof(a));

    memset(b,,sizeof(b));

    memset(c,,sizeof(c));

    LL aa=A,bb=B,cc=C;

    int pos=;

    while(aa){

        a[pos++]=aa%;

        aa/=;

    }

    pos=;

    while(bb){

        b[pos++]=bb%;

        bb/=;

    }

    pos=;

    while(cc){

        c[pos++]=cc%;

        cc/=;

    }

}

LL dfs(int pos,int la,int lb,int land,int lxor){

    if(pos<) return ;

    if(dp[pos][la][lb][land][lxor]!=-) return dp[pos][la][lb][land][lxor];

    LL res=;

    int up1=,up2=,up3=,up4=;

    if(la) up1=a[pos];

    if(lb) up2=b[pos];

    if(land) up3=c[pos];

    if(lxor) up4=c[pos];

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

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

            if((i&j)>up3) continue;

            if((i^j)<up4) continue;

            res+=dfs(pos-,la&&(i==a[pos]),lb&&(j==b[pos]),land&&((i&j)==c[pos]),lxor&&((i^j)==c[pos]));

        }

    return dp[pos][la][lb][land][lxor]=res;

}

int main(){

    scanf("%d",&T);

    while(T--){

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

        scanf("%lld%lld%lld",&A,&B,&C);

        init();

        ans=dfs(,,,,);

        ans=ans-max(A-C+,0LL)-max(B-C+,0LL);

        printf("%lld\n",A*B-ans);

    }

    return ;

}

巴特西

2019牛客暑期多校训练营（第七场）-H Pair（数位dp）

最新文章

热门文章