题解 | 小心火烛的歪

我觉得我这个办法有点笨, 但是数据范围不大的情况下可以用.

from itertools import combinations

def OR_process(a:str, b:str, m:int):
    ai = int(a, 2)
    bi = int(b,2)
    return bin(ai|bi)[2:].zfill(m)

def NOT_OR_process(a:str, b:str, m:int):
    ai = int(a, 2)
    bi = int(b, 2)
    return bin(ai^bi)[2:].zfill(m)

def package_process(A:list, B:list, n:str, m:str, process):
    if len(A) != len(B):
        raise ValueError
    if len(A) != n:
        raise ValueError
    
    res = []
    for i in range(n):
        res.append(process(A[i], B[i],m))
    return res

n, m , q  = map(int, input().split())
data = []

for _ in range(n*(q+1)):
    data.append(input())

garden = [x for x in data[:n]] #garden的状态
project_dict = {}

for i in range(1,q+1):  #把计划放入字典
    project = []
    for j in range(n):
        project.append(data[i*n + j])
    project_dict[i] = project

answer = ['1'*m for _ in range(n)]  #目标是在计划组合之后, 与graden初始状态取异或之后,满足所有位置都为"1"

if garden == answer:   #这里很坑, 有时候garden 一开始就是满1的.
    print(0)
else:
    found = False
    for i in range(1,q+1):   #不能从多往少选, 虽然计算量可能更小(因为组合越多满足的可能行越大), 但是题目要求数量最少的组合! 
        for c in combinations(range(1,q+1),i):
            if i>1:
                mix_project = project_dict[c[0]]
                for j in c[1:]:
                    mix_project = package_process(mix_project,project_dict[j],n,m, OR_process)
                result = package_process(mix_project,garden,n,m, NOT_OR_process)
            else: 
                project = project_dict[c[0]]
                result = package_process(project,garden,n,m, NOT_OR_process)

            if result == answer:
                found = True
                print(len(c))
                print(" ".join([str(x) for x in c]))
                break
        if found:
            break

    if not found:
        print(-1)