CodeForces - 1247C p-binary 【思维】

野性酷女 2023-06-15 11:03 29阅读 0赞

题目链接：[https://codeforces.com/problemset/problem/1247/C][https_codeforces.com_problemset_problem_1247_C]

题意：给你两个数n和p， 让你将n分解成最少的二进制位，但是二进制位变成了2^x  + p, 例如当n = 24，p = 1时，

![20191121232233586.png][]

思路：不难想到n在二进制分解后绝对不会超过40位，所以对于这么小的范围我们就暴力枚举多少位能够组成n就行了。

但是有可以重复用某一位的情况，所以还需要记录一下可以拆分多少位，如果够的话就说明可以。

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    #define ls rt << 1
    #define rs rt << 1|1
    #define mid ((l + r) >> 1)
    #define lson l, mid, ls
    #define rson mid + 1, r, rs
    const int maxn = 2e5 + 10;
    const int mod = 1e9 + 7;
    
    int main()
    {
        ll n, p;
        cin >> n >> p;
        int ans = -1;
        for(int i = 1; i <= 40; ++i)
        {
            ll tmp = n - 1ll * i * p;
            int cnt = 0, tot = 0;
            if(tmp > 0)
            {
                for(int j = 40; j >= 0; --j)
                {
                    if(tmp & (1ll << j))
                    {
                        ++cnt;
                        if(j > 0)
                            tot += j - 1;
                    }
                }
                if(cnt == i)
                {
                    ans = cnt;
                    break;
                }
                else if(cnt < i)
                {
                    if(cnt + tot >= i)
                    {
                        ans = i;
                        break;
                    }
                }
            }
        }
        cout << ans << endl;
        return 0;
    }

[https_codeforces.com_problemset_problem_1247_C]: https://codeforces.com/problemset/problem/1247/C
[20191121232233586.png]: https://img-blog.csdnimg.cn/20191121232233586.png