Codeforces Round 949题解（A、B、C）

A. Turtle and Piggy Are Playing a Game

首先\(p\)选\(2\)的话除得最慢，得的分多。考虑二进制表示，如果\(x = (1000000000)_{bin}\)，则每次除以\(2\)都是相当于右移一位，除完之后仍然是\(2\)的倍数，变成\(1\)的步数就是把最高位的\(1\)移动到\(0\)位的步数。

因为\(2l \le r\)，所以\(l \le \lfloor \frac{r}{2} \rfloor\)，若\(r = (1011101)_{bin}\)，则\(r >> 1 = (101110)_{bin}\)，可以发现\((1000000)_{bin}\)一定是在\([l, r]\)区间内部，因此我们可以直接选择\(x = 1 << (lg(r))\)。

int l, r;
 
void solve() {
    cin >> l >> r;
    cout << lg(r) << '\n';
}

B. Turtle and an Infinite Sequence

写下几组数据发现第\(m\)次改变后\(a_n\)的值变为\([n - m, n + m]\)这个区间内所有\(a_i\)的按位或的值。

令\(l = n - m\)，\(r = n + m\)。

l: 01011 0 11011
r: 01011 1 00110

设从左到右第一个不相等的位为\(bit\)，则\(ans\)的\(bit\)位左边的值就是\(l\)或\(r\)的这个位的值。对\(bit\)位及其右边的位，发现01011 0 11111在\([l, r]\)内，因此后面的位每一位或出来都是\(1\)，则加上\((1 << (bit + 1)) - 1\)即可。

int n, m;
 
void solve() {
    cin >> n >> m;
    int l = max(0, n - m);
    int r = n + m;
    int ans = 0;
    for (int i = 31; i >= 0; i --) {
        if ((l >> i & 1) != (r >> i & 1)) {
            ans += (1 << (i + 1)) - 1;
            break;
        }
        else {
            ans |= (l >> i & 1) << i;
        }
    }
    cout << ans << '\n';
}

Turtle and an Incomplete Sequence

int n;
int a[M];
int b[M];

int get_times_l(int x, int y) {
    int l = lg(x), r = lg(y);
    int i, j;
    for (i = l, j = r; i >= 0 && j >= 0; i --, j --) {
        if ((x >> i & 1) != (y >> j & 1)) {
            return i + 1;
        }
    }
    return i + 1;
}

int get_times_r(int x, int y) {
    int l = lg(x), r = lg(y);
    int i, j;
    for (i = l, j = r; i >= 0 && j >= 0; i --, j --) {
        if ((x >> i & 1) != (y >> j & 1)) {
            return j + 1;
        }
    }
    return j + 1;
}

void solve() {
    cin >> n;
    for (int i = 1; i <= n; i ++) {
        b[i] = 1;
    }
    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i ++) {
        if (a[i] != -1) {
            b[i] = a[i];
            int j;
            for (j = i + 1; j <= n; j ++) {
                if (a[j] != -1) {
                    break;
                }
            }
            if (j > n) {
                break;
            }
            int l = get_times_l(a[i], a[j]);
            int r = get_times_r(a[i], a[j]);
//            cout << l << ' ' << r << '\n';
//            cout << i << ' ' << j << '\n';
            if (j - i >= l + r && (j - i - l - r) % 2 == 0) {
                for (int k = i + 1; k <= i + l; k ++) {
                    b[k] = b[k - 1] / 2;
                }
                int rr = r;
                for (int k = i + l + 1; k <= i + l + r; k ++) {
                    b[k] = b[k - 1] * 2 + ((a[j] >> (rr-- - 1)) & 1);
                }
                int cnt = 0;
                for (int k = i + l + r + 1; k < j; k ++) {
                    if (cnt++ & 1) b[k] = b[k - 1] / 2;
                    else b[k] = b[k - 1] * 2;
                }
            }
            else {
                cout << "-1\n";
                return;
            }
            i = j - 1;
        }
    }
    int pos_l = -1, pos_r = -1;
    for (int i = 1; i <= n; i ++) {
        if (a[i] != -1) {
            pos_l = i;
            break;
        }
    }
    for (int i = n; i >= 1; i --) {
        if (a[i] != -1) {
            pos_r = i;
            break;
        }
    }
    int cnt = 0;
    if (pos_l != -1) {
        for (int i = pos_l - 1; i >= 1; i --) {
            if (cnt++ & 1) b[i] = b[i + 1] / 2;
            else b[i] = b[i + 1] * 2;
        }
    }
    cnt = 0;
    if (pos_r != -1) {
        for (int i = pos_r + 1; i <= n; i ++) {
            if (cnt++ & 1) b[i] = b[i - 1] / 2;
            else b[i] = b[i - 1] * 2;
        }
    }
    if (pos_l == -1 && pos_r == -1) {
        b[1] = 1;
        cnt = 0;
        for (int i = 2; i <= n; i ++) {
            if (cnt++ & 1) b[i] = b[i - 1] / 2;
            else b[i] = b[i - 1] * 2;
        }
    }
    for (int i = 1; i <= n; i ++) {
        cout << b[i] << ' ';
    }
    cout << '\n';
}