当前位置：首页 > news >正文

B. Turtle and an Infinite Sequence区间或和

news 来源：原创 2024/9/21 22:39:17

题目链接

区间或和有公式，如果求的是【l，r】区间或和，设x是l和r从高位到低位第一位二进制不同的位置，那么ans就是 l | (（1<<(x+1)）-1) ,比如101111 和100111答案就是100111 | 1111

也可以去n值去判断它的每一位是否可以取到1，如果n值本身有1，ans该位就有1。我们设判断的位置是d位，那么我们看看它能不能从小的数（左边的数）或过来，比如n=10011，l=100，那么第3一位0其实可以或上100。我们令x为n%2^d, x就是11，如果n大于等于2^d（前提条件），且n可以减去x+1（也就是说让n变成1111，也就是从前面借位，让后面都是1，可以减去x+1表示左区间长度大于等于x+1），表示该为1可以从左区间获得，或者说该位的0就是左区间为1时进位得到的。

也可以去判断右区间。n离进位最近距离就是2^d-x,如果右区间包括了这个长度，也可以得到1.

最后只需要判断min（x+1,2^d-x）是否<=m即可（前者得保证n大于等于2^d，也就是说存在高位）.

代码1：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
typedef unsigned long long ull;
typedef pair<ll,ll> pii;
const int inf=0x3f3f3f3f;
const int N=1e6+10;
const int mod=1e9+7;
const ll INF=2e9+10;
mt19937_64 rd(23333);
uniform_real_distribution<double> drd(0.000001,0.99999);void solve(){int n,m,l,r;cin>>n>>m;l=max(0ll,n-m),r=n+m;int ans=l;for(int i=40;i>=0;i--){if((1ll<<i)&(l^r)){ans|=((1ll<<(i+1))-1);break;}}cout<<ans<<endl;
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int t=1;cin>>t;while(t--){solve();}return 0;
}

代码2：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
typedef unsigned long long ull;
typedef pair<ll,ll> pii;
const int inf=0x3f3f3f3f;
const int N=1e6+10;
const int mod=1e9+7;
const ll INF=2e9+10;
mt19937_64 rd(23333);
uniform_real_distribution<double> drd(0.000001,0.99999);int n;
int a[N];void solve(){int n,m,l,r;cin>>n>>m;int ans=0;for(int i=0;i<=40;i++){if((n>>i)&1){ans|=(1ll<<i);continue;} int x=n&((1ll<<i)-1);int t=(1ll<<i)-x;if(n>=(1ll<<i))t=min(t,x+1);//if(x>=(1ll<<i)||t<=m)if(t<=m)ans|=(1ll<<i);}cout<<ans<<endl;
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int t=1;cin>>t;while(t--){solve();}return 0;
}