前言
2024年的周赛总体难度相比2023年稍高，综合质量也相当高，极端手速场非常少，对标OJ的思维题却不少，也许是为了防止GPT用户轻松AK的不得已而为之，但题主更愿意相信这个年代越来越卷，hot100的水平至少已经无法保证机试不会0分了~
本贴的内容和一年前的帖子类似，盘点2024年出的所有题目里知识点超纲，思维难度高或者个人认为有趣的题目~
正片之前先给朋友们看一看“万恶之源”：
3219.切蛋糕的最小总开销2 （难度分1789）
这道题新手猜个做法就能过，甚至截图丢给GPT都能过，但正确性证明并不简单。常见的思考方向是交换论证，但如何证明“每次都是对所有的蛋糕切同一刀”，看上去总是跳不出循环论证。可以把切蛋糕的过程反过来，看成 1 * 1 的小蛋糕合并成 m * n 的大蛋糕，这样就把题目转化成最小生成树，就有正确性保证了。详情可以参考灵神题解~
很多朋友认为正是造就美国站8000+AK的这道题，让周赛不得不重视GPT，于是彻底走向OJ化之路~
上篇：超模怪（20个）
数据结构
3245.交替组3 （难度分3112，超纲）
这道题难度分吃了知识点超纲+代码量大+同场第三题不白给（提前剧透，下篇里有）的多重buff，必须会树状数组才有救。环形相比非环形，细节也多了很多，由于后缀和前缀拼成的交替组的存在，修改j之后更新j前面与j后面的交替组终点时，就必须考虑跨过n-1和0这个分界。
3161.物块放置查询 （难度分2513，正解超纲）
3165.不包含相邻元素的子序列的最大和 （难度分2697，超纲）
这两个来自同一周的2场周赛，都是涉及单点修改和区间查询，最合适的数据结构是线段树。半夜那个sqrt分块还算有救，但实现细节极多，贡献成吨WA很正常。白天那个是打家劫舍问题，sqrt分块卡常严重，即使实现的比较好，也差三四个超大case才能过，还是老老实实上数据结构吧~
3072.将元素分配到两个数组中2 （难度分2052，多数语言超纲）
正解是树状数组，如果学过的话，应该算比较“板子”？ 当然如果用py，那就是个Easy题。
3187.数组中的峰值 （难度分2154，多数语言超纲）
情况基本同楼上。
3382.用点构造面积最大的矩形2 （难度分2722，超纲+思维难度较高）
这道题思维难度不低，可考虑枚举每个点p作为左下角，题目要求边界不能有多余点，那左上角只能是p正上方第一个点，右下角只能是p正右方第一个点，然后再看看右上角是否存在，如果存在就需要检查这4个点围成的矩形内有无其他点，这是二维偏序问题，需要树状数组来解决。周赛里想必很多人很头疼，简单版的暴力做法实现繁杂，需要额外消耗大量时间，冒2题选手的风险去梭哈困难版需要很大魄力~
动态规划
3225.网格图操作后的最大分数 （难度分3027，思维难度高）
二维网格DP并不见得都是送分题，这道题想要避免夹在两列中间的部分被重复计算，需要通过观察和思考，想到最优方案一定是一个或多个山形，设计状态时不仅要考虑j-1列填了多少，还要考虑当前列在上升还是下降段，这可以用j-1和j-2填的部分的大小关系来表示。
3003.执行操作后的最大分割数量 （难度分3039）
常规解法前后缀分解思路和实现细节都很变态，实际上还有个实现非常简单的状态压缩+记忆化搜索做法。这个做法看上去复杂度至少有2^26级别，很容易认为极不靠谱而直接放弃。但如果认真思考，可以发现字符集的状态并不是任意的，总状态数是n * 26^2，而不是指数级别。
3130.找出所有稳定的二进制数组2 （难度分2824，思维难度高）
朴素的DP复杂度为mn(m+n)，部分语言可能连同场第三题都很难通过。不妨从不合法的状态入手，必然是连续填相同数超出限制，因此将最后一位是0或1加入状态，那不合法状态就容易定位了，所有状态减去不合法状态就是当前状态的DP值。
3389.使字符频率相等的最少操作次数 （难度分2940，思维难度高）
“相等”看起来很棘手，可以转化为“出现k次”并枚举k，对于每个k在字符频率表上DP，只考虑单独操作和跟上一个字母一起操作这2种情况即可，因为和差2以上的字母操作不会得到更优解。
3348.最小可整除数位乘积2 （难度分3101）
题主打了三年多周赛的最高光，这题可以看成需要输出方案的数位DP，但注意这道题的islimit状态应该定义为“下限”而不是“上限”，最大的难点在于DP可能无解，可以通过补前导0来解决（实现极其易错），也可在这种情况下贪心构造答案。
二分查找
3049.标记所有下标的最早秒数2 (难度分3111，思维难度极高)
这道题有2个大思路，一是将清零操作对应的时刻排序后做为状态进行DP，二是二分猜答案，后者相对易于理解，因此归入二分区。答案有单调性很容易发现，但验证方法极其难想。无论正序还是逆序遍历所有时刻，似乎都找不到清零操作的合适时机。正确的验证方法是逆序遍历时刻，实时维护能用于减1和标记的时刻数，并根据当前时刻是否是某个位置的首次清零机会，使用带反悔的贪心策略。
3145.大数组元素的乘积 （难度分2859，实现难度高）
大思路并不算难想，先用二分猜答案的思想找到区间内的最小和最大数，然后通过位运算，把区间内所有数的每个二进制位，转化成对应答案的2的幂次。但区间两端不完整的数会让这道题实现极其复杂，比赛时间内调通确实是个很具挑战性的任务。还有数位DP做法，码量就更大了~
3357.最小化相邻元素的最大差值 （难度分3077，思维难度高）
最小化最大不难想到二分猜答案，但这题的验证方法并不显然，首先要想到连续的-1多于2个可以直接看成2个，再根据-1左边最小正常元素的min和-1右边的最大正常元素来确定2个填充变量的合理取值，当连续2个-1要填入2个不同元素时要注意他们的差，而边界位置的-1也需要特别留意。
数学
有请LC主站镇站之宝，圆和矩形！！
3235.判断矩形的两个角落是否可达 （难度分3773，思维难度极高）
也许对刷题多的朋友而言，“正难则反”是很常见的思路，从和圆有交点的路径考虑，不难想到并查集。但是……如果出现2个或更多圆在矩形的外部把上边界和右边界连起来，但矩形内部有路可走，这么做会出问题吧？比赛期间官方也没想到可能这样，标程也是错的。很多人认为肯定会改题，不允许圆心在矩形外。但官方竟然丧心病狂地增加了这样的case并rejudge，导致全站只有3人存活（实际上这3人的代码有精度问题，官方再狠一点可以无人生还）！想要解决这个问题似乎需要求任意两圆的交点，不在矩形内时不合并，但更好的做法是圆心连线按比例取点来代替相交区域。这么做的正确性依赖于相交区域部分在圆内时，是否合并不影响答案，这点难想也难证明，即使比赛期间有合理的标程和corner case，难度分也极大概率top1。
3337.字符串转换后的长度2（难度分2411，超纲）
线性代数也是数学（手动滑稽），那这题就扔数学里了~ 矩阵快速幂的实现其实就是矩阵乘法+快速幂，但作为求职向的刷题平台，出这东西真的好吗……
3405.统计恰好有相等相邻元素的数组数目 （clist难度分2241，多数语言超纲）
本质是组合数问题，n-1个下标里任选k个让他们和左边位置相同，py选手一行秒杀，其他语言就需要预处理阶乘及其逆元。
字符串匹配
3213.最小代价构造字符串 （clist难度分2923，超纲）
今年的究极事故场，比赛期间放过了DP+字典树的做法（复杂度为n^2，显然不合理），但设计了非常多的针对复杂度更低的DP+哈希做法的case，只得作废处理。words的总长度为m，那不同长度的种类就是O(sqrtm)级别，可以枚举每个合理的长度，并检索该长度是否存在目标哈希值来让复杂度相对合理。当然，这个做法也几乎没有通过的可能，那就只能用后缀数组或AC自动机这样竞赛级别的知识点了~
位运算
3181.执行操作可获得的最大总奖励2 （难度分2688，超纲）
主站首个正解就是压位（C++用bitset，py用大整数来位运算）的题目。看看专业叉人的大佬两年前说的啥（截图自主站2301题的题解）：
3022.给定操作次数内使剩余元素的或值最小 （难度分2917，思维难度高）
位运算题目往往能通过拆位解决，但这道题总感觉每一位的最优操作完全不同，如果拆位去做，处理低位时高位就会被彻底破坏，然后就没思路了。实际上处理低位时，只要把已经处理好的高位带上就不会出现这个问题，实现时注意如果某位不可行，mask一定要还原。
下篇：有趣的思维题 （9个）
3116.单面值组合的第K小金额 （难度分2387）
并不是只要枚举所有子集的题就是Easy，这道题是LC首次出现枚举子集和容斥原理有机结合，N数容斥很多人此前并没有接触过，不过可以用三数容斥的公式来大胆类推~
3377.使两个整数相等的数位操作 （难度分2186）
埃氏筛+dijkstra，这技能组合怎么看怎么抽象，但只有你想不到，没有LC做不到~ 实际上“素数”这个限制就是为了避免你贪心求解的，一定要想到转化成图模型来求最短路~
3363.最多可收集的水果数目 （难度分2404）
这道题可以很难也可以很简单，一定要认真审题，第一个小朋友的路线是唯一的，而后两个小朋友的路线不会交叉，想到这点，那就是白送的二维网格DP了~
3277.查询子数组的最大异或值 （难度分2692）
不得不佩服设计者，误导性可以说相当强。看到题目和示例，想必很多人会举几个较小的例子看最后剩下哪些元素，然后就去想着找和子数组长度的二进制表示有关的规律，其实算较短的子数组的过程里正确的状态转移公式已经明显了，但这时候思路往往已经被彻底带歪了……
3244.新增道路查询后的最短距离2 （难度分2270）
“简单版”的代码拿到“困难版”会TLE，这很正常，那如果“困难版”的代码拿到“简单版”会WA呢？实际这并不是“困难版”，也不需要BFS，注意审题，任何时候任意两条捷径不会交叉，既然这样，那当前点有捷径当然就要走了~
3260.找出最大的N位K回文数（难度分2370）
这道题的正解当然是DP，但由于K的范围太小，比赛里就自然会出现“歪门邪道”，比如 《 史 山 解 法 》
3139.使数组中所有元素相等的最小开销 （难度分2666）
2600+并不等于Hard，想必除了题主这样的菜鸟外，没人甘心交一个非常笨的暴力枚举最终值的做法吧~ 如果最终值就是原数组的max，很容易直接算出操作次数。但如果原数组是大家都差不多，只有一个明显掉队的形式，同时操作2个数却比操作1个数还便宜，那么可否让最终值大一些，从而大家都能陪着min做操作2呢本题可以暴力，二分或者数学方法直接拿到最优最终值，二分做法值得2600+，而数学做法恐怕放在CF也是至少2D的水准了
3149.找出分数最低的排列 （难度分2641）
状压DP的大思路比较明显，用记忆化搜索实现也问题不大，但搜到最后发现了讨厌的perm[0]，难道需要额外加状态，然后被卡常？实际上你把序列做任意平移，然后再带回得分公式，会发现完全一样！那题目要求字典序最小，perm[0]自然就等于0了~
最后请出镇站之宝同场第三题，全站唯一难度分2500+的Medium！
3234.统计1显著的字符串的数量 （难度分2556）
看上去无法优化，但注意只要0的数量达到了sqrtn，那再长的子串都不可能满足题意，因此内循环不枚举所有的可能终点，而是枚举子串里最后一个0的位置，然后计算以这个0为终点的合法子串总数，这样总复杂度就合理了~
