Leetcode第341场周赛解题报告（补档）

本次题目难度还是过低，不清楚具体什么情况

2643. 一最多的行

知识点：智商
复杂度：$O(n)$

class Solution:
    def rowAndMaximumOnes(self, mat: List[List[int]]) -> List[int]:
        l = [0] * len(mat)
        for idx, line in enumerate(mat):
            for v in line:
                if v == 1:
                    l[idx] += 1
        mxl = max(l)
        for idx, line in enumerate(l):
            if mxl == line:
                return [idx, line]

2644. 找出可整除性得分最大的整数

知识点：模拟
复杂度：$O(n)$
无语了 怎么这么简单

class Solution:
    def maxDivScore(self, nums: List[int], divisors: List[int]) -> int:
        s = [
            sum(1 if j % i==0 else 0 for j in nums)\
             for i in divisors
        ]
        mxl = max(s)
        cnt = []
        for i in range(len(divisors)):
            if mxl == s[i]:
                cnt.append(divisors[i])
        return min(cnt) 

2653. 滑动子数组的美丽值

知识点：动态规划/状态机
复杂度：$O(n)$
根据题意，假设当前的字符<=上一个字符，那么就说明需要新一轮abc
然后最终的答案就是需要的轮数*3-字符串长度

class Solution:
    def addMinimum(self, word: str) -> int:
        ln = 1
        lst = -1
        for i in word:
            n = ord(i) - ord('a')
            if n <= lst:
                ln += 1
            lst = n
        return ln * 3  - len(word)

2646. 最小化旅行的价格总和

知识点：树形DP
复杂度：$O(2 * n)$

这题本质上是一个折半/不折半的问题，类似于背包，但是受到上一次选择的状态限制。
因此对于每一个点而言，有两种状态，折半和不折半，分别记录当前点折半/不折半情况下的最小代价，然后最后min一下就好了。

这题最重要的是要预处理访问次数，要意识到访问次数与最终答案有关
然后就是知道树的性质，因为树本质上，从点A到点B，只有一个路径，因此不用找最小代价的路径（如果是图的话这题应该会很麻烦）

状态转移的过程：上一个节点折半过，那么当前节点必然不能折半。上一个节点没有折半过，那么当前节点可以折半，也可以不折半。

class Solution:
    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:
        #dp[2] 
        #0: not selected
        #1: selected

        # transfer: 1->0
        # transfer: 0->0 0->1
        
        cnt = [0] * (n + 1)
        p = [[]for i in range(n+1)]
        # 建树
        for a,b in edges:
            p[a].append(b)
            p[b].append(a)
        
        # 树上存在唯一路径，因此统计访问次数

        for a,b in trips:
            def sp(now,lst):
                if now == b:
                    cnt[now] += 1
                    return True
                for i in p[now]:
                    if lst == i:
                        continue
                    if sp(i,now):
                        cnt[now] += 1
                        return True
            sp(a,-1)
        
        def dfs(now, lst):
            pri = price[now] * cnt[now]
            hv_pri = pri // 2
            for i in p[now]:
                if lst == i:
                    continue
                nxt_ful, nxt_hav = dfs(i, now)
                pri += min(nxt_ful, nxt_hav)
                hv_pri += nxt_ful
            return pri, hv_pri
        return min(dfs(0,-1))