B. Code For 1 一个类似于线段树的东西

http://codeforces.com/contest/768/problem/B

我的做法是，观察到，只有是x % 2的情况下，才有可能出现0

其他的，都是1来的，所以开始的ans应该是R - L + 1

那么现在就是要看那些是x % 2的，然后放在的位置是属于【L, R】的，有多少个0，减去就行。

一开始，总长度是可以算出来的，然后就能算出一开始的n % 2的位置是那个，就是mid了，然后根据L和R选择递归

左边还是右边，然后我发现类似于线段树。。

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <assert.h>

#define IOS ios::sync_with_stdio(false)

using namespace std;

#define inf (0x3f3f3f3f)

typedef long long int LL;

#include <iostream>

#include <sstream>

#include <vector>

#include <set>

#include <map>

#include <queue>

#include <string>

#include <bitset>

const int maxn = 1e6 + 20;

LL n, L, R;

LL calc(LL val) {

    if (val > 1) {

        return 2 * calc(val / 2);

    }

    return 1;

}

LL ans;

void dfs(LL cur, LL L, LL R, LL be, LL en) {

    if (cur == 0) {

        return;

    }

    if (be == en) {

        return;

    }

    LL mid = (be + en) >> 1;

    if (L <= mid && mid <= R && cur % 2 != 1) {

        ans--;

    }

    if (L > mid) {

        dfs(cur / 2, L, R, mid + 1, en);

    } else if (R <= mid) {

        dfs(cur / 2, L, R, be, mid);

    } else {

        dfs(cur / 2, L, R, be, mid);

        dfs(cur / 2, L, R, mid + 1, en);

    }

}

void work() {

    cin >> n >> L >> R;

    if (n == 0) {

        cout << 0 << endl;

        return;

    }

    ans = R - L + 1;

    dfs(n, L, R, 1, 2 * calc(n) - 1);

    cout << ans << endl;

}

int main() {

#ifdef local

    freopen("data.txt", "r", stdin);

//    freopen("data.txt", "w", stdout);

#endif

    work();

    return 0;

}

巴特西

B. Code For 1 一个类似于线段树的东西

最新文章

热门文章