9

假设我们将考虑具有长度2n并且n可能约为的二进制数1000。我们正在寻找具有以下属性的kth数字（k 受 限制）：10^9

  • 金额1's等于金额0's可以描述如下的数量：#(1) = #(0)
  • 这个数字的每个前缀必须至少0's包含1's. 否定句子后可能更容易理解，即：没有前缀可以包含1's超过0's。

基本上就是这样。因此，为了清楚起见，让我们举个例子： n=2，k=2 我们必须取长度的二进制数2n：

0000
0001
0010
0011
0100
0101
0110
0111
1000
and so on...

现在我们必须找到2nd满足这两个要求的数字。所以我们看到0011的是第一个，0101也是第二个。如果我们更改k=3，则答案不存在，因为存在具有相同数量的相反位的数字，但是对于0110，存在前缀011，因此数字不满足第二个约束，并且所有具有1最高有效位的数字都相同。

那么到目前为止我做了什么来找到算法？

好吧，我的第一个想法是生成所有可能的位设置，并检查它是否具有这两个属性，但生成它们都将采用O(2^(2n))这不是n=1000.

此外，我意识到没有必要检查所有小于0011for n=2、000111forn=3等的数字……坦率地说，那些最高有效位的一半仍然“未触及”的数字，因为这些数字不可能满足#(1) = #(0)条件。使用它我可以减少n一半，但它没有多大帮助。而不是 2 * forever 我有永远运行的算法。它仍然O(2^n)是复杂的，这太大了。

对算法有什么想法吗？

结论

这篇文章是我在阅读 Andy Jones 帖子后的想法而创建的。

首先，我不会发布我使用过的代码，因为它是来自 Andy 的帖子Kasa 2009的以下文档中的第 6 点。您所要做的就是nr按照我所描述的那样考虑k。Unranking Dyck words 算法，将帮助我们更快地找到答案。但是，它有一个瓶颈。

while (k >= C(n-i,j))

考虑到这一点n <= 1000，加泰罗尼亚语数可能相当大，甚至C(999,999). 我们可以使用一些大数算术，但另一方面我想出了一个小技巧来超越它并使用标准整数。

我们不想知道加泰罗尼亚数实际上有多大，只要它大于k. n x n所以现在我们将在表格中创建缓存部分和的加泰罗尼亚数字。

...                                     ...
5 |                              42     ...
4 |                        14    42     ...
3 |                   5    14    28     ...
2 |             2     5     9    14     ...
1 |       1     2     3     4     5     ...
0 | 1     1     1     1     1     1     ...
   ----------------------------------   ...
    0     1     2     3     4     5     ...

生成它非常简单：

C(x,0) = 1
C(x,y) = C(x,y-1) + C(x-1,y)  where y > 0 && y < x
C(x,y) = C(x,y-1) where x == y

所以我们只能看到这个：

C(x,y) = C(x,y-1) + C(x-1,y)  where y > 0 && y < x

可能导致溢出。

让我们停在这一点上并提供定义。

k-flow- 这不是整数的真正溢出，而是值C(x,y)大于的信息k。

我的想法是在每次运行上述公式后检查是否C(x,y)大于k或任何总和分量-1。如果是我们把-1它作为一个标记，那就k-flow已经发生了。我想很明显，如果k-flow数字与任何正数相加，它仍然是k-flowed特别是 2 个k-flowed数字的总和k-flowed。

最后我们要证明的是，不可能产生真正的溢出。真正的溢出只有在我们总结a + b它们中的哪一个时才会发生，k-flowed但它们总和产生了真正的溢出。

当然这是不可能的，因为最大值可以描述为a + b <= 2 * k <= 2*10^9 <= 2,147,483,647这个不等式中的最后一个值是带符号的 int 值。我还假设 int 有 32 位，就像我的情况一样。

4

2 回答 2

4

您描述的数字对应于Dyck 单词。Kasa 2009的Pt 2提供了一个简单的算法，用于按字典顺序枚举它们。如果您想进一步阅读，它的参考资料应该会有所帮助。

顺便说一句（请注意，我在写这篇文章时半睡半醒，所以它可能是错误的），维基百科文章指出，长度的 Dyck 单词的数量2n是n加泰罗尼亚语数，C(n). 您可能希望找到比您要查找的更大的最小n的，然后从 . 开始枚举 Dyck 单词。C(n)kX^n Y^n

于 2013-12-16T03:09:35.220 回答
0

很抱歉上次误会了这个问题，所以我编辑它，现在我可以承诺更正，你可以先测试代码，复杂度是O(n^2)，详细答案如下

首先，我们可以将问题等同于下一个

我们正在寻找具有以下属性的kth largest数字（k 受 限制）：10^9

  • 数量1's等于0's可以描述如下的数量：#(1) = #(0)
  • 这个数字的每个前缀都必须至少包含 [[ 1'sas 0's]]，这意味着：没有前缀会包含比 [[ 0's] 1's] 更多的前缀。

举个例子来说明一下：让n=3和k=4，满足的数是5，下图说明了我们在上一题和新题中应该确定的内容：

|                       000111  ------>    111000                          ^
|                       001011  ------>    110100                          |
|                       001101  ------>    110010                          |
|  previous 4th number  010011  ------>    101100  new 4th largest number  |
v                       010101  ------>    101010                          |

所以在我们解决了新问题之后，我们只需要按位不。

现在主要的问题是如何解决新的问题。首先，设 A 为数组，所以A[m]{1<=m<=2n}只能是 1 或 0，设DP[v][q]是满足条件 2 和条件 #(1)=q in的数字的数量{A[2n-v+1]~A[2n]}，所以DP[2n][n]是满足的数字的数量。

A[1]只能是1或0，如果A[1]=1，数字的数量是DP[2n-1][n-1]，如果A[1]=0，数字的数量是DP[2n-1][n]，现在我们要找到kth largest数字，如果k<=DP[2n-1][n-1]，kth largest数字A[1]必须是1，那么我们可以A[2]用来判断DP[2n-2][n-2]；如果k>DP[2n-1][n-1], kth largestnumber'sA[1]必须是 0 并且, 那么我们可以用k=k-DP[2n-1][n-1]来判断。所以同样的理论，我们可以一一判断，直到没有数字可以比较。现在我们可以举个例子来理解A[2]DP[2n-2][n-1]A[j](n=3, k=4)

（我们使用动态规划来确定DP矩阵，DP方程为 DP[v][q]=DP[v-1][q-1]+DP[v-1][q]）

   Intention: we need the number in leftest row can be compared,
              so we add a row on DP's left row, but it's not include by DP matrix
              in the row, all the number is 1.
              the number include by bracket are initialized by ourselves
              the theory of initialize just follow the mean of DP matrix

   DP matrix = (1) (0) (0) (0)                4<=DP[5][2]=5  -->  A[1]=1
               (1) (1) (0) (0)                4>DP[4][1]=3  -->  A[2]=0, k=4-3=1
               (1) (2) (0) (0)                1<=DP[3][1]=3  -->  A[3]=1
               (1) (3)  2  (0)                1<=1  -->  a[4]=1
               (1) (4)  5  (0)                no number to compare, A[5]~A[6]=0
               (1) (5)  9   5                 so the number is 101100

如果还没有看清楚，可以用代码来理解

Intention：<code>DP[2n][n] 增加的非常快，所以代码只有在n<=19, 在问题n<1000，所以可以使用大数编程，代码可以通过位运算优化，所以代码是只是一个参考

/*-------------------------------------------------- 
    Environment: X86 Ubuntu GCC 
    Author: Cong Yu 
    Blog: aimager.com                              
    Mail: funcemail@gmail.com                      
    Build_Date: Mon Dec 16 21:52:49 CST 2013 
    Function: 
--------------------------------------------------*/

#include <stdio.h>

int DP[2000][1000];
// kth is the result
int kth[1000];

void Oper(int n, int k){
    int i,j,h;
    // temp is the compare number
    // jishu is the 
    int temp,jishu=0;

    // initialize
    for(i=1;i<=2*n;i++)
        DP[i-1][0]=i-1;
    for(j=2;j<=n;j++)
        for(i=1;i<=2*j-1;i++)
            DP[i-1][j-1]=0;
    for(i=1;i<=2*n;i++)
        kth[i-1]=0;

    // operate DP matrix with dynamic programming
    for(j=2;j<=n;j++)
        for(i=2*j;i<=2*n;i++)
            DP[i-1][j-1]=DP[i-2][j-2]+DP[i-2][j-1];

    // the main thought
    if(k>DP[2*n-1][n-1])
        printf("nothing\n");
    else{
        i=2*n;
        j=n;
        for(;j>=1;i--,jishu++){
            if(j==1)
                temp=1;
            else
                temp=DP[i-2][j-2];

            if(k<=temp){
                kth[jishu]=1;
                j--;
            }
            else{
                kth[jishu]=0;
                if(j==1)
                    k-=1;
                else
                    k-=DP[i-2][j-2];
            }
        }
        for(i=1;i<=2*n;i++){
            kth[i-1]=1-kth[i-1];
            printf("%d",kth[i-1]);
        }
        printf("\n");
    }
}

int main(){
    int n,k;
    scanf("%d",&n);
    scanf("%d",&k);
    Oper(n,k);
    return 0;
}
于 2013-12-16T03:28:23.470 回答