【HDU】5747 - Aaronson（位运算 & 贪心）

FishWang

发布于 2025-08-27 09:53:49

12700

代码可运行

运行总次数：0

代码可运行

点击打开题目

Aaronson

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 723 Accepted Submission(s): 400

Problem Description

Recently, Peter saw the equation . He wants to find a solution in such a manner that is minimum and every ( ) is non-negative.

Input

There are multiple test cases. The first line of input contains an integer , indicating the number of test cases. For each test case: The first contains two integers and .

Output

For each test case, output the minimum value of .

Sample Input

Sample Output

Source

BestCoder Round #84

没有总结出来公式=。=用位运算先凑最大的数，然后一个个往下算出来的。

代码如下：

#include <cstdio>
int main()
{
    int n,m;
    int u;
    int k;        //n的二进制位数 
    scanf ("%d",&u);
    while (u--)
    {
        scanf ("%d %d",&n,&m);
        int t = n;
        k = 0;
        int ans = 0;
        while (t)
        {
            t >>= 1;
            k++;
        }
        if (k - 1 <= m)
        {
            while (n)
            {
                n = n & (n-1);
                ans++;
            }
        }
        else
        {
            while (m--)
            {
                if (n & 1)
                    ans++;
                n >>= 1;
            }
            for (int i = 0 ; n ; i++)
            {
                if (n & 1)    
                    ans += (1 << i);
                n >>= 1;
            }
        }
        printf ("%d\n",ans);
    }
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-08-26，如有侵权请联系 cloudcommunity@tencent.com 删除

minimum