Codeforces Round #843 (Div. 2) C Interesting Sequence

绝地灬酷狼 2024-03-30 17:31 177阅读 0赞

Problem - C - Codeforces

题意：

给定n和x，求最小的m使得：

0e0d1d8e52c5874275573ed2ba3637ad.png

n和x范围是1e18

思路：

看到1e18，要不就是打表找规律，要不就是O(1)，要不就是O(logn)

因为这题是bitmask，因此按位考虑，是O(logn)的

让我们凭空求m，要不枚举，要不二分，要不直接求

枚举肯定不行

二分的话不能维护区间与的结果

因此我们根据n和x的位表示直接求m

33b3849ade46b2632be7818f5e8af155.png

Code：

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. int n,x;
  5. void solve(){
  6.     cin>>n>>x;
  7.     bitset<64> b1(n),b2(x);
  8.     int l=n,r=5e18;
  9.     for(int i=63;i>=0;i--){
  10.         if(b1[i]==0&&b2[i]==0) continue;
  11.         else if(b1[i]==0&&b2[i]==1){
  12.             cout<<-1<<'\n';
  13.             return;
  14.         }else if(b1[i]==1&&b2[i]==1){
  15.             r=min(r,(n/(1ll<<i)+1)*(1ll<<i)-1);
  16.         }else{
  17.             l=max(l,(n/(1ll<<i)+1)*(1ll<<i));
  18.         }
  19.     }
  20.     if(l<=r) cout<<l<<'\n';
  21.     else cout<<-1<<'\n';
  22. }
  23. signed main(){
  24.     ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  25.     int __=1;cin>>__;
  26.     while(__--)solve();return 0;
  27. }

发表评论

表情：
评论列表 （有 0 条评论，177人围观）

还没有评论，来说两句吧...

相关阅读