[Python3] 超级码力在线编程大赛初赛 第1场题解

时间:2020-8-30 作者:admin


P1 树木规划

描述
在一条直的马路上,有

nn

棵树,每棵树有一个坐标,代表它们距离马路起点的距离。 如果每相邻的两棵树之间的间隔不小于

dd

,那么我们认为这些树是美观的。 请计算出最少移除多少棵树,可以让这些树变得美观。

树木的棵树为

nn

1n1051 \leq n \leq 10^{5}

。 树木的坐标用

treestrees

表示

00 \leq

trees

i109_{i} \leq 10^{9}

。 最小美观间隔为

dd

1d101 \leq d \leq 10^{\circ}

。 保证输入的坐标是排好序的,且两两不相同。

说明
样例中,将位置

22

66

的树木移走,剩下 [1,3,5],它们是美观的。

class Solution:
    """
    @param trees: the positions of trees.
    @param d: the minimum beautiful interval.
    @return: the minimum number of trees to remove to make trees beautiful.
    """
    def treePlanning(self, trees, d):
        # write your code here.
        rem = 0
        pre = trees[0]
        for x in trees[1:]:
            if x - pre >= d:
                pre = x
            else:
                rem += 1
        return rem

P2 正三角形拼接

描述
给出

nn

根木棍,每次切割可以将

11

根木棍切成

22

段。 请计算出最少切割几次,可以从所有木棍中选出

33

根,组成一个 正三角形 。

一开始的木棍根数为

nn

3n10003 \leq n \leq 1000

。 所有木棍的长度为一个整型数组

lengthslengths

11 \leq

length

i109_{i} \leq 10^{9}

。 切割必须要将木棍分成 根整数长度的木棍,而且总长度要和原木棍相等。

说明
可以从长为

77

的木棍中,切出

22

根长为

33

的木棍,那么木棍的长度应该为[2,3,1,3,3,5] ,可以拼出边长为 的正三角形。

class Solution:
    """
    @param lengths: the lengths of sticks at the beginning.
    @return: return the minimum number of cuts.
    """
    def makeEquilateralTriangle(self, lengths):
        # write your code here.
        c = collections.Counter(lengths)
        for k, v in c.items():
            if v >= 3:
                return 0

        A2 = [k for k, v in c.items() if v == 2]
        if len(A2) > 0:
            m = min(A2)
            for x in lengths:
                if x > m:
                    return 1
        for x in lengths:
            if 2 * x in lengths:
                return 1
        return 2

P3 大楼间穿梭

描述
蜘蛛侠在大楼间穿梭。大楼的高度可以看作是一个从左到右排列的数组。 现在蜘蛛侠站在第一栋大楼上,他想跳到最后一栋上。 蜘蛛侠的视野为

kk

,他可以花费

xx

点体力,用蛛丝移动到右侧

kk

幢建筑中第一栋比当前位置高的大楼。 或者蜘蛛侠可以花费

yy

点体力,跳跃到右侧接下来两栋大楼其中一栋。 请计算蜘蛛侠最少花费多少体力,到达最后一栋上。

大楼的高度为数组

heightsheights

,一共有

nn

栋大楼,

2n1052 \leq n \leq 10^{5}

,

11 \leq

heights

i109_{i} \leq 10^{9}

. 蜘蛛侠的视野为

kk

1kn1 \leq k \leq n

。 两种行动的体力花费满足

1x,y1091 \leq x, y \leq 10^{9}

说明
样例中,先花费

66

点体力跳到第三栋建筑,再花费

1010

点到达最后一栋。

解:

  1. 单调栈 + 动态规划
  2. 难点在题目的描述是错误的, k步范围内可以调到相同高度的楼。
class Solution:
    """
    @param heights: the heights of buildings.
    @param k: the vision.
    @param x: the energy to spend of the first action.
    @param y: the energy to spend of the second action.
    @return: the minimal energy to spend.
    """
    def shuttleInBuildings(self, heights, k, x, y):
        # write your code here.
        n = len(heights)
        suf = [-1] * n
        inf = 10 ** 14
        dp = [inf] * n
        dp[0] = 0
        stack = []
        # 1 first build
        for i in range(n-1, -1, -1):
            while stack and heights[i] > heights[stack[-1]]:
                stack.pop()
            if stack:
                suf[i] = stack[-1]
            stack.append(i)
        for i in range(0, n):
            if suf[i] != -1 and suf[i] - i <= k:
                dp[suf[i]] = min(dp[suf[i]], dp[i] + x)
            for di in [1, 2]:
                j = di + i
                if j < n:
                    dp[j] = min(dp[j], dp[i] + y)
        return dp[-1]
    def baseline(self, heights, k, x,y):
        n = len(heights)
        inf = 10 ** 14
        dp = [inf] * n
        dp[0] = 0
        for i in range(n):
            for j in range(i+1, min(i+k+1, n)):
                if heights[j] >= heights[i]:
                    dp[j] = min(dp[j], dp[i] + x)
                    break
            for j in range(i+1, min(n, i+2+1)):
                dp[j] = min(dp[j], dp[i] + y)

        return dp[-1]

if __name__ == "__main__":
    heights = [1,5,4,3,3,5,1]
    k = 3
    x = 10
    y = 6
    print(Solution().shuttleInBuildings(heights, k, x, y))
    print(Solution().baseline(heights, k, x, y))


P4 对称前后缀

描述
给定一个字符串

ss

。 我们令一个字符串的权值为一个字符串的最长对称前后缀长度。 请求出

ss

的所有子串的权值的总和。 例如,“abcxyzcba” 的最长对称前后缀的长度为

33

,因为 “abc” 和 “cba” 对称。

字符串的长度为

nn

1n31031 \leq n \leq 3 * 10^{3}

。 字符串均由小写英文字符组成。

说明
样例中,单个字符的子串的权值为

11

,它们的和为

77

。 另外的权值为: “bacb” -> 1 “bacbdab” -> 2 “bdab” -> 1 “acbda” -> 1 所以权值和为

1212


解:

  1. 常规dp
  2. 修正回文串, “afa”=> 3. 将dp值大于等一半长的改为长。
class Solution:
    """
    @param s: a string.
    @return: return the values of all the intervals.
    """
    def suffixQuery(self, s):
        # write your code here
        n = len(s)
        ret = 0
        dp = [[0] * n for _ in range(n)]
        for k in range(1, n+1):
            for i in range(n):
                j = i + k -1
                if j >= n: continue
                if k == 1:
                    dp[i][j] = 1
                if k == 2:
                    dp[i][j] = 1 if s[i] == s[j] else 0
                if k > 2:
                    dp[i][j] = 1 + dp[i+1][j-1] if s[i] == s[j] else 0

                lsub = (j - i + 1) // 2
                if dp[i][j] >= lsub:
                    dp[i][j] = j - i + 1
                ret += dp[i][j]
        return ret

    def baseline(self, s):
        def f(s):
            L, R = 0, len(s) -1
            k = 0
            while L <n and  R>=0 and s[L] == s[R]:
                k += 1
                L, R = L+1, R-1
            return k
        ret = 0
        n = len(s)
        for i in range(n):
            for j in range(i, n):
                ret += f(s[i:j+1])
        return ret

import random
def randnstr(n):

    return "".join(map(lambda x: chr(x), [random.randint(ord('a'), ord('e')) for _ in range(n)]))
if __name__ == "__main__":
    for k in range(3, 20):
        for i in range(10000):
            s = randnstr(2)
            if Solution().suffixQuery(s) != Solution().baseline(s):
                print(s)
    s = "fdafas"
    print(Solution().suffixQuery(s), Solution().baseline(s))
    print("finish")

总结

  1. 题目都是基础题, 但是坑一定是有的, 有些常规坑,有的是你想不到的坑,例如题目是错误的。
  2. 一开始不能输入测试数据,以为这次比赛不能测, 结果发现是bug, 下次打比赛一定关注钉钉群。
声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。