CCF 202009-3 点亮数字人生 python 满分

题目叙述问题描述：略输入格式：略输出格式：略样例 满分证明解题思路两个难点第一，判断存在环路第二，将全部FUNC（逻辑功能）按顺序读入运行 具体实现思路 满分代码感谢及参考博文

题目叙述

问题描述：略

输入格式：略

输出格式：略

样例

样例输入1 1 3 5 XOR 2 I1 I2 XOR 2 O1 I3 AND 2 O1 I3 AND 2 I1 I2 OR 2 O3 O4 4 0 1 1 1 0 1 1 1 1 0 0 0 2 5 2 2 5 2 2 5 2 2 5 2 样例输出1 1 0 1 0 1 1 0 0 样例输入2 1 2 6 NOR 2 O4 I2 AND 2 O4 O6 XOR 2 O5 O1 NOT 1 O6 NAND 2 O2 O2 AND 2 I1 O3 2 0 0 1 0 3 2 3 4 6 1 2 3 4 5 6 样例输出2 LOOP 样例输入3 1 1 2 AND 2 I1 O2 NOT 1 O1 2 0 1 0 0 2 1 2 样例输出3 LOOP 样例输入4 1 2 4 AND 2 I1 I2 NAND 2 O1 O1 XOR 2 O2 O2 NOT 1 O2 2 0 1 1 1 0 0 2 1 2 样例输出4 1 0 样例输入5 1 3 9 AND 3 I1 I2 I3 OR 3 I1 I2 I3 AND 2 I1 I2 AND 2 I1 I3 AND 2 I2 I3 OR 2 O1 O7 AND 2 O2 O8 NOT 1 O9 OR 3 O3 O4 O5 8 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 2 6 9 2 6 9 2 6 9 2 6 9 2 6 9 2 6 9 2 6 9 2 6 9 样例输出5 0 0 1 0 1 0 0 1 1 0 0 1 0 1 1 1 样例输入6 1 3 8 NAND 2 O2 O3 NAND 2 I1 O4 NAND 2 I2 O4 NAND 2 I1 I2 NAND 2 O6 O7 NAND 2 O1 O8 NAND 2 I3 O8 NAND 2 O1 I3 8 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1 5 1 5 1 5 1 5 1 5 1 5 1 5 1 5 样例输出6 0 1 1 0 1 0 0 1

满分证明

红色框框是我的，第一个是用C++写的（链接见参考）

解题思路

这题就是读起来太长了，不过理解了还好! 先说难点再说实现思路。

两个难点

第一，判断存在环路

该问题为判断有向图是否存在环路，要用到图的知识，用拓扑排序判断环或者DFS判断。 构建邻接矩阵，然后使用上述两种中任意一种方式，有位大佬已经给出模块化公式，详情见参考博文链接。

第二，将全部FUNC（逻辑功能）按顺序读入运行

第一种思路 本来我想的是先将所有输入全为I（不需要运算）的器件读完，再将剩下的全部按O大小排序，依次读入。 想法很好，具体实现也实现了，但在测试参考博文1给出的样例时不能通过，才发现其中bug。进而转为采用第二种思路。 第二种思路 在每个器件后面加一个状态值，用while循环判定是否全部执行完。

具体实现思路

解决完上面两个难点，问题就简单很多了。

将所有具体逻辑功能进行封装成函数随时准备调用；依据题意自行构建邻接矩阵（注意这里是有向图）函数模块；判断有向图是否为环函数模块；进行模拟运算函数模块；主程序，按照题意的输入读入数据输出数据。

细节注意（在编写上述程序时有几个注意事项）

在具体逻辑功能函数中，虽然NOT只有一个参数，但为了和其他模块适配，也要写成传入数组的形式，方便管理；在编写NAND和NOR函数时，注意调用NOT函数时，传入为数组；一般在编写程序时，输出是在全部读入结束后进行。所以全部输出进行存储，最后一次输出；在编写模拟运算函数时，涉及嵌套数组的复制（仅仅复制值，改变时原值不变），这里会涉及深度拷贝，不懂的可以查看参考博文3（讲的很详细）；在模拟运算函数时，整个模拟在while循环中进行，使用计数器判定是否跳出循环。先判断该运算函数有没有被执行过（每个函数的状态），再判断该运算函数能不能被执行（其运行的先决条件能否被满足）。第二个判断我是将所有输出赋值为-1，检测先决条件中有没有-1，再决定执不执行该运算函数；在输出的时候也要注意LOOP的出现，作为特殊情况处理。

满分代码

import copy def _NOT(ll): if not ll[0]: return 1 else: return 0 def _AND(ll): st = ll[0] for i in range(1, len(ll)): st = st and ll[i] return st def _OR(ll): st = ll[0] for i in range(1, len(ll)): st = st or ll[i] return st def _XOR(ll): st = ll[0] for i in range(1, len(ll)): st = st ^ ll[i] return st def _NAND(ll): return _NOT([_AND(ll)]) def _NOR(ll): return _NOT([_OR(ll)]) # 构建邻接矩阵 def buildmatrix(temfunc): mat = [[0] * len(temfunc) for _ in range(len(temfunc))] for i in range(len(temfunc)): for j in range(2, int(temfunc[i][1]) + 2): if temfunc[i][j][0] == "O": mat[int(temfunc[i][j][1:]) - 1][i] = 1 return mat # 判断是否存在环 def findcircle(G): node_set = set() r = len(G) have_in_zero = True while have_in_zero: have_in_zero = False for i in range(r): if i not in node_set and not any([row[i] for row in G]): node_set.add(i) G[i] = [0] * r have_in_zero = True break return False if len(node_set) == r else True def light(S, M, N, ip, op, func): res = [] for i in range(S): I = {} O = {} for j in range(1, M + 1): I[j] = ip[i][j - 1] for j in range(1, N + 1): O[j] = -1 tem_func = copy.deepcopy(func) count = len(func) while count != 0: for p in range(len(func)): # 函数未被执行过 if tem_func[p][-1]: num = int(func[p][1]) te = '' for k in range(num): te += func[p][2 + k][0:1] + "[" + func[p][2 + k][1:] + "]," tel = te[:-1] if tel.find(",") != -1: tep = list(eval(tel)) else: tep = [eval(tel)] if -1 not in tep: O[p + 1] = eval("_" + func[p][0] + "(" + str(tep) + ")") count -= 1 tem_func[p][-1] = False # 存储运算结果 res.append(list(O[op[i][l]] for l in range(1, op[i][0] + 1))) return res count = int(input()) fin = [] for _ in range(count): M, N = map(int, input().split()) func = [] ip = [] op = [] for _ in range(N): # 加一个状态值，判定有没有执行 temp_func = list(map(str, input().split())) temp_func.append(True) func.append(temp_func) S = int(input()) for _ in range(S): ip.append(list(map(int, input().split()))) for _ in range(S): op.append(list(map(int, input().split()))) if findcircle(buildmatrix(func)): fin.append("LOOP") continue fin.append(light(S, M, N, ip, op, func)) for i in range(len(fin)): for j in range(len(fin[i])): if fin[i] == "LOOP": print(fin[i]) break for k in range(len(fin[i][j])): print(fin[i][j][k], end=" ") print()

感谢及参考博文

部分内容参考以下链接，这里表示感谢 Thanks♪(･ω･)ﾉ 参考博文1 点亮数字人生( 202009-3/CCF)———附带思路和完整代码（邻接表、邻接矩阵） https://blog.csdn.net/qq_33375598/article/details/108914796 参考博文2 两种方式判断有向图是否有环-python实现 https://blog.csdn.net/songyunli1111/article/details/101559771 参考博文3 第 20 次 CSP认证-202009-Java-点亮数字人生（亮不起来T_T）（内附代码和若干测试用例） https://blog.csdn.net/H_X_P_/article/details/108569908 参考博文4 Python的深浅拷贝 https://www.cnblogs.com/shiqizz/p/11514870.html