解题思路:
    先全排列,然后筛选掉不符合的。时间复杂度O(n3),时间超限17,但用java或C/C++可以AC。
注意事项:

参考代码:

from itertools import permutations
n,m = map(int,input().split())
nums = [list(map(int,input().split())) for _ in range(m)]
count = 0
mab = list(permutations([i for i in range(n)]))
for i in range(len(mab)-1,-1,-1):
    result = []    #存储每个猜想的筛选结果,只要有一个不满足就移除这个序列
    for j in range(m):
        if nums[j][-1] == 0:    #筛选预判错了的
            for k in range(1,nums[j][0]):
                if mab[i].index(nums[j][k]) > mab[i].index(nums[j][k+1]):    #只要不是按照错误的顺序就说明满足
                    result.append(True)
                    break
                else:    #否则不满足
                    result.append(False)
                    break
                    
        if nums[j][-1] == 1:    #筛选预测对了的
            for k in range(1,nums[j][0]):
                if mab[i].index(nums[j][k]) > mab[i].index(nums[j][k+1]):    #如果不按照正确的顺序,就说明不满足
                    result.append(False)
                    break
                else:
                    result.append(True)
        if result.count(False) > 0:    #剪枝,只要有False就没必要再判断下去了
            break
    if result.count(False) != 0:
        mab.pop(i)
print(len(mab))
for i in range(len(mab)):
    for j in mab[i]:
        print(j,end=" ")
    print()


点赞(0)
 

0.0分

1 人评分

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:

一点编程也不会写的:零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码?手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的 必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

评论列表 共有 0 条评论

暂无评论