题目列表

1. AC 公因子的数目
2. AC* 沙漏的最大总和
3. AC* 最小 XOR
4. AC 对字母串可执行的最大删除数

赛后总结

太菜了，以至于拿力扣当安慰赛QAQ。

虽然比赛过程不算理想，对于四道题都不算难的比赛只拿了$666$名，还有很大提升空间，而且二三题都漏情况了，跟卡时间AK的情况一样了……不过这个排名卡得实在太离谱了……

公因子的数目

签到题，数据范围忒小了点，以至于枚举都能过。

class Solution:
    def commonFactors(self, a: int, b: int) -> int:
        cnt = 0
        for i in range(1,min(a,b)+1):
            if(a%i==0 and b%i==0):cnt+=1
        return cnt

沙漏的最大总和

使用二维前缀和，手生以至于行列不分WA了一次。

class Solution:
    def maxSum(self, grid: List[List[int]]) -> int:
        sums = [0] * len(grid)
        for i in range(len(grid)):
            sums[i] = [0] * len(grid[0])
            for j in range(len(grid[0])):
                sums[i][j] = grid[i][j]
        for j in range(1,len(grid[0])):
            sums[0][j] += sums[0][j-1]
        for i in range(1,len(grid)):
            sums[i][0] += sums[i-1][0]
            for j in range(1,len(grid[0])):
                sums[i][j] += sums[i-1][j] + sums[i][j-1] - sums[i-1][j-1]
        #print(sums)
        ans = sums[2][2] - grid[1][0] - grid[1][2]
        for j in range(3,len(grid[0])):
            ans = max(ans,sums[2][j] - sums[2][j-3] - grid[1][j] - grid[1][j-2])
        for i in range(3,len(grid)):
            ans = max(ans,sums[i][2] - sums[i-3][2] - grid[i-1][0] - grid[i-1][2])
        for i in range(3,len(grid)):
            for j in range(3,len(grid[0])):
                ans = max(ans,sums[i][j] - sums[i-3][j] - sums[i][j-3] + sums[i-3][j-3] - grid[i-1][j-2] - grid[i-1][j])
        return ans

最小 XOR

认真地分情况讨论了，但是

class Solution:
    def minimizeXor(self, num1: int, num2: int) -> int:
        # 初始化
        nums = num1 - 0
        cnt1 = 0
        flag1 = []
        if nums == 0:flag1 = [0]
        while(nums):
            flag1.append(nums % 2)
            if nums % 2 : cnt1 += 1
            nums //= 2

        nums = num2 - 0
        cnt2 = 0
        flag2 = []
        if nums == 0:flag2 = [0]
        while(nums):
            flag2.append(nums % 2)
            if nums % 2 : cnt2 += 1
            nums //= 2
        print(flag1,flag2)
        # 分情况讨论
        ans = 0
        if (cnt1 == cnt2): return num1 # 最没有技术含量的
        elif (cnt1 > cnt2): # 只消掉cnt1最高位的1
            cnt3 = cnt1 - cnt2
            for i in range(len(flag1)):
                if flag1[i]:
                    if(cnt3):
                        cnt3 -= 1
                    else:
                        ans += 1 << i
            return ans
        else:
            if(cnt2 >= len(flag1)): # 1的数量比整个数组都多，直接把1全挤在一块
                return (1 << cnt2) - 1
            else: # 尽可能把多余1挤在较低位置
                cnt3 = cnt2 - cnt1
                for i in range(len(flag1)):
                    if not flag1[i]:
                        if(cnt3):
                            cnt3-=1
                            ans += 1 << i
                    else:
                        ans += 1 << i
            return ans

对字母串可执行的最大删除数

想了半天才意识到是递推，做了这么多数据结构现在脑子里全是数据结构……

每次合法修改只能建立在前面都是合法修改的前提之上，对于从当前位置开始的所有合法修改，修改之后每个可能结果的最大修改次数。

class Solution:
    def deleteString(self, s: str) -> int:
        dp = [-1] * (len(s)+1)
        dp[0] = 0
        for i in range(len(s)):
            if(dp[i]) == -1 :
                continue
            for j in range(1,len(s)//2+1):
                if(s[i:i+j]==s[i+j:i+2*j]):
                    dp[i+j] = max(dp[i+j],dp[i] + 1)
            dp[len(s)] = max(dp[len(s)],dp[i] + 1)
        return dp[-1]