牛客多校第六场-H-Pair

链接：https://ac.nowcoder.com/acm/contest/887/H
来源：牛客网

题目描述

Given three integers A, B, C. Count the number of pairs <x ,y> (with 1≤x≤Aand1≤y≤B)
such that at least one of the following is true:
- (x and y) > C
- (x xor y) < C
 
("and", "xor" are bit operators)

输入描述:

The first line of the input gives the number of test cases,T(T≤100). T test cases follow.

For each test case, the only line contains three integers A, B and C.
1≤A,B,C≤10^9

输出描述:

For each test case, the only line contains an integer that is the number of pairs satisfying the condition given in the problem statement. 示例1

输入

3 3 4 2 4 5 2 7 8 5

输出

5 7 31

数位dp求 x&y<=c && x^y>=c的个数然后用所有方案剪掉 具体见代码 #include <bits/stdc++.h> #define ll long long using namespace std; int T,A,B,C; int a[35],b[35],c[35]; ll f[35][2][2][2][2]; void cal(int x,int v[]) {for (int i=0;i<=30;i++) v[i]=(x>>i)&1; } ll dfs(int pos,bool lima,bool limb,bool limand,bool limxor) // 位 x<a y<b x&y<c x^y>c {if (pos==-1) return 1;if (f[pos][lima][limb][limand][limxor]!=-1) return f[pos][lima][limb][limand][limxor];int aa=lima?a[pos]:1; //lima=1说明之前一直相等当前位取要<=a，否则说明之前<a了当前位可以乱取int bb=limb?b[pos]:1;int c1=limand?c[pos]:1; //同理如果之前x&y一直等于c那么当前位要x&y<=c，否则就可以乱取int c2=limxor?c[pos]:0;ll &ret=f[pos][lima][limb][limand][limxor];ret=0;for (int i=0;i<=aa;i++)for (int j=0;j<=bb;j++){if ((i&j)>c1) continue;if ((i^j)<c2) continue;ret+=dfs(pos-1,lima&&i==aa,limb&&j==bb,limand&&(i&j)==c1,limxor&&(i^j)==c2);}return ret; } int main() {scanf("%d",&T);while(T--){scanf("%d%d%d",&A,&B,&C);memset(a,0,sizeof(a));memset(b,0,sizeof(b));memset(c,0,sizeof(c));memset(f,-1,sizeof(f));cal(A,a); cal(B,b); cal(C,c);ll ans=dfs(30,1,1,1,1);ans-=max(0,A-C+1);ans-=max(0,B-C+1); //减掉x,y为0的情况printf("%lld\n",(ll)A*B-ans);}return 0; } View Code

 

转载于:https://www.cnblogs.com/tetew/p/11324428.html

总结

以上是生活随笔为你收集整理的牛客多校第六场-H-Pair的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。