赞
踩
本期除了第三题有点小坑,其他题都是几行代码的事。
一个等差数列是一个能表示成a, a+b, a+2b,..., a+nb (n=0,1,2,3,...)的数列。在这个问题中a是一个非负的整数,b是正整数。 现给出三个整数,分别表示等差数列的第一项a、最后一项、公差b,求该数列的和。
输入描述:输入三个整数,之间用空格隔开。第1个数作为首项(0≤a≤1e10),第2个数作为末项(0<c≤1e10),第3个数作为公差(0<b≤1000).
输出描述:输出占一行,包含一个整数,为该等差数列的和。如果所给三个整数,不能构成等差数列,则返回-1。
示例:
示例一 输入 2 11 3 输出 26
本题关键是怎样理解“不能构成等差数列”的情况。根据题意,首项 a,末项 n,和公差 b 都已经给出,那么只要检查首项和末项是否同时存在数列中即可。
我们可以固定 a 为首项,以末项 n 为终点,设置步长为 b,生成一个 range 对象,它自然是一个等差数列。然后只要检查生成的等差数列的末项是不是 n(检查 n 是否在此 range 中即可)。
- a, n, b = map(int, input().strip().split())
- nums = range(a, n+1, b)
- if n in nums:
- print(sum(nums))
- else:
- print(-1)
在希腊神话中,有一个神祗阿波罗。阿波罗拥有一枚能够使人变得更加聪明的神奇宝石。但是,这枚宝石的魔力被封印在了一个混乱的顺序中,你需要通过排序的方法才能拥有这枚宝石的魔力。 给定一个长度为 N 的整数数组 A,请你将数组 A中的元素进行冒泡排序。
输入描述: 第一行包含整数 N(0<N<100000)。 第二行包含 N 个整数(0≤X<100000),表示数组 A。
输出描述: 输出N行,每行包含一个整数,表示排序后的数组 A。
示例:
示例一 输入 5
2 5 3 1 4输出 1
2
3
4
5
题目的本质是排序,但只是从字面去要求冒泡排序是没用的,因为只要答案正确,就能pass,凡是 Online Judge 的比赛都不会检查代码实现的过程。而且冒泡排序的复杂度是 ,python自带的sort方法排序,快排、归并等,都是 ,如果以本题的数据范围 ,乖乖地使用冒泡排序,反而有可能不通过(Python使用传统排序方法实现排序的效率要比C++差许多)。
- n = int(input())
- nums = map(int, input().strip().split())
- print(*sorted(nums), sep="\n")
如果感兴趣的话,你也可以手写冒泡试试,网上模板很多,这里就不啰嗦了。
小明手头上有n个问题,每个问题都有一个数值,表示这个问题的难度;正好小明团队有n个人,每个人都有一个数值,表示这个人的能力。现在小明要把这n个问题分配给每个人,要求能力更高的人分配到更高难度的问题。
输入描述:第1行包含一个数字 n (n <= 100000),表示小明手头上有n个问题,团队有n个人 第2行到第n+1行,每一行包含1个数字,表示n个问题的难度(正整数,小于10^9)。第n+2到2n+1行,每一行包含一个数字,表示团队n个人的能力值(正整数,小于10^9)。
输出描述:输出n行,按输入的顺序,输出每个人分配到的问题的难度,如果有两个人能力值相同,那么输入的顺序靠前,分配到更高难度的问题。
示例:
示例一 输入 3
1
2
3
3
2
1输出 3
2
1
思路很明显,先排序,把难度最大的任务按次序分给能力最大的人,然后最后按照每个人出现的顺序输出任务就好。但是这里存在一个小坑,就是“如果有两个人能力值相同,那么输入的顺序靠前,分配到更高难度的问题。”如果直接对人的能力采用降序排序,能力相同的人的位置会发生改变。比如,如果有4个人,输出的顺序以能力代表分别是,1,2,2,3,如果使用sort加reverse关键字按能力从大到小排序,中间两个2的位置会发生翻转,于是对应难度值降序排列的任务时,能力相同但是后输入的人对应的难度更高,这样便得不到正确答案。
对于此类问题(需要降序排列,但要保持正序排列的相对位置),有个常用的小技巧,就是把数组每个数字都转成负数,然后再来一遍升序排列,相对位置即可保持不变。而此题的数组转换成负数后,对应的其实就是能力最大的人,不需要再把负数转变回去,只要将难度降序排列的任务对应上就好。
在代码实现上,我使用了 zip 函数将输入的顺序变成一个二元组,最后再将结果的对应位置放入任务。
- n = int(input().strip())
- task = [int(input().strip()) for _ in range(n)]
- ppl = [int(input().strip()) for _ in range(n)]
- ppl = sorted(zip((-i for i in ppl), range(n)))
- result = [0]*n
- task.sort(reverse=True)
- for i, j in enumerate(ppl):
- result[j[1]] = task[i]
- print(*result, sep = "\n")
对于一个字符串,请设计一个算法,只在字符串的单词间做逆序调整,也就是说,字符串由一些由空格分隔的部分组成,你需要将这些部分逆序。 给定一个原字符串A,请返回逆序后的字符串。例,输入“It’s a dog!”输出“dog! a It’s”
输入描述:输入一行字符串str。(1<=strlen(str)<=10000)
输出描述:返回逆序后的字符串。示例:
示例一 示例二 输入 It’s a dog! ABC 输出 dog! a It’s ABC
本期的大水题竟然放在最后一道,有点出乎意料。实在没啥好分析的,题目给的模板已经把单词按空格分隔成了列表,所以直接把列表翻转,再用空格拼接然后打印出来即可。
- s = input().strip().split()
- print(" ".join(s[::-1]))
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。