lightoj1042

maksyuki 发表于 oj 分类，标签: 基础算法-简单数学

27 8月 2015

1042 - Secret Origins

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.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.

The Onoroy value of an integer N is the number of ones in its binary representation. For example, the number 13 (1101₂) 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 ≤ 10⁹).

Output

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

Sample Input	Output for Sample Input
5231423239178	Case 1: 27Case 2: 14241Case 3: 395Case 4: 11Case 5: 16

题目类型：位运算

算法分析：如果直接枚举比n大的数并判断二进制中1的个数是否相同会TLE，此时使用的方法是将n的二进制表示存储到数组中，然后依次求长度为i的二进制位中的下一个排列，如果长度为i的二进制位存在下一个排列，则直接将该数转化为十进制输出即可。如果没有下一个合理的排列，则尝试下一个长度的二进制位的排列。由于尝试的二进制的排列的长度不超过2次，所以时间复杂度几乎为O(n)的，其中n为原十进制数的二进制表示的长度，而由已知可得n不超过32，所以不会TLE

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

const int INF = 0x7FFFFFFF;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int MOD = 10000007;


const int maxn = 1000 + 66;

int ans[maxn], temp[maxn];

int Get (int val)
{
    int cnt = 0;
    do
    {
        ans[cnt++] = val % 2;
        val /= 2;
    } while (val);

    int i;
    for (i = 0; i < cnt / 2; i++)
    {
        int temp = ans[i];
        ans[i] = ans[cnt-1-i];
        ans[cnt-1-i] = temp;
    }

return cnt;
}

int Trans (int val)
{
    int i, sum = 0, wei = 1;
    for (i = val - 1; i >= 0; i--)
    {
        sum += wei * temp[i];
        wei *= 2;
    }

return sum;
}


int main()
{
//    ifstream cin ("aaa.txt");

    int t, flag = 1;
    cin >> t;

    while (t--)
    {
        memset (ans, 0, sizeof (ans));
        memset (temp, 0, sizeof (temp));
        int n;
        cin >> n;

        int val_a, val_b;
        val_a = Get (n);

        int i;
        for (i = val_a; ; i++)
        {
            int j;
            for (j = 0; j < val_a; j++)
                temp[j] = ans[j];

            bool is_find = false;
            while (next_permutation (temp + 1, temp + i))
            {
                is_find = true;
                break;
            }

            if (is_find || i > val_a)
                break;
        }


        cout << "Case " << flag++ << ": " << Trans (i) << endl;
    }

return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

const int INF = 0x7FFFFFFF;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int MOD = 10000007;

const int maxn = 1000 + 66;

int ans[maxn], temp[maxn];

int Get (int val)

{

int cnt = 0;

{

ans[cnt++] = val % 2;

val /= 2;

} while (val);

int i;

for (i = 0; i < cnt / 2; i++)

{

int temp = ans[i];

ans[i] = ans[cnt-1-i];

ans[cnt-1-i] = temp;

}

return cnt;

}

int Trans (int val)

{

int i, sum = 0, wei = 1;

for (i = val - 1; i >= 0; i--)

{

sum += wei * temp[i];

wei *= 2;

}

return sum;

}

int main()

{

// ifstream cin ("aaa.txt");

int t, flag = 1;

cin >> t;

while (t--)

{

memset (ans, 0, sizeof (ans));

memset (temp, 0, sizeof (temp));

int n;

cin >> n;

int val_a, val_b;

val_a = Get (n);

int i;

for (i = val_a; ; i++)

{

int j;

for (j = 0; j < val_a; j++)

temp[j] = ans[j];

bool is_find = false;

while (next_permutation (temp + 1, temp + i))

{

is_find = true;

break;

}

if (is_find || i > val_a)

break;

}

cout << "Case " << flag++ << ": " << Trans (i) << endl;

}

return 0;

}

lightoj1041

lightoj1043

一	二	三	四	五	六	日
« 6月
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

超客的水墨烟雨

lightoj1042

Input

Output

Sample Input

Output for Sample Input

分类目录

标签云

书签

近期评论