原题链接:蓝桥杯算法提高VIP-3000米排名预测
解题思路:
先全排列,然后筛选掉不符合的。时间复杂度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分
1 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:
一点编程也不会写的:零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码?手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复