题目列表

1. AC* 2404. 出现最频繁的偶数元素
2. AC 2405. 子字符串的最优划分
3. AC 2406. 将区间分为最少组数
4. TLE 2407. 最长递增子序列 II

赛后总结

总体来说没有上一次糟糕，但有些问题仍然存在。熟练度依旧不算好，初级竞赛BUG Free还是很难达到，依旧不会静态查错。

由于接下来的答案里可能会出现大量引用灵神（灵茶山艾府）题解的段落，此处就在这里供上对灵神的ORZ并留下其在LeetCode的个人主页链接作为引用内容的统一来源：https://leetcode.cn/u/endlesscheng/

2404. 出现最频繁的偶数元素

本来是一道顶针题，但就是能搞出来“1次错误尝试”也是挺离谱的。

因为题目中有提到“如果存在多个满足条件的元素，只需要返回最小的一个。”，所以要么在判断时多判断一次，要么就提前把数组先升序排好，不然如果先遍历到较大的一个答案就能搞出一些奇怪的错误。

2405. 子字符串的最优划分

这其实也是一道顶针题，但是想到了828. 统计子串中的唯一字符，就把事情想复杂了，开始思考当时是如何切割之类的……

其实只要做好标记然后一旦不满足条件就切割就OK了，没有那么复杂。

2406. 将区间分为最少组数

在权衡了这题和上一题之后，决定先完成这道题（由于前文提到的那道每日题导致一时半会没反应过来）。这题稍微读了几遍题面之后就发现，在按照起始位置优先比较、 并考虑终止位置、 （为什么划掉之后会说） 均使用升序排序后，只要统计所有组的末尾，然后建一个小根堆就可以了。考虑如下：

1. 如果 当前处理的区间 没法接到当前所有已存在组中，结束数字最小的那个区间，那么他肯定无法接到其他的区间之后；
2. 若 当前处理的区间 可以接到最小者和次小者之后，因为排序之后 下一个区间 的起始位置必然不小于 当前处理的区间，所以将现有区间接到哪个区间后面造成的效果都是相同的；
3. 若存在 $ N $ 个起始点相同的区间，而符合条件的现有组数量 $M$ 少于区间数量 $N$ ，无论如何安排，都必然会创建 $N-M$ 个区间，即最终造成的影响是等价的；
4. 接着说(3)，由于第(2)点，(3)的情况可以推广至全体未处理的区间。

所以推了半天，结束位置的影响其实没有吗？
看了一眼灵神的题解，这题其实也可以使用差分数组来做。由于 $right_i \le 10^6$ ，这个数组放在C++里是开得下的，然后使用差分计算结果后，区间最高的重叠次数就是答案，证明略。

2407. 最长递增子序列 II

这题就是自己太年轻了。比赛时也许想到了按照数字处理，但总觉得数字并不是有序的，所以可能会有问题。不过自己赛后坐下来慢慢写证明的时候也想通了。详细的说明写在程序的精注里面了，就在不远处。

虽然灵神使用的是线段树，但为了省时间自己就用分块实现了，在层次较低、不会恶意编造数据卡掉分块的场合中，分块（单次时间复杂度 $O\left( \sqrt{n}\right)$）无论是代码量还是调试难度都优于线段树（单次时间复杂度 $O\left(\log_2n\right)$），小比赛用用还是没问题的。

自己分析过分块就是不一样，这里留下链接：《浅谈分块在信息学算法的应用》

程序精注

2407. 最长递增子序列 II

"""
思路：
---------【比赛中 - TLE】
一般的DP：对于每一位nums[i]，在前面寻找满足题目要求的所有数，然后逐个比较；
一般的DP的剪枝：如果前面是下坡的，直接越过山头；如果前面是上坡的，二分
    寻找满足要求的数。
---------【比赛后 - 灵神优化(ID:灵茶山艾府)】
一、构建优化后的模型：
    首先，对于不满足要求的数字，对答案无法产生影响，根本无需遍历；
    第二，对于同一个满足要求的准备接入的末尾数字，一定是选择以该
        数字为结尾，最长子序列相对较长的那个，此条的确是易证；
    最后，由于第二条所指出的，可以将以序列中数字-数字位置为基础的
        DP优化为仅以数字本身的DP，而且根据数据范围，开数组不会造成空间超限。
    优化后的DP模型为：dp[i][j] 表示对于当前处理到第i位的数字而言，
        之前所有的以数字j为结尾的合法子序列中最长的长度，迭代方程：
            dp[i][j] = 1 + max{dp[i-1][j'] | min(0,j-k) <= j' < j}
    由于i和j均采用递增遍历，所以对于dp[i]，只有dp[i-1]的数字会造成影响，
        同时由于j' < j且单次操作只会修改dp[i][j]，所以可以直接把第一维给省略了，
        最终采用的模型是这样的：
            dp[j] = 1 + max{dp[j'] | max(0,j-k) <= j' < j}
    由于涉及到了区间取最大值，所以在此步骤的max需要另用算法优化，
        灵神使用的是线段树，我准备使用代码量更小、更好调试、自己也更熟的分块；
        复习一遍自己的文章就会了，属实是受益终身（笑）。
        [《浅谈分块在信息学算法的应用》](https://www.zhtg.net.cn/yingcai-lunwen/)
"""
class LoveStacks:
    # 分块，单点修改，区间求最大值
    # 这里默认数组从0开始
    # 将所有数字分为sqrt(n)组为最优分块方案

    # 对于当前数字 i，其所在的分块编号为 i // self.STACK_SIZE
    # 对于一个编号为 j 的分块，其处理的数据下标范围为
    #       [j * STACK_SIZE , (j+1) * STACK_SIZE)
    def __init__(self,inp):
        self.nums = inp.copy()
        self.SIZE = len(self.nums)
        self.STACK_SIZE = int(sqrt(self.SIZE))      
        self.stackMax = [0] * (self.SIZE // self.STACK_SIZE + 5)    # 注意留底
        for i,num in enumerate(self.nums):
            if num > self.stackMax[i // self.STACK_SIZE]:
                self.stackMax[i // self.STACK_SIZE] = num

    def modify(self,pos,val):
        self.nums[pos] = val
        if val > self.stackMax[pos // self.STACK_SIZE]:
            self.stackMax[pos // self.STACK_SIZE] = val

    # 处理分块
    def maxi(self,l,r):             # 习惯性定义为闭区间
        ans = 0
        # 如果区间[l,r]的大小不超过 2*STACK_SIZE
        # 那么就不需要（大概率没机会）通过分块，而是直接处理
        if r - l + 1 < 2 * self.STACK_SIZE:
            for i in range(l,r+1):
                if self.nums[i] > ans:
                    ans = self.nums[i]
            return ans

        # 处理分块左边的零碎数据
        # 左边的零碎数据范围为 [l,((l - 1) // STACK_SIZE + 1) * STACK_SIZE)
        #                            这里 + 1是为了取到左边界所处分块的右界
        for i in range(l,((l - 1) // self.STACK_SIZE + 1) * self.STACK_SIZE):
            if self.nums[i] > ans:
                ans = self.nums[i]

        # 通过分块处理范围数据
        # 分块处理数据编号范围为 [(l - 1) // STACK_SIZE + 1,
        #                               (r - 1) // STACK_SIZE )
        # 即 “左边不包括左边界所在分块，右边不包括右边界所在分块”
        for i in range((l - 1)//self.STACK_SIZE + 1,(r - 1) // self.STACK_SIZE):
            if self.stackMax[i] > ans:
                ans = self.stackMax[i]

        # 处理分块右边的零碎数据
        # 右边的零碎数据范围为 [((r - 1) // STACK_SIZE) * STACK_SIZE,r]
        for i in range(((r - 1)//self.STACK_SIZE)* self.STACK_SIZE,r + 1):
            if self.nums[i] > ans:
                ans = self.nums[i]
        return ans

class Solution:
    def lengthOfLIS(self, nums, k: int) -> int:
        sta = LoveStacks([0] * (max(nums)+5))       # 定义分块
                                      # 注意这里一定要初始化成 0
        for i, val in enumerate(nums):
            j = 1 + sta.maxi(max(val-k,0),val-1)    # 范围查找
            sta.modify(val,j)                       # 单点修改
        return sta.maxi(0,max(nums))

程序简注

2404. 出现最频繁的偶数元素

class Solution:
    def mostFrequentEven(self, nums: List[int]) -> int:
        mp = {}
        maxi = -1
        maxn = 0
        nums.sort()
        for i in nums:
            if i % 2 != 0 : continue
            if not (i in mp):
                mp[i] = 1
            else :
                mp[i] += 1
            if mp[i] > maxn:
                maxn = mp[i]
                maxi = i
        return maxi

2405. 子字符串的最优划分

class Solution:
    def partitionString(self, s: str) -> int:
        mp = set()
        ansi = []
        l = 0
        r = 0
        while(l<len(s)):
            r = l
            mp = set()
            while r < len(s) and s[r] not in mp:
                mp.add(s[r])
                r += 1
            ansi.append(s[l:r])
            l = r
        return len(ansi)

2406. 将区间分为最少组数

class Solution:
    def minGroups(self, intervals: List[List[int]]) -> int:
        intervals.sort()
        lis = [[0]]
        heapify(lis)
        for interval in intervals:
            if interval[0] <= lis[0][0]:
                heappush(lis,[interval[1],interval])
            else:
                pu = lis[0]
                pu[0] = interval[1]
                pu.append(interval)
                heapreplace(lis,pu)
        return len(lis)