首页 > ACM题库 > HDU-杭电 > hdu 2656 Counting Game[解题报告]C++
2014
02-12

hdu 2656 Counting Game[解题报告]C++

Counting Game

问题描述 :

Let’s define the number of ’1′ of X in base 2 is V(X).Now give you an X and a k, please give me the kth number Y strictly greater than X and V(X) = V(Y).

输入:

Input includes several cases. Each case contains one line with two integers X, k. Input ends with a case X = 0 and k = 0. X is a 32-bit integer, 0 < K <= 50000.

输出:

Input includes several cases. Each case contains one line with two integers X, k. Input ends with a case X = 0 and k = 0. X is a 32-bit integer, 0 < K <= 50000.

样例输入:

5 1
481 2
0 0

样例输出:

6
484

HDU_2656

    由于K比较小,Y也在int的范围内,所以可以不断生成比X大一点的排列,直到生成到第K个为止。

#include<stdio.h>
#include<string.h>
int X, K;
struct Integer
{
    int a[32];
    void init(int x)
    {
        int i;
        for(i = 0; i < 32; i ++)
        {
            a[i] = x % 2;
            x /= 2;
        }
    }
    void getnext()
    {
        int i, j, cnt = 0;
        for(i = 0;; i ++)
            if(a[i] == 1)
            {
                if(a[i + 1] == 0)
                {
                    a[i + 1] = 1;
                    for(j = 0; j <= i; j ++)
                    {
                        if(cnt)
                            -- cnt, a[j] = 1;
                        else
                            a[j] = 0;
                    }
                    break;
                }
                ++ cnt;
            }
    }
}integer;
void solve()
{
    int i;
    long long int ans = 0;
    integer.init(X);
    for(i = 0; i < K; i ++)
        integer.getnext();
    for(i = 31; i >= 0; i --)
        ans = ans * 2 + integer.a[i];
    printf("%I64d\n", ans);
}
int main()
{
    for(;;)
    {
        scanf("%d%d", &X, &K);
        if(!X && !K)
            break;
        solve();
    }
    return 0;
}

解题转自:http://www.cnblogs.com/staginner/archive/2012/04/09/2439792.html


  1. 我没看懂题目
    2
    5 6 -1 5 4 -7
    7 0 6 -1 1 -6 7 -5
    我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
    第二个是7 0 6 -1 1 -6 7输出是14 7 7
    不知道题目例子是怎么得出来的