经常刷题的朋友都知道，想要通过一道题，实现的算法除了要保证正确性（对极个别题也可以是出错概率极低），还要让复杂度和数据范围能匹配。一般来说总运算量少于7个数量级就能够通过，但也有一些题目，你发现总运算量不足7个数量级，甚至只有6个数量级的代码，提交却总是TLE，即使做一些“歪门邪道”的常数优化（对python有手写max/min，cache_clear，预处理一些内容，给非递归方法加记忆化等），也似乎是杯水车薪。
当然，如果LC也像OJ一样，判定TLE只看单组case，那复杂度合理的做法不可能TLE。但实战中如果出现这种现象，往往是有非常巧妙的做法，你认为被“卡常”的做法，本意就是不期望通过的，因此相比无意义的优化，不如另辟蹊径，看看是不是有重要的性质没有被挖掘出来。
和常用套路盘点贴，Easy题数量严重超标的周赛盘点贴类似，本贴也会持续更新。
正片
这次从一道LCP个人赛的中等题开始。这个题最直观的思路是从终点开始反向BFS，把BFS路过的所有能作为起点的位置都加入答案。复杂度显然和输入成线性，对于不超过1000*1000的网格图，理应通过。但实际上这个做法没有任何通过希望。
这道题的标准解法就是很多人不敢写的纯暴力，即以所有边界点为起点，分别模拟路径。不同的起点如果到达同一点，那此时的方向必定是不同的，而且也不存在进入死循环的问题。每一个坐标与方向的组合(x,y,d)，对应的下一步都唯一，反过来也成立。如果你还是怀疑，可以在草稿纸上画一画，看看能不能画出反例。
这道题也在我的另一个盘点贴。思考这样一个问题：cost最小时，数组元素的最终值一定在原始数组中吗？
如果你的答案是“不一定”，那恭喜你要被卡常卡到比赛结束了。虽然值域只给到10^6，但枚举整个值域想要通过所有case极其困难。
这道题的正解是中位数贪心，因为输入本质就是压缩过的数组，元素的真实总量是sum(cost)。想到这一点，后面就非常容易了。
个人认为这题还是值得Hard，对于n=10^5，n|Σ|^2在LC上本就不应该是合理的复杂度，但很多人真就想各种歪门邪道把这个复杂度的做法硬卡过去（也能理解，竞赛OJ这个复杂度一般能过）……
大思路比较简单，先根据相邻字母的条件把原串切成若干部分，然后对每个部分，用滑动窗口来判断是否有为k,2k,3k...26k的子串满足条件。最容易想到的做法是预处理每个字符前缀和，但这样做总复杂度就是n|Σ|^2。实际这题的本意肯定是希望你借助“频率的频率”来直接判断整个滑动窗口是否有效，而不是每滑一步都枚举26个字母。
数据范围这么小，固定的3*3网格，直接按773题的做法，暴力BFS不就行了？这复杂度应该忽略不计吧？
没错，python语言对于最差的case，也只需要200ms。但是这道题case总数非常多，暴力BFS通过难度很高。而且我几乎确定，case数量就是以卡掉暴力为依据的，只不过双向BFS+好的实现细节，还是有机会捡漏。
这道题的正解是做上帝视角的思维转换。即把“搬出石头”的所有位置及顺序，和“搬入石头”的所有位置及顺序，两两组合求总步数，最小的作为答案。想到这点已经可以轻松通过了，如果能用状态压缩DP代替暴力回溯，速度就能更快。
有些人可能会问，最优解的某一步也可能是从已经是1的格子搬出石头啊？的确是这样，但对于这道题，欲擒故纵不能减少总步数。
这道题难度分能超过2400似乎不可思议，4重循环不现实，但可以2重循环枚举j和k，如果把所有(j,k)的组合对应的k右边比nums[j]小的元素数量和j左边比nums[k]大的元素数量都预先统计好，最终答案就不难求。
但你会发现，这样做的运行时间非常危险。实际上2个哈希表（或二维数组）里有一个是多余的，因为nums已经保证是0到n-1的排列，设cur=nums[k]，则nums[cur]以及相关的预处理结果都是可查的，这样只要预处理其中一个表，另一个就可以算出来。这道题既然给了这样的条件，想必是希望能用上的。
状态压缩DP的大思路不算难想。如果使用记忆化搜索，搜到最后发现出现了“讨厌”的nums[perm[0]]，怎么办？增加一个状态first，表示第一次选的？如果你这么想，那就无法通过这道题了（虽然2^n * n^3对于n=14且常数很小，不太应该TLE）。
应该认真观察一下公式。公式是循环的，一个排列做任意平移，分数都不可能变，而答案要求字典序最小，因此first一定就是0，不需要出现在DP的状态中！
这道题二分的大思路还不算难想，具体验证就是遍历每个工人求t秒最多能搬多少高度，所有工人能搬的高度总和不低于初始山高，那最终答案就不会超过t。看上去求t秒能搬的高度再套一个二分就行，长度1w的数组，带几个log似乎还不至于TLE。
然而非常坑的是，对python语言二分套二分还真就会TLE。那怎么办呢？更快的做法是内层用二次方程求根公式来代替二分猜高度。至于会不会因为开方精度问题而错误取整，还是信任一次py的高精度吧~
没错又是周赛416。题目都说了《线性》，交26n的能不能解释下如果26n不是不期望解法，为什么要出成2道题？
至于为什么除了python都是敢交就过，是不是可以这么理解，python优势场太多了，sortedcontainers导致的逆天优势场也有过好几次，所以必须要来一个让python选手巨难受的卡常场来平衡一下？
正解需要一个哈希表记录滑动窗口与目标串的字母频率的差，显然只有这个表为空时，滑动窗口才是有效的，用判断这个表是否为空，来代替每滑一步遍历所有26个字母，这才能让总复杂度合理。具体实现需要注意的细节较多。
看上去先预处理每种元音和所有辅音的计数前缀和，然后对每一个下标j，二分找能满足各个条件的下标i，取个交集就可以了。
但带log的做法应该都得TLE（至少py是如此），正解是滑动窗口，元音部分必须用变长滑窗+哈希表统计字符种类这一曾经常出在会员题的套路，辅音部分则可以转化成“至少k个”与“至少k+1个”这两个滑动窗口的“差集”。当然，辅音部分也可以通过预处理每次计数发生变化的位置，这样也能直接定位，但空间复杂度就比较高。
刷题多的朋友不难想到状态压缩BFS，但这个做法很难通过全部数据。实际上可以把这个BFS优化成BFS式DP，即visited中去掉能量这个维度，只保留r,c,mask三个维度，同时visited存放每个r,c,mask对应的最优能量值，这就能避免反复横跳无意义消耗能量。
二分猜答案+DP验证确实是相对直观的做法（毕竟最小化最大），但既然XOR没有单调性需要DP，那不如直接把猜答案的“答案”融入进DP里面，状态值不用True和False，而直接把异或值当状态值，这就把二分的外壳拿掉了，也不会被卡常了。
回文数题目不难想到枚举前一半，但如果暴力枚举所有可能的前一半并验证是否满足题意，繁杂的实现会带来巨大常数，即使在所有case外面预处理也很不保险。当然，一个最简单的避免卡常的做法是直接把2666888888886662加到预处理的10^15以内的数之后，这样8位数就完全不用枚举了。这个数字确实没那么显然，需要一定的推理，但相比3题选手，还是宁愿hardcode。这道题高效的枚举方法是先预处理出前一半里可能的数字组合，然后对每个数字组合枚举全排列，这样即使考虑前一半是8位数，运行也很快。这道题还有数位DP与背包DP做法，不过这两个做法都是难度分3开头的级别了，前者实现相当繁杂，后者思维难度超出LC周赛水平。
这题确实非常卡常，但如果想到↑↓↑……和↓↑↓……的数组总数肯定是一样的，那只算一种把答案乘以2，卡常问题就会好很多（毕竟空间省了一半，开内存都要时间的）。如果看DP的公式，会发现这两种的计算方法明显不一样，而如果从只给了数据范围没给具体内容的角度分析，对称性显然成立，每个↑↓↑……数组都能镜像出一个↓↑↓……数组。
如果熟悉题主另一个帖子的套路1.5即二分猜答案解决第k大/第k小问题，很容易条件反射想到二分猜答案+数位DP验证。但这道题用这个做法很难通过，因为你不知道答案的上界是多少，如果对每个case都用2^50做上界，那就是用极端大case的复杂度来跑每个case，以LC平台的总TLE机制100%会TLE。实际上这道题的正解是用组合数学计数来按位确定答案，从高到低枚举每一位，如果当前位填0会导致更低位的组合数总量都不够，那当前位就必须是1。
这道题数据范围允许n^2，但BFS,DP（或记忆化搜索）等n^2的做法不是TLE就是MLE。实际上这道题的正解很简单，就是主站第5题的暴力做法，枚举中心点用背向双指针来找最长串。指针移动的过程中发现两边字符不一样该删哪个？既然你不知道删哪个好，那就两种情况都试一试，题目只允许1次删除，只要删过后续就不能进行任何操作，因此不存在后效性。
番外1
这部分为正解的复杂度较低，但复杂度较极限的做法似乎不是很难通过。
给的数据范围是200，但O(mn * max(m,n))还是很危险，所以我曾经认为（但不符合事实）如果同场第四题难度分有2800+，那这题至少也应该有2700+，因为保险的做法就是用第四题的代码来过第三题。
也有大佬说，这个复杂度的记忆化搜索无法通过，但递推式可以，所以……就是用来证明“记忆化搜索不是万能的”？
O(n^5)的记忆化搜索可以通过，但注意不要2重循环枚举最终差值所在的位置l和r，然后分别从l左边和r右边搜，这样还是会搜到很多垃圾状态。
这道题标准做法的复杂度是O(n^4),可以参考题解区羊神的详细分析。
对于困难版来说n^3本身就是不合理的复杂度，但很多题解照搬简单版的做法，既然这样那为什么出成2道题？
实际上这个题优化并不难，n^3做法需要预处理每一行的最大，次大与第三大所在的列，既然每一行能处理，那前i行或者后j行的最大，次大与第三大也可以预处理，只不过如果这三个值所在的列有重复是无意义的，维护时必须保证这三个数位于不同的列，代码不是很好写。
番外2
如果说因为有更巧妙的思路而卡常是可以理解的行为，为了卡常而卡常那就只能定位为题目“质量很差”了，但这样的题目也不是没有：
这道题如果时间点的取值范围给到10^9，那就只值2000分左右，滑窗+哈希表可解，哈希表统计元素种类在LC里题目不少（只不过很多是会员题，这点的确很不友好）。但实际上时间点的范围是10^6，那看似枚举所有时间点，有查询的就填答案，这就可以了吧？很遗憾，这不可以，这连2/3的case都过不了，还是按标准解法，把logs和查询都排序吧。
当m,q<=10^5，U<=10^6时，m+q+U和mlogm+qlogq哪个更小？这个只能问testcase的设计者了。
涉及回文显然要想到枚举前一半，但无论枚举k进制回文数来判断十进制是否回文，还是枚举十进制数判断k进制是否回文，都是好的代码实现可以通过，效率相对低的实现会TLE。这道题的复杂度无法分析，也没有更好的做法，只能说这是在逼人本地跑代码打表，把打好的表扔上做题页面。
不多说啥了，能被unrate说明LC官方还似乎有救。
正解是AC自动机/后缀数组，DP+哈希如果常数优化做的非常到位，可以极限通过。
如果想把哈希的做法都卡掉，那就多几组超大case，把nlogn和n∑的做法一起卡掉，并且把这道题改成7分（因为z函数面试角度毫无疑问超纲）。如果想让哈希的做法可以过，而把z函数作为“进阶”，那就把数据范围改成10^5，并把这题和第三题换一下（难度标签不用改，字符串哈希这个知识点值得Hard），让大家都轻松过了，也没啥不好的，反正那个子序列的题能撑得起整场周赛难度。现在n∑预处理的MLE，现算的TLE，nlogn极其卡常但也有机会过，作为面试平台真的十分膈应人。
番外3
这道题是适合记忆化搜索的典型，因为递推式比较难确定什么状态不是垃圾状态。从数据范围看不加剪枝的复杂度可以接受，但实际情况是不加剪枝很容易TLE。专业叉人的大佬在交了几十个case，叉了无数代码，当时跑的最快的几乎全军覆没之后，做出警告说“老老实实搜索就好，别做奇奇怪怪的剪枝”。所以……这道题究竟考的是什么？现役官解的剪枝（AB中间插C的情况一律忽略）有无正确性保证？
