周赛240407

出师不利，第一题变量名能写错，慢就是快，少就是多，提交之前一定要有万全的检查。

第二题100242. 满足距离约束且字典序最小的字符串

纯思维题，先花时间想清楚基础问题再想后面的问题。吸取教训，代码一定要写的清晰明了，自己才能更好的看懂并写下去。

Python 取模运算中余数符号和除数符号一致，并满足：$被除数-除数*商(整除)=余数$

思路：转换问题，问不超过k，那么用完$k$是最优的，因为用$k$总能使字典序变小(除非原序列全是$a$), 那么就依次枚举，知道不能转换为$a$的情况下将剩余的$k$转换称可以转换成的最小的字典序字母。

class Solution:
    def getSmallestString(self, s: str, k: int) -> str:
        s = list(s)
        n = len(s)
        for i in range(n):
            d = min(ord(s[i])-ord('a'), ord('a')-ord(s[i])+26)
            if k>=d:
                k-=d
                s[i]='a'
            else:
                num = ord(s[i])-ord('a')
                ch = min((num-k)%26, (num+k)%26)
                ch = chr(ch+ord('a'))
                s[i] = ch
                break
        return ''.join(s)

第三题 3107. 使数组中位数等于 K 的最少操作数

这题比较简答，最后一刻用二分交的，结果右端点取值保守错了一发。

实际不需要二分，在排好序的序列里，用中位数去靠近中位数更优，所以直接排序计算将前面比k大的和后面比$k$小的计算差值就可以了。

class Solution:
    def minOperationsToMakeMedianK(self, nums: List[int], k: int) -> int:
        nums.sort()  
        n = len(nums)
        mid = n // 2  
        op=abs(nums[mid]-k)
        for i in range(mid): 
            if nums[i]>k:
                op += nums[i] - k
        for i in range(mid+1, n):
            if nums[i]<k:
                op += k - nums[i]
        return op

第四题100244. 带权图里旅途的最小代价

并查集+思维题。如果一些数字相与$(and)$， 如果存在较小的数字二进制位中是$0$，那么就算有再多的数字在这一位上是$1$也没有用了。所以在一个连通块内最小代价就是所有边都走一遍，而连通块可以用并查集来判断。

class Solution:
    def minimumCost(self, n: int, edges: List[List[int]], query: List[List[int]]) -> List[int]:
        def find(x):
            if p[x]!=x:
                p[x]=find(p[x])
            return p[x]
        p={i:i for i in range(n)}
        dis={}
        ret=[]
        for u,v,_ in edges:
            p[find(u)]=find(v)
        for u,v,w in edges:
            pu = find(u)
            if pu not in dis:
                dis[pu]=w
            else:
                dis[pu]&=w
        for x,y in query:
            if x==y:
                ret.append(0)
                continue #如果相等一定要continue
            px, py = find(x), find(y)
            if px==py:
                ret.append(dis[px])
            else:
                ret.append(-1)
        return ret