小心火烛的歪_

Python 3

牛客313号_光

n,m,q = list(map(int,input().split()))
A = [list(map(int,input())) for _ in range(n)]
all_ones = True
for row in A:
    if any(bit == 0 for bit in row):
        all_ones = False
        break
if all_ones:
    print(0)
    exit()
target_bits = []
for row in A:
    bits = 0
    for bit in row:
        bits = (bits<<1) | (1-bit)    #取反：0->1,1->0
    target_bits.append(bits)
valid_meth = []
meth_bits = []
for i in range(q):
    meth_q = [list(map(int,input())) for _ in range(n)]
    is_valid = True
    for row in range(n):
        for col in range(m):
            if A[row][col] == 1 and meth_q[row][col] == 1:
                is_valid = False
                break
        if not is_valid:
            break
    if is_valid:
        valid_meth.append(i)
        mbits = []
        for row in meth_q:
            bits = 0
            for bit in row:
                bits = (bits << 1) | bit  #保存满足要求的矩阵
            mbits.append(bits)
        meth_bits.append(mbits)   #多个矩阵列表
if not valid_meth:
    print(-1)
else:
    from itertools import combinations
    min_count = float('inf')
    best_comb = []
    best_combs = []
    for r in range(1,len(valid_meth) + 1):
        for comb in combinations(range(len(valid_meth)),r):
            union = [0] * n  #每个元素表示一行的覆盖情况
            for idx in comb:
                mbits = meth_bits[idx]  #获取子矩阵的二进制表示
                for j in range(n):
                    union[j] |= mbits[j]  
            cover_all = True
            for j in range(n):
                if (union[j] & target_bits[j]) != target_bits[j]:
                    cover_all = False
                    break
            if cover_all:
                if r < min_count:
                    min_count = r
                    best_combs = [[valid_meth[i] for i in comb]]
                elif r == min_count:
                    best_combs.append([valid_meth[i] for i in comb])  # 添加新组合   
                    break
        if min_count != float('inf'):
            break
    if min_count == float('inf'):
        print(-1)
    else:
        print(min_count)
        print(' '.join(map(lambda x: str(x + 1), sorted(best_combs[0]))))

发表于 2025-06-19 10:45:11 回复(0)

Python 3

牛客944845056号

我的两个失误：1、没意识到空地可重复放烟花。2、使用递归当遇到在非空地放烟花的情况别直接return，不然后面的方案就不能被考虑到了。

发表于 2025-05-05 20:15:30 回复(0)

Python 3

忧伤的双曲线

def tongji(x):# 输入一个01mask，输出其中'1'的数量，同时输出每个'1'的“索引+1”构成的列表

count = 0

list_idx = []

for i in range(len(x)):

if x[i]=='1':

count += 1

list_idx.append(str(i+1))

return count,list_idx

def is_success(land,fang_an):

for i in range(len(land)):

for j in range(len(land[i])):

if (land[i][j]=='1' and fang_an[i][j]=='1') or (land[i][j]=='0' and fang_an[i][j]=='0'):

return False

return True

def bing(fang_an1,fang_an2,flag):

if flag=='0':

return fang_an1

elif flag=='1':

answer = []

for i in range(len(fang_an1)):

answer.append('')

for j in range(len(fang_an1[i])):

if fang_an1[i][j]=='1' or fang_an2[i][j]=='1':

answer[i]+='1'

else:

answer[i]+='0'

return answer

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

grass = []

fangan = {}

for i in range(n):

grass.append(input())

for j in range(q):

fangan[str(j+1)] = []

for k in range(n):

fangan[str(j+1)].append(input())

num_keneng = 2**q

list_keneng = []

for i in range(num_keneng):

bin_i = bin(i)[2:]

if len(bin_i)!=q:

bin_i = '0'*(q-len(bin_i))+bin_i

list_keneng.append(bin_i)

result0 = []

for j in range(n):

result0.append('0'*m)

flag_jie = False

p_min = q

mask_min = ''

for i in list_keneng:

result = result0

for j in range(len(i)):

result = bing(result,fangan[str(j+1)],i[j])

flag_success = is_success(grass,result)

if flag_success:

tongji_i = tongji(i)

p = tongji_i[0]

if p <= p_min:

p_min = p

mask_min = i

flag_jie = True

if not flag_jie:

print(-1)

else:

result_i = mask_min

list_result = tongji(result_i)[1]

print(p_min)

print(' '.join(list_result))

发表于 2025-03-19 20:33:29 回复(0)

提交观点

小心火烛的歪

输入描述:

输出描述:

输入

输出

输入

输出

说明

问题信息

热门推荐

相关试题