Python程序查找满足给定条件的彩色顶点子集的数量

假设我们有一个数组colors，表示一个正n边形的颜色。这里这个n边形的每个顶点都被随机地用给定数组中存在的n种不同颜色中的一种颜色着色。我们必须找到多边形顶点的特殊子集的数量，使得这些子集满足以下条件：

  • 子集的大小必须至少为二。
  • 如果我们从多边形中移除存在于子集中的顶点（这些顶点的相邻边也将被移除），那么剩下的顶点和边形成一些连续的路径。
  • 这些路径中都不应该包含两个相同颜色的顶点。

我们必须计算存在此类子集的数量。如果答案太大，则返回结果模10^9 + 7。

因此，如果输入类似于colors = [1,2,3,4]，则输出将为11。

为了解决这个问题，我们将遵循以下步骤：

  • count := 一个空映射，其中所有值都将是一个空列表。
  • n := colors的大小
  • 对于范围从0到colors的大小-1的i，执行以下操作：
    • 将i插入到count[colors[i]]的末尾
  • answer := 0
  • 对于范围从2到n的i，执行以下操作：
    • answer := answer + nCr(n, i)
  • 对于count的所有键的列表中的每个i，执行以下操作：
    • l0 := count[i]
    • n0 := l0的大小
    • 如果n0 > 1，则执行以下操作：
      • 对于范围从0到n0-2的i，执行以下操作：
        • 对于范围从i+1到n0 - 1的j，执行以下操作：
          • d1 := l0[j] -l0[i]
          • d2 := l0[i] -l0[j] + n
          • 如果d1 <= n-3 或 d2<= n-3，则执行以下操作：
            • answer := answer - 1
  • 返回answer

示例

让我们看看以下实现以更好地理解：

Open Compiler
from collections import defaultdict
from math import factorial

def nCr(n, i):
   if n==1:
      return 1
   return factorial(n)//factorial(i)//factorial(n-i)

def solve(colors):
   count = defaultdict(list)
   n = len(colors)

   for i in range(len(colors)):
      count[colors[i]].append(i)
   answer = 0

   for i in range(2, n+1):
      answer += nCr(n, i)

   for i in count.keys():
      l0 = count[i]
      n0 = len(l0)

      if n0 > 1:
         for i in range(n0-1):
            for j in range(i+1, n0):
               d1 = l0[j] -l0[i]
               d2 = l0[i] -l0[j] + n
               if d1 <= n-3 or d2<= n-3:
                  answer -=1

   return answer

colors = [1,2,3,4]
print(solve(colors))

输入

[1,2,3,4]

Learn Python in-depth with real-world projects through our Python certification course. Enroll and become a certified expert to boost your career.

输出

11

更新于: 2021年10月25日

88 次浏览

开启您的 职业生涯

通过完成课程获得认证

开始学习
广告