博览局网站建设,深圳大浪有做网站的吗,帝国备份王wordpress,字体设计说明本期比赛的在线测试系统好像出了点问题#xff0c;导致很多选手最后提交的分数是0#xff0c;而问哥也遇到好几次提交后一直显示“运行中”而没有结果的情况。鉴于之前遇到过类似情况#xff0c;不停地刷新页面才得以继续。但是此问题已经存在并持续了好几期#xff0c;极大… 本期比赛的在线测试系统好像出了点问题导致很多选手最后提交的分数是0而问哥也遇到好几次提交后一直显示“运行中”而没有结果的情况。鉴于之前遇到过类似情况不停地刷新页面才得以继续。但是此问题已经存在并持续了好几期极大地影响了参赛体验希望官方重视起来并尽快修复。 第一题天然气订单 天然气运输成本昂贵危险性高为了节省运输成本提倡绿色环保需要尽可能的优化订单配送比如相同地区的天然气订单可以一次性配送。现需要向多个地区运输天然气。但是同一个地区可能有多个订单需求。当前仅只知道某些成对的订单是同一个地区的同一个地区的天然气需要尽可能一次性配送从而降低运输成本所以需要尽可能的将同一个地区的订单放在一起。订单的编号是1到n。 输入描述输入第一行是两个正整数nm表示订单的数量和已知的关系数量。(1nm10000)接下来有m行每行两个正整数a和b表示a号订单和b号订单属于同一个地区(1a,bn)接下来有n行每行两个正整数xy分别表示该车完成A地任务的利润和B地任务的利润。 输出描述输出第一行包含一个整数x表示这些订单共来自x个不同的地区。接下来的输出包含x行每行表示输出若干个订单编号表示这些订单属于同一个地区按照订单编号升序输出。优先输出最小的订单编号较小的地区。 示例 示例输入7 6 1 2 2 2 3 2 4 5 5 4 6 7输出3 1 2 3 4 5 6 7分析
看到“xx的编号是1到n”的描述首先想到的就是并查集的数据结构。然后发现此题还是求连通子图同属一个地区的订单类似此前考过的《蚂蚁家族》和《交际圈》。但是本题除了要求连通子图的个数还要输出每个子图中的所有节点。
使用深搜dfs应该也能做如果用并查集的话还需要用到并查集的两个优化操作路径压缩和按秩合并不然可能会超时。又因为最后要输出每个连通子图的所有节点只需要把按秩合并后的并查集中最早出现的“祖先”作为键其他成员作为值生成一个字典即可。最后字典中键的个数即连通子图的个数而每个连通子图的节点也已经排好序了直接输出即可。
参考代码 n, m map(int, input().strip().split())
nodes list(range(n1))# 路径压缩的查集操作
def find(n):if nodes[n] n: return nnodes[n] find(nodes[n])return nodes[n]for _ in range(m):a, b map(int, input().strip().split())aa find(a)bb find(b)# 按秩合并的并集操作if aa bb: nodes[bb] aaelse: nodes[aa] bbres dict()
for i in range(1, n1):if nodes[i] i:res[i] [i]else:res[find(nodes[i])].append(i)print(len(res))
for value in res.values():print(*value) 并查集的操作很简单简单来讲路径压缩就是每次查找时都把查找路径中所有的节点指向目前的“公共祖先”使得后面的查找不用再重复查找路径而按秩合并就是优先把数字更小排在前面的节点作为“祖先” 这样可以使得并查集的树形结构深度最小更加平衡。而本解法实际利用了按秩排序的最早公共祖先以及排序性质。 第二题小艺读书 书是人类进步的阶梯。小艺每周因为工作的原因会选择性的每天多读几页或者少读几页。小艺想知道一本n页的书她会在周几读完。 输入描述第一行输入n(1n1000)第二行输入7个整数分别表示周一~周日的读书页数p(0p1000)。不考虑7个整数都为0的情况 输出描述输出答案。1-7 示例 示例输入100 15 20 20 15 10 30 45输出 6 分析
题目描述不是特别好没有说明从哪一天开始读书那就只能默认从周一开始了虽然常识里感觉怪怪的。而测试用例也不全面没有周日读完的情况也就是输出7。对于考察循环数组的简单题来说不完整的测试用例使得本题更水了。
解题方法就是循环模拟下标每次加一如果循环至下一周下标要对7取模。最后输出下标即可。要注意的是如果是周日读完此时下标为0要特判输出7但是本题的测试用例没有出现这种情况。
参考代码 n int(input().strip())
pages [int(item) for item in input().strip().split()]
i 0
while n 0:n - pages[i]i (i1)%7
if i 0: print(7)
else: print(i) 第三题买苹果 小易去附近的商店买苹果奸诈的商贩使用了捆绑交易只提供6个每袋和8个每袋的包装(包装不可拆分)。 可是小易现在只想购买恰好n个苹果小易想购买尽量少的袋数方便携带。如果不能购买恰好n个苹果小易将不会购买。 输入描述输入一个整数n表示小易想购买n(1 ≤ n ≤ 100)个苹果 输出描述输出一个整数表示最少需要购买的袋数如果不能买恰好n个苹果则输出-1 示例 示例输入20输出 3 分析
我猜本题原本是想考察完全背包但是由于数据范围很小使用暴力穷举也能过。
因为要买恰好 个苹果所以最多只能买 袋每袋6个装的苹果和 袋每袋8个装的苹果均向下取整有点像百钱百鸡。于是设 暴力枚举每一种 的组合如果 就把 的结果保存在集合里。最后输出集合中的最小值即可。如果不存在满足该等式的 则集合为空输出 -1。
参考代码 n int(input().strip())
res set()
for i in range((n//6)1):for j in range((n//8)1):if 6*i 8*j n:res.add(ij)
if res: print(min(res))
else: print(-1) 算法复杂度为 准确来讲计算了 次所以当 n 很小时和使用DP完全背包的算法复杂度 m为物品的种类本题为2没有什么区别。关于完全背包感兴趣的同学可以参考网上资料问哥之前的文章也有涉及此处不再赘述。 第四题圆桌 有N个客人与足够多张的圆桌。主人安排每位客人坐在一个圆桌边但是每位客人希望自己左右边上分别有一些空座位不然会觉得害羞。注意如果一个客人所在的圆桌只有他一个人那么他左边的空座位数量就是他右边的空座位数量。试问主人需要准备多少个座位才能让每个客人舒适的坐下。 输入描述第一行输入一个整数N(1N10000),代表客人的数量接下来N行每行两个整数li与ri(1iN,1liri1000000000)代表第i位客人希望左边有li个空座位右边有ri个空座位。 输出描述输出一个整数代表主人需要准备的最少座位数量。 示例 示例输入3 1 1 1 1 1 1输出6分析
第11期考过的老题可以参考网上的题解也可以参考我以前的文章。
本题有一定思维难度当时问哥也是把时间浪费在证明算法的正确性上了但如果想通了代码不过寥寥数行。
