Pair(二进制处理+数位dp)（2019牛客暑期多校训练营（第七场））

示例：

输入：

3
3 4 2
4 5 2
7 8 5

输出：5 7 31

题意：存在多少对<x,y>满足x&y>C或x^y<C的条件。（0<x<=A,0<y<=B）

题解：首先逆向考虑，求有多少对(x,y)满足x&y<=C且x^y>=C，然后用A*B去减它即可。然后就是数位dp模板题(数位dp不懂可先补一下知识再看这题)，用dp[pos][ia][ib][iand][ixor]表示到第pos位的个数，ia位表示是否是A的上限，ib表示是否是B的上限，iand表示与的上限是否是C，ixor表示异或的下限是否是C，（当处理至某一位不为上下限时，即其上下限可随便取值，不懂将solve()中//printf("dp[%d][%d][%d][%d][%d]=%lld\n",pos,i,j,i&j,i^j,ans);的斜杠去掉，输入示例看过程）因为该dp表示的值与输入的A,B,C有关，所以每次都要memset置-1。因为dfs存在x或y为0的情况。而x、y最小是1，所以要减掉x或y为0的情况。x为0的个数有max(0,B-C+1)，即y>=C;同理，y为0有max(0,A-C+1)种。

code:

#include<bits/stdc++.h>

#define LL long long

using namespace std;

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

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

LL solve(int pos,int ia,int ib,int iand,int ixor)

{

    if(pos<)return ;

    if(dp[pos][ia][ib][iand][ixor]!=-)return dp[pos][ia][ib][iand][ixor];

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

    if(ia)up1=a[pos];//如果ia/ib/iand/ixor为0，即此处无上下限约束

    if(ib)up2=b[pos];

    if(iand)up3=c[pos];

    if(ixor)up4=c[pos];

    LL ans=;

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

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

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

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

            ans+=solve(pos-,ia&&(i==a[pos]),ib&&(j==b[pos]),iand&&((i&j)==c[pos]),ixor&&((i^j)==c[pos]));

            //printf("dp[%d][%d][%d][%d][%d]=%lld\n",pos,i,j,i&j,i^j,ans);

        }

    }

    return dp[pos][ia][ib][iand][ixor]=ans;

}

int main()

{

    scanf("%d",&t);

    while(t--){

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

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

        LL tA=A,tB=B,tC=C;

        memset(a,,sizeof(a));memset(b,,sizeof(b));memset(c,,sizeof(c));

        int i=,j=,k=;

        while(tA||tB||tC){//处理A,B,C的二进制

            if(tA){a[i++]=tA&;tA=tA>>;}

            if(tB){b[j++]=tB&;tB=tB>>;}

            if(tC){c[k++]=tC&;tC=tC>>;}

        }

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

        summ=(A*B)-summ;

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

    }

    return ;

}

巴特西

Pair(二进制处理+数位dp)（2019牛客暑期多校训练营（第七场））

最新文章

热门文章