3

我正在尝试解决这个问题： http ://uva.onlinejudge.org/external/102/10232.html

  1. 基本上，一个数字x大于y，如果1二进制表示的 's的数量x大于y;

  2. 如果它们确实有相同数量的1'，那么我们以自然方式进行比较；

所以，现在我们有一个由整数组成的位序列1 .. 2147483647。给定某个整数的索引，我们如何才能有效地获得该整数？

注意：序列中的前几个整数应该是：

0, 1, 2, 4, 8, 16, 32, .. 1073741824, 3, 5, 6, 9, ..
-  ---------------------------------  --------------
0           one 1's                       two 1's

笔记：

  1. 创建一个查找表是可行的，但它太慢了，而且内存太多！
  2. 把所有的整数分到不同个数1的包里也很慢：同一个包里怎么数，是不是要一个一个地数？
  3. 我不是学生。我是一个工作的专业人士。解决 ACM 问题只是我的爱好。使用蛮力通常不是我的口味，如果我相信有更有效的算法来做到这一点。
4

2 回答 2

4

我认为您可以将其分解为两个单独的问题：

  1. 找出有多少个恰好设置了 k 位的数字，以及
  2. 找到恰好设置了 k 位的第 n 个最小数字。

假设您可以解决问题 (1) 和 (2)。那么这里有一个整体问题的解决方案，用 Awful Pseudocode 编写：

function nthNumber(n):
    let numBitsNeeded = 0;
    while true:
       let x = number of numbers with exactly numBitsNeeded bits.
       if x >= n, break

       n -= x

    return the nth-smallest value with exactly numBitsNeeded bits

这个想法是弄清楚数字 n 中有多少位，并从那里确定您需要多少位的数字。

让我们分别解决每个问题。

第 1 部分：计算恰好设置了 k 位的值的数量

幸运的是，这部分有一个很好的封闭式解决方案。如果您有一个 32 位数字，并且想知道有多少个数字恰好设置了 k 位，则可以计算值 32 选择 k，因为您要选择数字中的哪些位置将设置位。这可以计算为

32！/ (k! (32 - k)!)

如果愿意，您可以预先计算并将其放入表中，这意味着您可以在 O(1) 时间内计算此值。

第 2 部分：确定恰好设置了 k 位的第 n 个最小数。

由于所有这些数字都具有相同的位数并且它们像往常一样进行比较，因此您可以将这部分问题视为找到 k 位的第 n 个字典顺序组合。您可以这样做的一种方法如下：假设您知道在位置 k、k + 1、k + 2、k + 3 等处有多少个最高位的数字。然后您可以对这些数字进行二进制搜索以确定数字中最高的最佳位置。完成此操作后，您可以递归地应用相同的过程，但使用 k - 1 位来恢复数字的剩余位。

所以现在我们需要弄清楚如何计算在某个位置 p 选择最高 1 位的 k 位的方法的数量。幸运的是，这也不是那么难。如果您有 k 位并且最高位在位置 p，那么您需要将剩余的 k - 1 位分配到小于 p 的位置。执行此操作的方法数由 (p - 1) 选择 (k - 1) 给出，即

（p - 1）！/ (k - 1)!((p - 1) - (k - 1))!

将此与上述逻辑相结合，您可以确定数字的所有位应该去哪里，而不必一直计数。

希望这可以帮助！

于 2013-10-16T00:47:22.090 回答
1

According to @templatetypedef 's core algorithm, I finally got it Accepted:

#       Problem     Verdict     Language    Run Time    Submission Date
12534054    10232   Bit-wise Sequence   Accepted    C++     0.018   2013-10-21 00:39:12

The credit should still go to @templatetypedef, but I'm also posting the main code for others' reference.

The code is actually short, because most is my comments :-)

The main code (I spent a lot of time solving the "Offset 1" issue):

#include <cstdio>
#include <bitset>
#include <algorithm>
#define N 32
using namespace std;

unsigned C[N][N]; // C[k][n] means choose k objects from n objects
unsigned S[N];
void CreateLookupTable()
{
    // Create the C(k, n)
    for (int n = 0; n < N; ++n)
        C[0][n] = 1;
    for (int n = 1; n < N; ++n)
    {
        for (int k = 1; k < n; ++k)
            C[k][n] = C[k][n-1] + C[k-1][n-1];
        C[n][n] = 1;
    }

    // Construct an accumulated sequence from C[i, 31], where i is [0..31]
    int n = N-1;
    S[0] = C[0][n];
    for (int i = 1; i < N; ++i)
        S[i] = S[i-1]+C[i][n];
}

// n: the position in the current bucket
// b: how many 1's in the target number
// h: the index of the possible highest 1
inline void FillBitset(int n, int b, int h, bitset<N>& bs)
{
    if (b == 0)
        return;

    // Search for which small bucket the number is. Similar as before,
    // If b = 4, h_ = 3, there will be C[3][3] numbers
    // If b = 4, h_ = 4, there will be C[3][4] numbers
    // If b = 4, h_ = 5, there will be C[3][5] numbers
    // ...
    // If b = 4, h_ = h, there will be C[3][h] numbers
    //
    // Also, it's very easy to prove that:
    // C[3][3]                                    = C[4][4]
    // C[3][3] + C[3][4]                          = C[4][5]
    // C[3][3] + C[3][4] + C[3][5]                = C[4][6]
    // ...
    // C[3][3] + C[3][4] + C[3][5] + .. + C[3][h] = C[4][h+1]
    //
    // Now let's determine which C[b][i], where i is [b..(h+1)]
    unsigned* lb = lower_bound(&C[b][b], &C[b][h+1]+1, n);
    int c = lb-(&C[b][b])+b;

    // Don't forget to decrease c to get the index of the highest bit 1
    --c;

    // Fill the actual highest bit
    bs.set(c);

    // When c < b, lb must point to C[b][b] == 1, which means all lower bits
    // are also 1's, and we should stop here
    if (c < b)
    {
        for (int i = 0; i < c; ++i)
            bs.set(i);
        return;
    }

    // Deduct the number of numbers in the lower buckets, and search for
    // (b-1) 1's in a smaller bucket. Apparently, the possible highest 1
    // should be at index c-1, since the current bucket's highet 1 is at
    // index c
    FillBitset(n-C[b][c], b-1, c-1, bs);
}

inline unsigned GetNumber(int n)
{
    if (n == 0)
        return 0;

    // From index to position
    ++n;

    // Get which bucket Number[n] is
    unsigned* lb = lower_bound(S, S+N, n);
    int b = lb-S; // There are b 1's in the number, and b is always > 0
                  // because n == 0 is excluded above

    // So let's go to the core algorithm: get the position in the bucket
    // For each bucet, we need to divide it into small bags/buckets.
    // 
    // If b = 4, there will be [3..30] = 28 bags to represent how many numbers
    // whose highest one is at index 3, 4, 5, .. 30
    // 
    // If b = 4, and the highest 1 is at index 3, there will be C[3][3] numbers
    // If b = 4, and the highest 1 is at index 4, there will be C[3][4] numbers
    // If b = 4, and the highest 1 is at index 5, there will be C[3][5] numbers
    // ...
    // If b = 4, and the highest 1 is at index 30, there will be C[3][30] numbers
    //
    // Now our task is to find which small bucket the number is
    bitset<N> bs;
    FillBitset(n-S[b-1], b, N-2, bs);

    return (unsigned)bs.to_ulong();
}

Test Input:

0
1
2
31
32
0
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
496
497
498
2147483647
1234567890
987654321
6123512
852412
123125
67658153
214155
5623674

Test Output:

0
1
2
1073741824
3
0
1
2
4
8
16
32
64
128
256
512
1024
2048
4096
8192
16384
32768
65536
131072
262144
524288
1048576
2097152
4194304
8388608
16777216
33554432
67108864
134217728
268435456
536870912
1073741824
3
5
1610612736
7
11
2147483647
1195924317
1467508257
147227152
1099186184
135856144
1247429124
57624
100730919
于 2013-10-21T00:41:14.337 回答