题解"/>
atcoder:arc129(a,b,c),abc228(a,b,c)题解
arc129
A题:
题意:
输入N,L,R,求L~R这个区间内,有多少个数与N异或运算后小于N?(N^X<N)。
思路:
异或运算:在二进制下,0^0=1,1^1=0,0^1=1,1^0=1.
不难发现,当一个数的最高位1与同位置的1异或后,得到的数一定小于本身。所以只需要反复找N中的1位然后与该位置为1的数异或,结果一定小于本身。最后需要注意数在区间l-r即可。
代码如下:
#include<iostream>
#include<algorithm>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<sstream>using namespace std;typedef long long ll;ll qpow(ll a,ll b)
{int ans=1;while(b>0){if(b&1){ans*=a;}a*=a;b>>=1;}return ans;
}int main(void)
{int t=1;ll n,l,r;//cin>>t;cin>>n>>l>>r;ll res=0;for(int i=62;~i;i--){if(n>>i&1){ll lls=max(l,1ll<<i);ll rrs=min(r,(1ll<<(i+1))-1);if(rrs>=lls)res+=rrs-lls+1;}}cout<<res<<endl;
}
B题:
题意:
有以下三个函数:
- If x<lx<l: dist(l,r,x)=l-xdist(l,r
更多推荐
atcoder:arc129(a,b,c),abc228(a,b,c)题解
发布评论