Codeforces Round 949-(Div.2)B题题解

B. Turtle and an Infinite Sequence

题意

有一个无限长的序列 。初始：

每过一秒，序列中的每个元素都会同时发生变化，具体变化为：每一个变化为(特别地，)

问：秒后的值

解题思路

不难发现，秒后(其中)

而求解到的或和，我们按位枚举二进制位，累加该二进制位对答案的贡献值，即为。

具体来说：

• 若区间[l,r]存在有二进制位为的数，则其对答案的贡献值为,反之该位对答案的贡献值为
• 判断存在有二进制位为的数：在该二进制位或，区间必然存在有二进制位为的数，反之则不存在

解题代码

#include <bits/stdc++.h>
using namespace std;
typedef long long  ll;
void solve()
{
    int n,m;cin>>n>>m;
    ll l=max(0,n-m),r=n+m;
    ll ans=0,sub=r-l,lst=0;
    for(int i=0;i<=35;i++){
      if(l&(1ll<<i)) ans+=(1ll<<i);
      else {
        if(lst+sub>=(1ll<<i)) ans+=(1ll<<i);
      }
      if(l&(1ll<<i)) lst+=(1ll<<i);
    }
    cout<<ans<<"\n";
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t;
    cin>>t;
    while(t--)
    solve();
    return 0;
}