Codeforces Round #843 (Div. 2) C【思维】

https://codeforces.com/contest/1775/problem/C

题意

题意是说，给你n和x，你要求出最小的满足要求的m，使得 \(n\)&\((n+1)\)&\((n+2)\)&\(...\)&\(m=x\)

若没有满足的输出-1

思路

容易知道x的范围\(0\leq x \leq n\)

若\(x\)为0，答案是 \((1 << n的最高位的bit + 1)\)

若\(x\)为n，答案就是n

否则，先将\(x\)转化成二进制，\(x\)中至少有一个1，对于一个bit来说 n 0 x 1是不可能发生的，这一位x是1 只可能n取1，这个时候恰好满足“\(x\)最右边的1及之前的部分和\(n\)中对应的部分相同”，若这个条件不满足，输出-1

再来考虑这个位置之后的序列，x中的数肯定都是0了，假设n这一段数中，最高位上的数是1，此时x对应位上的数是0，可以知道此时肯定发生了进位，但是n和x的前缀又是完全相同的，故这种情况也不合法，输出-1

那么在这一段数中，\(n\)中就算有1，也不是紧邻着\(x\)中最右边的\(1\)的，我们只需要找到\(n\)中最低位的\(1\)，设这个位置为\(i\)，答案就是 \(((n >> i + 1) | 1) << i + 1\)

code

#include<bits/stdc++.h>

#define ll unsigned long long

using namespace std;

const int N = 2e5 + 10, mod = 1e9 + 7;

int T;

ll n, x;

int main() {

    cin >> T;

    while(T--) {

        cin >> n >> x;

        if(x > n) {

            puts("-1");

            continue;

        }

        if(x == n) {

            printf("%lld\n", n);

            continue;

        }

        if(x == 0) {

            for(int i = 60; i >= 0; i--) {

                if(n >> i & 1) {

                    printf("%lld\n", (1LL << (i + 1)));

                    break;

                }

            }

            continue;

        }

        int pos = -1;

        for(int i = 0; i <= 60; i++) {

            if(x >> i & 1) {

                pos = i;

                break;

            }

        }

        // [st...pos] ,  [pos + 1, ... , en]

        bool f = 1;

        for(int i = 60; i >= pos; i--) {

            if((x >> i & 1) != (n >> i & 1)) {

                f = 0;

                break;

            }

        }

        if(pos && (n >> (pos - 1) & 1)) f = 0;

        if(!f) {

            puts("-1");

            continue;

        }

        ll ans = 0;

        for(int i = pos - 1; i >= 0; i--) {

            if(n >> i & 1) {

                ans = ((n >> i + 1) | 1) << i + 1;

                break;

            }

        }

        printf("%lld\n", ans);

    }

    return 0;

}

巴特西

Codeforces Round #843 (Div. 2) C【思维】

题意

思路

code

最新文章

热门文章