代码不是很好看。前4题都ac了,最后一题9%,求大佬思路
第一题:
给定一个时间,包括星期、时、分,然后再给一个分钟数n,输出给定时间往前n分钟的星期、时、分,时分都是2位,不足首位补0。
思路:先把往前推的天数对10080取余,也就是一周的分钟数,然后对week,h,m的修改分别求出来,通过一个标志位判断是否借位:
pre = pre % 10080 week_ = pre // 1440 h_ = (pre % 1440) // 60 m_ = pre % 60 if m < m_: carry = 1 m += 60 - m_ else: carry = 0 m -= m_ if h < h_ + carry: h = h + 24 - h_ - carry carry_w = 1 else: h = h - h_ - carry carry_w = 0 week_ += carry_w if week <= week_: week = week + 7 - week_ else: week = week - week_ h, m = str(h), str(m) if len(h) == 1: h = '0' + h if len(m) == 1: m = '0' + m print(str(week)) print(h + ':' + m)
第二题:
有n个运动员,给2个长为n的数组,分别为出发时各个位置上运动员的编号和到达时运动员的编号,那么问到达时超过了别人的运动员有几个。
例子:
5
[5, 3, 1, 4, 2]
[2, 4, 5, 1, 3]
答案:
3
第一行为出发时的编号,第二行为到达时的编号,上例中只有3和5没有超过别人。
额。。双指针,具体看代码
n = 5 start = [5, 3, 1, 4, 2] end = [2, 4, 5, 1, 3] res = 0 idx1, idx2 = 0, 0 s = set() while idx1 < n: if start[idx1] in s: idx1 += 1 continue while end[idx2] != start[idx1]: res += 1 s.add(end[idx2]) idx2 += 1 idx1 += 1 idx2 += 1 print(res)
第三题
场景就不说了
给n和k,输出最小的x使得
[x] + [x/k] + [x/k^2] + ...
[x]为向下取整,总有一个时刻[x/k^m]==0,因此求使得前面m项和大于n的最小x。
思路:x从1开始会超时,我的解法比较暴力,只是在x的开始位置求了一下,从[n/k]*(k-1)开始,直到n,然后就AC了。。
n, k = 10, 3 ans = -1 for i in range(n // k * (k - 1), n + 1): total = 0 ii = i while ii: total += ii if total >= n: ans = i break ii //= k if ans != -1: break print(ans)
第四题
场景是正方形SABC,正方形各个点都是联通的,从S开始,经过n步之后回到S的不同路径。
思路:dp不行,会超时,找规律
n S A B C
0 1 0 0 0
1 0 1 1 1
2 3 2 2 2
3 6 7 7 7
每一轮迭代之后大概就是这样的,规律显而易见了。。
例子:
n = 3
答案:
6
解释:
S->A->B->S
S->A->C->S
S->B->A->S
S->B->C->S
S->C->A->S
S->C->B->S
n = 3 a, b = 1, 0 for i in range(1, n + 1): if i % 2 == 1: a = (3 * b) % 1000000007 b = a + 1 else: a = (3 * b) % 1000000007 b = a - 1 print(a)
看到有人觉得第四题规律不知道怎么找的,我想了下,是可以推出来的
dp的思想,S是从ABC过来的,ABC其实是一样的,同等地位的,所以dp[n][S] = 3 * dp[n-1][A],然后就是ABC的规律了。A是从SBC过来的,因此dp[n][ABC] = dp[n-1][S] + 2 * dp[n-1][BC],所以结果就是
S, A = 3 * A, S + 2 * A
代码如下:
n = 3 a, b = 1, 0 for i in range(n): a, b = (3 * b) % 1000000007, (a + 2 * b) % 1000000007 print(a)
第五题
没思路,求大佬告知
全部评论
(8) 回帖