lightoj1042

发表于 | 分类于 ， ， | 阅读数 次

链接:lightoj1042

Description

  • This is the tale of Zephyr, the greatest time traveler the world will never know. Even those who are aware of
  • Zephyr’s existence know very little about her. For example, no one has any clue as to which time period she
  • is originally from.
  • But we do know the story of the first time she set out to chart her own path in the time stream. Zephyr had
  • just finished building her time machine which she named - “Dokhina Batash”. She was making the final
  • adjustments for her first trip when she noticed that a vital program was not working correctly. The program
  • was supposed to take a number N, and find what Zephyr called its Onoroy value.
  • The Onoroy value of an integer N is the number of ones in its binary representation. For example, the number
  • 13 (11012) has an Onoroy value of 3. Needless to say, this was an easy problem for the great mind of Zephyr.
  • She solved it quickly, and was on her way.
  • You are now given a similar task. Find the first number after N which has the same Onoroy value as N.

    Input

  • Input starts with an integer T (≤ 65), denoting the number of test cases.
  • Each case begins with an integer N (1 ≤ N ≤ 109).

    Output

  • For each case of input you have to print the case number and the desired result.

    Sample Input

    5
    23
    14232
    391
    7
    8

    Sample Output

    Case 1: 27
    Case 2: 14241
    Case 3: 395
    Case 4: 11
    Case 5: 16

    题解

  • 思路还行，代码实现有点困难，太弱了
  • 把n最右边的连续的1向右移动直到个数-1，把n最左边连续的1的末尾的相邻0改为1就是答案了
  • 以下是我的代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,x,y) for(register int i=x;i<=y;++i)
#define repd(i,x,y) for(register int i=x;i>=y;--i)
#define ll long long
#define lowbit(i) i&(-i)
using namespace std;
int pre,T,n,ct,now,bit[40],id;
int get(int x){
    int cnt=0;
    while(x){
        if(x&1)cnt++;
        x>>=1;
    }
    return cnt;
}

int getbit(int x){
    rep(i,0,30){
        if(x&1)bit[i]=1;
        else bit[i]=0;
        x>>=1;
    }
}

int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        ct=get(n);
        n+=lowbit(n);getbit(n);now=get(n);
        while(ct!=now){
            rep(i,0,30)if(!bit[i]){
                now++;bit[i]=1;
                n|=(1<<i);break;
            }
            
        }
        printf("Case %d: %d\n",++id,n);
    }
    return 0;
}

以下是大佬的代码，我只想说。。差距好大

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<cstdio>  
#include<cstring>  
#include<cmath>  
using namespace std;  
typedef long long ll;  
int main()  
{  
    ll t;  
    scanf("%lld",&t);  
    for(ll k=1;k<=t;++k)  
    {  
        ll n;  
        scanf("%lld",&n);  
        ll x=n&-n,y=n+x;  
        n=((n&~y)/x>>1)|y;  
        printf("Case %lld: %lld\n",k,n);  
    }  
    return 0;  
}