Codeforces Round #735 (Div. 2) C. Mikasa

Codeforces Round #735 (Div. 2) C. Mikasa

ps:代码最后调出来来不及交了,没有AC,纯属口嗨 qwq

本质是找个最小的k使得n^k>m

\(n > m\) 则答案为0

下面描述的变化量即为要找的k。

1、找到n最高的值为1且不与m相同的一个二进制位,假设为第x位,代表的值为2^(x-1)

2、若能找到这样的二进制位,因为要使n^k>m,那么n高于该位的值为0的位都应该向m补齐(补齐,即若m此位为1,n此位为0,则应该补为1),低于该位的不做处理(保证n的变化量,即k尽量小)。

3、若找不到这样的二进制位,那么可以以最低的代价造一个这样的二进制位(即找到m的二进制值为0的最低位,把n对应位置变成1),然后再按照上面处理。

明天再交代码试试。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

int t;
LL n, m;

//找二进制为0的最低位
LL ct(LL x) {
    LL res = 1;
    while(true) {
        if ((x & res) == 0) return res;
        res <<= 1;
    }
}

int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%lld%lld", &n, &m);
        if (n > m) {
            printf("0\n");
            continue;
        }

        //找x代表的值
        LL tmp = 1, last = -1;
        while(tmp <= n) {
            if ((n & tmp) != 0 && (m & tmp) == 0) {
                last = tmp;
            }
            tmp <<= 1;
        }

        LL p = ct(m);
        if (last == -1) {
            printf("%lld\n", m+p-n-(m%p)+(n%p));
        } else {
            printf("%lld\n", m-(m%last)-(n-(n%last)-last));
        }
    }
}

上一篇:2021零售商业智能(BI)的 8大好处


下一篇:MATLAB-输出在目标温度、目标压力下平衡时的气相摩尔分量及气液组成