Competitive Programming Guide Book 中解释 "counting the number of subgrids" 解决方案

Question

我在竞争性程序员手册中看到了一个问题的解释，但并不真正理解它是如何包含问题的所有解决方案的，我想知道是否有人可以为我解释一下。如果我遗漏了有关问题的某些信息，我不确定我是否只是没有正确理解解决方案。问题和解决方案的图片如下：

根据我的理解，问题只是要求子网格（构成 a x b 或 a x a 框的四个角），其中每个角都是黑色的。他们的解决方案（据我所知）是计算每列中黑盒对的数量，然后使用公式 count(count-1)/2 计算总数。如果我理解正确，我的问题是这如何涵盖所有情况？我脑海中的具体例子是：

X O O O O O
O X O O O O
O O X O O O
X O O O O O 
O X O O O O
O O X O O O

和

X X X O O O
O O O O O O
O O O O O O
X X X O O O 
O O O O O O
O O O O O O

使用提供的解决方案，这两个框不会给出相同的答案吗？你会得到 count = 3 对于两个输入，每个输入的总数输出 3，尽管它们有不同的解决方案。我只是觉得在解决方案时我遗漏了一些东西。

感谢您的帮助。

Answer 1

作为伪代码给出的算法实际上只是内部循环。如前文所述，外循环是对所有行对的循环。

int count_subgrids(const int** color, int n)
{
    int subgrids = 0;
    for(int a=0; a<n; ++a)
        for(int b=a+1; b<n; ++b) {    // loop over pairs (a,b) of rows 
            int count=0;
            for(int i=0; i<n; ++i) {  // loop over all columns
                if(color[a][i]==1 && color[b][i]==1)
                    ++count;
            }
            subgrids += ((count-1)*count)/2;
        }
    return subgrids;
}

在您的第一个示例中，count=0 表示任何一对行，因此 subgrid 也仍然是 0。在您的第二个示例中，存在三对行，即 (a,b)=(0,1)、(0,2) 和 (1,2)，其中 count=2，因此 subgrid=3最后。

Competitive Programming Guide Book 中解释 "counting the number of subgrids" 解决方案

Explaining "counting the number of subgrids" solution in the Competitive Programming Guide Book

c++

algorithm

subgrid