2

我有一个表，它由以这种方式排列的非负整数组成：表中的每个元素都是不出现在其左侧或上方的最小值。这是一个 6x6 网格的示例：

0 1 2 3 4 5
1 0 3 2 5 4
2 3 0 1 6 7
3 2 1 0 7 6
4 5 6 7 0 1
5 4 7 6 1 0

如您所见，第一行和第一列以 0 1 2 3 4 5 ... 在坐标 (x,x) 中始终为 0。在之后的每个图块上，您必须将不存在的最小正数放置在同一行或列上。就像在数独游戏中一样：在同一行和同一列上不能有两次数字。

现在我必须打印给定坐标（y，x）中的数字。例如 [2, 5] = 5

我想出了一个可行的解决方案，但它需要太多的内存和时间，我只知道还有另一种方法可以做到这一点。我的时间限制是 1 秒，我必须找到的数字的坐标可以达到 (1000000, 1000000)。

这是我目前的代码：

#include <iostream>
#include <vector>

int main()
{
    int y, x, grid_size;
    std::vector< std::vector<int> > grid;

    std::cin >> y >> x; // input the coordinates we're looking for

    grid.resize(y, std::vector<int>(x, 0)); // resize the vector and initialize every tile to 0

    for(int i = 0; i < y; i++)
        for(int j = 0; j < x; j++)
        {
            int num = 1;

            if(i != j) { // to keep the zero-diagonal

                for(int h = 0; h < y; h++)
                    for(int k = 0; k < x; k++) { // scan the current row and column
                        if(grid[h][j] == num || grid[i][k] == num) { // if we encounter the current num
                            num++;                                   // on the same row or column, increment num
                            h = -1; // scan the same row and column again
                            break;
                        }
                    }

                grid[i][j] = num; // assign the smallest number possible to the current tile

            }
        }

    /*for(int i = 0; i < y; i++) {            // print the grid
        for(int j = 0; j < x; j++)            // for debugging
            std::cout << grid[i][j] << " ";   // reasons

        std::cout << std::endl;
    }*/

    std::cout << grid[y-1][x-1] << std::endl; // print the tile number at the requested coordinates
    //system("pause");
    return 0;
}

所以我该怎么做？这比我想象的要容易吗？

4

1 回答 1

5

总结您的问题：您有一个表格，其中每个元素都是不出现在其左侧或上方的最小非负整数。您需要在 (x,y) 位置找到元素。

结果非常简单：如果x和y是基于 0 的，则 (x,y) 处的元素是x XOR y。这与您发布的表格相匹配。我已经对 200x200 的表进行了实验验证。

证据：

很容易看出，相同的数字不会在同一行或同一列出现两次，因为如果 x 1 ^y = x 2 ^y 则必然 x 1 =x 2。

看到那x^y是最小的：让a是一个小于 的数字x^y。让i是最左边的位的索引（从右边）a与 不同x^y。的ith 位a必须为 0， 的ith 位x^y必须为 1。

因此，要么x或y必须在i第 th 位为 0。假设 WLOG 为x0。将x和表示y为：

x = A0B
y = C1D

其中 A,B,C,D 是位序列，B 和 D 是i位长。由于 的最左边的位与a中的相同x^y：

a^x = C0E

其中 E 是i位序列。所以我们可以看到a^x < y。(a^x)出现在同一列的第 th 行的值为： (a^x)^x = a。因此，该值a必须已经出现在同一行（或列，如果它在第 th 位y中有 0 ）。i对于小于 的任何值都是如此x^y，因此x^y确实是最小可能值。

于 2013-01-07T14:31:33.307 回答