训练日志
【本文章同步发表至个人博客】
5 月 4 日
早上来改模拟赛，T1 赛时 95pts 实际上不是因为卡常，而是题面描述看错了，真实的 k 应当还要减一，改了结果 cwoi 机子又被卡常了，加了个快读还有一些神秘小优化就卡过了。T2 考试的时候脑子不太好，没想到用树状数组 or 线段树维护，其实是一道简单题。T3 依旧人类智慧，赛时怕超时没开太大，改大了一点就过了。
下午来做专题，这题要在原来直接 DFS 的基础上加一点贪心，具体的是拿二进制数表状态 & 每次优先填可放数少的。
5 月 5 日
今天一天都在写专题。这题 DFS 暴搜就行，但要注意剪枝，最重要的四个点就是 1. 将棍子按长度从大到小排序 2. 如果当前剩余未填长度等于此根棍子的长度且无法填完就直接回溯，因为显然拿剩余的短棍子拼成一个这样的棍子不会更优 3. 如果当这根棍子都无法作为开头拼出第一根，那后面的短棍子也显然是不可以的 4. 预处理然后每次选择直接跳到下一个长度不同的棍子。这题及其加强版依旧 DFS 爆搜，有一个剪枝要注意：我们按按当前 r 计算剩余侧面积加上当前已经确定的面积，如果大于等于目前答案就直接返回，猎奇的一点是加强版里的数据范围比原题大 1，然后就被演了。
5 月 6 日
早上改了昨晚晚练，先用单调队列预处理出从每一个点一步最多能到的最左点 & 最右点，然后倍增扩展（拿线段树维护），最后依次查询就做完了。
下午打 CF，T1 秒了；T2 显然就是按照放一个最大的，然后凑 MEX 就完了，为啥一直不对，换了 114514 种稀奇古怪的排序还是不对；T3 就能换则换，不能换就不行就做完了。赛后发现 T2 我求 MEX 有问题，我的做法只能求递增序列的 MEX，关键赛时想破脑袋都想不到会是这里错了。
5 月 7 日
早上努力学习了一下分块专题中的这题，下午写了然后又调了好久才调出来，结果发现有一次在下放 lazy_tag 的时候在循环中就提前清零了，我在写啥啊，关键这神秘错误还不好找，晕~。做法就是用分块维护每个左端点 j 到当前右端点 i 的恰好出现一次的元素个数，支持区间加、单点赋权值、查询值 ≤k 的权值和，然后再 DP 转移即可。
5 月 8 日
早上来改了昨晚晚练，首先拓扑把每一对找出来是好做的，我赛时也写了，然后赛时一直卡的点就是不知道怎么才能让它优先经过它的另一对，结果一看题解，欸，就是把它另一对的边建到它这里就可以了啊，有道理，我赛时怎么想不到，然后拓扑找最长链就可以了。
下午做专题，这题先搜索前一半的数并存起来，然后再搜索后一半的数，在存起来的数中二分找到加起来满足要求的最大的就可以了。这题及其加强版都是直接 BFS 就可以了，简直是大模拟，敲了一亿年。这题还是遍历图，算是板子。
5 月 9 日
早上改了昨晚晚练，这题其实昨晚已经推了一大部分了，但还差一点，首先要满足条件的话，图中就不能存在长度为 2 的链，所以图中的点要么只有出边，要么只有入边，要么是孤点，要么是两点环（成对出现，互相连边），所以我们预处理出不含两点环的 n 点单图数和全部由两点环组成的 2n 点单图数，然后递推即可。
5 月 11 日
早上改了一道前天比赛的题，这题纯赛时没看，简单 DP。
改了一道上周晚练题，其实一开始没看懂题解都打算把这道题放了的，但后面看好多同学都改出来了，啊这，又回去争了一下。总的做法就是维护一个队列存放当前可被删除的颜色，初始时，若某颜色已连通，则入队，每次取出一个颜色，将其所有城市标记为 0，然后与相邻特殊城市合并连通块，并更新邻域信息，具体一点的就是拿并查集分别维护同色结点的连通块以及标记为 0 的连通块，注意需要启发式合并以降低时间复杂度。
晚上改了晚练，二维树状数组板子，没啥好说的。
5 月 12 日
上午写了一道超级搜索题，反正注意的点就是状态中一定要把人和箱子都放进去才行，然后就是大模拟了。
下午写这题，难点在于把它抽象成图，然后建边，一开始不懂蓝书上说的双端队列 BFS，到头来就只是一个 Dijkstra，只不过 Dijkstra 是用堆优化的，这里由于边权只有 0 或 1，所以可以直接用双端队列代替堆，效率更高。这题依旧直接 BFS，每次有两种选择，要么买 1L 油，要么前往下一站，调了很久的是它的中文题面描述有误，实际城市是从 0 开始编号的，但是题面写的是 1。
5 月 13 日
改了昨晚晚练题，首先将值域离散化，设 dp[i][j] 表示前 i 所学校、第 i 所在区间 j 的方案数，转移时枚举上一个区间更小的学校，拿前缀和 & 预处理组合数就可以过了，但这个卷积推式子什么的，我是真不会。
5 月 14 日
改昨晚晚练题，早上看了好多题解都没看懂，大概是因为自己所想的做法实在有点神秘，后来改了一上午，还是被迫用了题解区的方法。大概就是将每个雨滴和查询起点转化为区间 [l,r] 后按 l 降序、r 升序排序，从后向前用树状数组维护 r 的后缀最大值然后进行 DP 转移。
写专题，这题写了好久了，一直没写对，无奈之下看了眼题解，感觉很不对吧，题目描述的有点不清楚，就人可不可以不走没有说清楚，这就很难办啊，但反正也只是判断的问题，就分别从两个点开始 BFS 就做完了，感觉这题有点屎。
5 月 15 日
改了昨晚晚练，状压 DP，不是特别好想，但知道怎么做了后代码比较好写。做法就是正难则反，用状压 DP 求不满足要求的序列数，设 dp[i][mask] 表示前 i 个数字、状态为 mask 且不符合要求方案数，其中一个二进制数 mask 表示以当前位置结尾的所有连续子段和的存在情况：第 k 位为 1 代表存在和为 k+1 的子段，知道定义后，每次枚举转移就可以了。
5 月 16 日
今天早上重温了一下这题 & 这题，准备去给小六讲，感觉问题不大。
5 月 18 日
改了晚练，先在两端添加半径无穷大的炸弹，设 dp[i] 为前 i 个地雷中第 i 个不引爆的方案数，用单调栈预处理左右最近的引爆者 l[i] & r[i]，转移时用树状数组动态维护满足 j ≥ l[i] 且 i≤r[j] 的 dp[j] 的前缀和即可。
5 月 19 日
补之前因为账号原因没做的题，就归并排序板子，但是我甚至还没写过归并排序。这题，简单贪心，把炸弹归到线段后尽量往右选就完了。
5 月 20 日
改了昨晚晚练，赛时 DP 考虑漏了一些情况，结果年少轻狂没测大样例直接开始优化，最后优化完交的时候才发现大样例都没过。总结做法就是设 dp[i] 为以 i 作为最后一个记录点的最大个数，按 a 值从小到大激活点，用并查集维护在已激活点中步长 ≤D 可达的最左端，每次在线段树上查询该左端前 D 范围内的最大 dp 值转移即可。
这题，做法是每次优先选择平均权值最大的非根块，将其合并到父块中。合并时，将该块所有节点延后父块大小步。重复合并直至整棵树缩为一个根块，输出初始代价加上累计增量即可。
5 月 21 日
这题，很普通的一道队列套队列，只是要注意多测清空，学习了一种方便的清空队列的方式：q=queue<int>()。
改了昨晚晚练，求基环树直径，做法就是先用拓扑排序剥树，度数为 1 的点入队，不断删除叶子，过程中自底向上维护 d[u]（子树的最大深度）和 f[u]（子树内的最大直径）。然后剩余度数为 2 的点构成环，遍历找出环上的点及统计出边权。破环成链后，用单调队列在长度不超过环长的滑动窗口内计算 max(v[i]+v[j]+sum[j]−sum[i])，其中 v[i] 为环上点的 d 值，sum 为边权前缀和，最后答案就是累加每一棵基环树内不经过环的最大距离和经过环的最大距离的最大值。
这题，拿一个小根堆维护要选的商品的价值，将所有商品按过期时间排序后，贪心考虑如果当前过期时间等于目前已选的数量且堆顶小于当前商品的价值，则替换入堆。如果当前过期时间大于目前已选的数量，则直接入堆即可。
这题，KMP 板子，但脑子表示不想再重温 KMP 了，毕竟之前为了搞懂这个大战了一个下午，直接找到了之前的板子敲了一遍。
5 月 22 日
改了昨晚晚练，由于后加入的人肯定只与前面的人相连，所以我们可以倒序 DP，根据加入方式将当前人的贡献合并到其主持人上，动态维护选与不选的相对价值即可。
改了 CF 的 T2，难评，对每个数取前缀最大值与当前值的差的最大值，尝试可否满足要求就没了。T3，尝试最小值可能到达的数值作为最终的数，取最小值输出就做完了。
继续补之前漏的题，这题，把每一层剥出来后，就是单调栈做最大的矩形纸片了。这题，字符串前缀就在容易想到字典树，建树后每次看当前这个字符串是否会经过之前字符串的结尾，以及当前字符串在建树过程中是否需要添加新的点，不需要就说明当前这个字符串是之前某个字符串的前缀。
5 月 26 日
改了前晚晚练，这题怎么说呢，首先你得发现一个性质，就是这个答案只与字符串中的 110 & 101 有关，当有 110 的时候，答案即为总长度减去出现 110 的位置再减一；否则，存在 101 的话，答案就为 1；否则，答案就为 0。所以现在就只需要拿一个线段树统计这一段的长度、前两位和后两位、是否出现 110 或者 101 以及出现的位置，由于有取反操作，所以还需要一个取反的懒惰标记。
5 月 27 日
改了昨晚晚练，定义 dp[i] 表示前 i 条边必须选 i 的最多边数，f[i] 表示方案数。维护维护前 i 步路径中最后出现 A 和 B 的位置，转移就从这两个位置中最小的位置之前转移而来，如果选不选 i 对边数没有影响，那方案数就相加，否则就继承转移点的方案数。
终于是继续做了专题，这题就 A 算法的板子，个人理解就是和平常的算法排序方式不同，这是用估计的最终值排序，所以会比平时用目前的值排序效率更高，有个剪枝是当一个点弹出大于 k 次后就可以直接忽略不管这个点了。这题个人感觉状态数不大，所以就没有优化 BFS，结果一下就创过了，那好吧。这题叫什么 IDA 算法，个人理解也就是 DFS 上的按估计结果剪枝，这个的估计其实不太好想，看了蓝书才知道实际上一次移动最多解决 3 个断点，所以就估计断点数除以 3 向上取整就可以通过了。
5 月 28 日
改了晚练，首先将物品按重量排序后，利用相邻重量差与 D 的关系把序列划分成连通段，并在奇数长度的段中贪心选择一个满足奇偶性或连通性条件的物品单独运输，然后将所有询问按 D 离线排序，用并查集维护段长、段内节省和以及两类可牺牲物品的最小节省值，随着 D 的增大合并连通段并激活内部可牺牲物品，动态更新全局最大节省就做完了。
6 月 12 日
改了昨晚晚练，首先利用所有质量两两整除的性质，从小到大逐层处理，每层用当前最轻且价值最高的物品填满容量除以次轻质量所得余数的零头，再将剩余物品按重量累加打包成次轻质量的新物品，以此类推就做完了。
继续专题，这题思路很简单，但代码实现可不好写啊，就每次直接枚举用哪一种方式，加上 IDA 的做法，其中估价函数就是 8 减去中间最多出现的数，然后有一个剪枝是每次不进行上一次的逆操作。这题，一道 BFS 板子，只是注意一下需要交换 n & m。
6 月 15 日
依旧专题，这题按照低位往高位搜索，然后有一个剪枝就是如果当前位数既不能满足没有进位的情况也不能满足有进位的情况就直接回溯，思路倒比较简单，但代码不是特别好实现。
6 月 17 日
改了不知道多久的晚练，期望 DP，先 DP 求出从起点出发恰好走 t 步到达每个点 v 的概率 f[t][v]，然后再枚举每一次可能的转移，在时刻 t 从 v 走到 u 的贡献期望就为 f[t][v]/m[v]*u 再乘上从 u 出发在剩余 T−t−1 步内至少一次回到 v 的概率（依旧 DP），最后累加答案就做完了。
6 月 21 日
改了昨晚晚练，做法就是将操作转为随机排列，依次考虑点，若其所在连通块大小 >k 则删边。对于每个联通子图，求出其恰作为一个完整连通块出现的概率，树形 DP 统计以每个点为根、大小为 i、非父亲外部边数为 j 的连通块个数，最后统计答案就可以了。
改了模拟赛 T3，思路就是选取攻击力最大的生物，若其能击败所有其他生物，则答案为其无法直接击败的生物数，否则判断那些无法被它直接击败的生物的最大攻击力能否直接击败它，若不能则检查可被它击败的生物的区间能否覆盖这个最大攻击力到它的防御力的范围，能则存活数为该数，否则加一，具体的采用用离散化 + 树状数组（维护各防御力值上的生物数量）+ 两棵线段树（一个维护区间最大值，另一个维护区间覆盖）。
改了今晚晚练，呃，赛时没有想到可以先排序再去做，反正排完序后要选的绝对是一段，只需要拿一个 set 存区间，外面套一个双指针就做完了。
6 月 22 日
改了模拟赛 T1，赛时没推出公式啊，反正就随便统计一下 U&D 的数量就做完了，个人不太喜欢这种题。T2，赛时没仔细看，原来就是一个小清新线段树，每个节点分别存该区间会从前面删除多少辆车、该区间内部净增加的车数（自己入栈且未被自己后面的删除吃掉的部分）、该区间内部净增加车辆的价值总和、左儿子区间在被右儿子区间删除了 右 cut 辆车后，左儿子内部剩余车辆的价值和，然后动态维护就可以了。
6 月 23 日
改了昨晚晚练，赛时一直在调自己的假贪心，完全没想树形 DP，呃，分别定义为这个点被炸了、这个点还剩一个儿子、还剩两个儿子，转移不太难，稍微推一下就可以了。
改了不知道多久的晚练，首先有一个判无解的东西，如果某层中存在两点的距离大于 k，那就直接无解了，然后又可以发现同层的点的答案是一样的，这就引导我们按层来推公式，然后推出来的式子加一个离线 & 双指针就可以过了，感觉这篇题解写的挺好的。
6 月 24 日
改了昨晚晚练，额，期望 DP，设 dp[i][j] 表示第一个数值在 i，第二个数值在 j 时，i 追到 j，i 所用的期望步数，然后稍微推一推转移就可以了，感觉最主要的还是要发现 i 的期望步数只与 i+1 有关。
下午写了几道概率与期望的例题，感觉 C 老的讲稿已经很详细了，自己也没有什么多的心得体会就不写总结了。
6 月 29 日
改了昨晚晚练，和我自己的想法是一样的，就是对于一个点如果它最短的两条获胜边长度减一小于等于 k，那这个点就可以获胜了，树形 DP 一下就做完了。
改了古早晚练，比较困难的 DP，即设 f[i][j][k] 为将前 i 头 H 牛和前 j 头 G 牛匹配，最后一头失配的奶牛种类为 k，所得的最大失配重量和。然后预处理出 g[i][j]：从第 i 头 H 牛和第 j 头 G 牛开始能连续匹配的最多对数；nxtb[i]：第 i 头 H 牛右侧第一个不能与之匹配的 G 牛的下标；nxta[j]：第 j 头 G 牛右侧第一个不能与之匹配的 H 牛的下标。然后转移分为改变种类和不改变种类两种。对于 T=1 的情况直接将权值取反 & 答案取反即可。
6 月 30 日
改了昨晚晚练，总的来说外层就是一个拓扑排序，然后具体的又分为了如何判断此点现在的入度为 0，判断是否存在一条 u->v 的边，有一个优化的点就是你可以二分找是否存在一条 u-> 集合的边，然后就过了，代码好写但不好调。
7 月 1 日
改了昨晚晚练，就是超级大分讨 & 计数，后面 k=n+m 的情况不知道算重了的情况该怎么做然后就被卡死了，具体的推导可以参考这篇题解。
改了不知道多久的晚练，首先观察到如果一种方案合法，那反过来也一定合法，而且这两种方案的贡献总数应当是 m，所以我们就只需要求方案数，显然最终的图是可以分成一层一层的，我们就状压 DP 设 dp[state] 为定向点集 state 内的边使得 state 为 DAG 的方案数，然后枚举零度点点集，对于去重这一步采用容斥就可以了。
写了一道期望的题目，设 dp[i][j][k] 前 i 个教室，换了 j 次位置，第 i 个教室有没有换的期望，然后转移也很简单，主要是想出是 DP & 状态设计。
晚练居然被我场切了，首先读题想了一下建图 & 最短路，感觉复杂度不对，又感觉 DP 一下就很可能过吧，写完测了大样例发现跑了 5s，个人认为这不是常数大的问题，然后灵机一动发现可以预处理 DP ，然后就过了。具体的做法就是将可以快速跳转的点离散化，然后从每个点跑一遍 DP，向前转移即可，查询只需要找到两点的对应的相邻端点即可。
7 月 2 日
依旧写了一道期望的题目，一开始题面有歧义害我想了好久。做法就是期望 DP，设 dp[i][j] 表示从 i 出发抓到 j 所需要的期望步数，转移时需要提前预处理出它两点之间的最短路以及下一步要走到哪里去（BFS），然后转移采用记忆化搜索就做完了。
7 月 6 日
晚练是这题，首先可以二分答案，接下来考虑怎么 check，我们可以直接求出每个点必须要在多久以前种下树才行，然后贪心的从要求种下时间最早的点开始，每次要种到这棵树一定是从当前点向根节点不停跳的，然后依次判断就做完了。
7 月 8 日
改了一下午的这题，首先我们要预处理出每个点到其子树内点的最短路，这点很重要，只能算其子树内的点，不然就会 TLE & MLE（实现需要用到 DFS 序），然后对于每个点我们分别考虑其子树内的点和子树外的点，内部的点显然是一直往上跳最优，外部的点均可转化为先跳到 LCA，再通过一条最短路到达，实现就是一直从 u 向上跳其父节点即可。
改了今晚晚练，首先观察到每长出一个叶子，就会减少一个连接位置，再增加两个连接位置，所以当树的大小为 x 时，就有 x+1 个连接位置。然后我们考虑每一条路径的贡献，设 u 的子树大小为 sz[u]，显然 u->fa[u] 这条边的贡献就为 sz[u]*(n-sz[u])，所以我们实际上只需要求出求出所有情况下子树大小分别为 1-n 的点的数量即可。具体的，我们设 f[i][j] 表示树的大小为 i 时，子树大小为 k 的点的数量，转移就要么是接到一个子树大小为 k-1 的上面，要么接到外面。需要注意的一点是新加一个节点需要单独考虑，方案数为当前树的大小的阶乘。
7 月 13 日
改了模拟赛的T3，这个题赛时只有 111 型考虑错了，我们将每两个相邻 0 中 1 的个数存下来，要求经过操作使得其中所有数小于 2，每次操作实际上就是将其中两个数变为 x+k 以及 x-k，所以优先换 k 为 2 的即可。
改了模拟赛T4，首先设 f[i][j][0] 表示在前 i 张强化牌中选择 j 张且第 i 张被选中的所有情况下，这 j 张牌的乘积之和，g[i][j][0] 表示在前 i 张攻击牌中选择 j 张且第 i 张被选中的所有情况下，这j张牌的和之和。再分别记录下其前缀和为对应 f[i][j][1] & g[i][j][1]。对于统计答案，当 m 张牌中，强化牌的数量小于 k−1 张时，此时必然是选上所有的强化牌，然后选上权值最大的一些攻击牌，此时枚举 i & j 分别表示强化牌有 i 张和最后被选中的攻击牌是第 j 张即可；当 m 张强化牌中，强化牌的数量大于等于 k−1 时，此时必然是选上权值最大的 k−1 张强化牌，然后选上权值最大的一张攻击牌，枚举 i & j 分别表示最后被选中的强化牌是第 i 张和被选中的攻击牌是第 j 张即可。
7 月 14 日
改了这题，想到是搜索却不知道该如何下手的来着，其实只需要关注这一个重叠点，看它能不能上下左右移，具体的就是看两边的符合条件的起点有没有交集，预处理出每个点上下左右的没障碍物的最远距离即可。
7 月 15 日
改了这题，要保证一段数列为等差数列的话，实际上只需要满足以下三个条件，第一个即为首项和末项的差为 k 的区间长度倍数，第二个条件为相邻两数差的公共 gcd 为 k 的倍数，最后再满足区间内没有重复出现的数就可以了。具体的实现我们可以拿线段树维护区间最大值，最小值，公共 gcd，前驱最大值（判是否有重复出现的数字），至于前驱的维护可以拿一个 set，然后就做完了。需要注意的一点是 k=0 的情况需要特殊讨论一下。
写了一下可持久化线段树，这题求第 k 小，我们可以用 rt[i] 维护前缀 [1,i] 的权值线段树，区间 [l,r] 就通过 rt[r] 与 rt[l-1] 相减得到，然后这样找就可以了。
写了这题，其实想出 DP 状态后转移是简单的，设 dp[x][i][0/1][0/1] 表示以 x 为根的子树中共放了 i 个监听装置，其中 x 点放没放装置，x 点有没有被监听到的方案数，直接做就可以了，时间复杂度其实是对的，只是代码比较难写的来着。
预习了一下明天的题，其实是不想写今天的题了，这题暴力判断每个字符串就可以了，建出来 Trie 树后把每一条边转化为字母的边存下来跑一个拓扑看有没有环就可以了，至于长度比较问题，实际上就是看有没有字符串是当前串的前缀，有的话就直接返回 false 就可以了。
7 月 16 日
先是想起来去写了一下 DFS 序 +ST 表求 LCA，结论就是 u & v 的 LCA 等于 DFS 序上位置在 [dfn[u]+1,dfn[v]] 的深度最小的任意结点的父亲，画个图也就很好理解了，需要注意的一点是相同要特判一下。
然后看了一下今天的串串，发现后面的题都是自动机一块的，我都没学过，就暂时先放了，这题似乎更优解是后缀数组，但是我不太会，而且这个数据范围建 Trie 树暴力也能过，然后就过了。
往后看了看这题，DP 是简单的，设 dp[i][j][0/1] 表示表示在第 i 个小时，已经休息了 j 个小时，0 表示这个小时没在休息，1 表示这个小时正在休息。然后主要是考虑中间有一个相连的点，做法就是直接钦定这个点要选，然后再 DP 一遍和刚刚的答案取最大值即可。
这题，首先可以破环成链，然后就把绝对值函数给拆掉了，简单推推式子发现可以用单调队列维护，然后就做完了。
这题，其实还是比较简单的一个博弈论，就建完 trie 树后直接从 DFS 从下往上传答案就可以了，注意局数对答案的影响即可。
这题，就是板子而已了，KMP+LCA 就做完了，正好试用了一下今天早上的黑科技。
7 月 17 日
这题，直接做是困难的，我们可以考虑每一条边的贡献，树形 DP 转移就可以了，具体一条边我们考虑它的子树选几个黑点，我们就可以知道它的贡献了，简单推一推就可以了。
这题，首先观察到每次公布的队伍都会成为当前第一名，因此公布顺序的逆序就是最终排名，所以我们就将题目转化为有多少种公布队伍的排列，使得总新增题数不超过 m。我们直接记录每支队伍的新增题数是不可行的，但我们可以利用差分来优化 DP，注意到若当前已经公布了 s 支队伍，那么这次增加的 delta 对总数的影响就为 delta*(n-s)，现在我们就可以 DP 了，设 dp[S][i][j] 表示在当前已经公布的队伍集合为 S 的情况下最后公布的队伍为 i，当前消耗的总题数为 j 的方案数。对于每一个集合，枚举 i 和下一个选择的点转移即可。
晚上挑战了一下这题，这个大分讨 DP 黑降紫还是有点说法的，其实最后是 AI 帮忙调出来的来着。做法就是先将数组排序后进行 DP，设 dp[i][j][k][s] 表示已经加入前 i 个最小的数，当前有 j 个连续段，当前代价为 k，确定了 s 个端点。对于每段的新增贡献就为 (2*j-m)*(a[i+1]-a[i]) ，转移分为 5 种大情况：
- 新建一个不包含端点的连续块；
- 建一个包含端点的连续块；
- 接到已有的连续块但不形成排列端点；
- 接到已有连续块且形成排列端点；
- 连接两个连续块。
分别大力讨论就做完了。
7 月 18 日
早上来先把这题做了，就插入性 DP 的板子。
这题，还是一道简单的滑动窗口，不同的是这道题需要维护两个单调队列，一个表示最大值，一个表示最小值。这道题也可以二分 +ST 表做。
这题，首先容易想到一个朴素的 DP，定义 f[i] 表示飞到 i 的最小劳累值，可以从 i-k 到 i-1 转移而来，然后显然这个东西就可以用单调队列优化一波，然后就做完了。
这题，单调栈维护当前序列的后缀最大最小值，在加一个二分查找就做完了。
7 月 20 日
模拟赛 T1，离散化后直接维护一段区间的前缀 & 后缀就可以了，每次只需要考虑端点及端点加减长度即可。T2，一个唐唐树上问题，把每条边的贡献拆开 & 统计当前已处理颜色的点数即可。
这题和这题，最短路 + 二分板子。
7 月 21 日
这题，直接分层向下建图跑最短路即可，每向下走一层就相当于做了一次免费的飞机。有一个需要注意的点是，如果不用 k 次就到达了终点的话，我们的答案会出问题，所以我们可以对每层的终点向下一层终点连一条零边。
这题，差分约束的板子，其实就是转化为最短路，但是有负边权，所以只能用 spfa，注意入队次数大于 n 即存在负环，直接无解。
这题，能想到转化为最短路都很牛吧，注意到我们枚举数字可以看成是在个位加一以及乘十组成的，前者的数位和贡献为 1，后者为 0，我们只需要在模 k 意义下跑最短路即可，由于贡献只有 0 & 1，所以可以直接维护一个 deque 跑 01 BFS，注意特判 1。
这题 & 这题，矩阵快速幂板子吧，后者那么大的矩阵，出题人纯猎奇吧。
这题，首先可以发现如果所有边的长度都是 1，那邻接矩阵的 t 次方就能算路径数。我们想把一个长度为 w 的边，拆成 w 条长度为 1 的边，这样就能用的矩阵幂方法做了，具体的就把一个点拆出 9 个点并将长度设为 1 即可，然后矩阵快速幂跑 t 次方就做完了。
7 月 22 日
这题，高斯消元板子，其实感觉高斯消元也没有那么难。
这题，尝试用 Floyd 求最短路的方式，把矩阵乘中的乘定义为 min，然后跑 n 次快速幂即可。
这题，求逆元而已，也算是板子，这题，神秘 gcd。
7 月 23 日
这题 & 这题 & 这题 & 这题 & 这题都是树剖的板子，线段树稍微改变一下维护的东西就做完了。
这题，显然会有很多重复计数的约数，我们把它们合并到一起计算，然后使用类似前缀和的方式就可以解决了。
7 月 24 日
这题，首先看题就知道一定是跑边双，然后想要图中每个点都有两条边且代价最小，我们可以将缩完点后的叶子结点每两个连一条边，所以答案就是叶子结点数量除以二向上取整了。
这题，缩完边双，然后求树上距离就完了，搞一个 LCA 就做完了。
这题，首先建反图，从终点跑一遍 Tarjan，然后在原图中按拓扑 DP 即可，需要注意有环显然就是极大值了，代码比较难调，最后输出时需要把终点排除在外。
7 月 27 日
这题，这题，扩展欧几里得板子，只是需要注意有负数要自己写一个向上 & 向下取整。
这题，依旧模板。
7 月 28 日
这题，所要求的概率可以用相同的除以总方案数得到，相同的方案数可以通过维护区间内颜色 i 出现的次数来得到，然后一个分块板子就完了。
这题，难点在于如何不统计重复，可以考虑从度数小的边连向度数大的边，如果度数相同则用编号小的指向编号大的，这样定向后注意到每个点的出边是小于根号 2m 的，然后就可以暴力枚举通过了。
这题，上课的时候有同学分享了一个神秘的做法，可以直接按大小排序后依次遍历判断是否在给定区间内，然后这样居然还真的过了，只是优化了一下储存。
这题，将每一次区间查询用一个前缀异或数组和 cnt 数组，cnt[x] 表示当前区间内前缀异或值等于 x 的下标个数，然后套个莫队就可以了。
7 月 30 日
这题，拆个段然后一个快速幂就做完了。
这题，首先可以做一个完全背包，求出不管要求凑出 s 的方案数记为 dp[s]，然后接下来用一个容斥，计算某一个交集的方案数可以用总数减去它们所用超的数量，剩下的就可以自行组合了，然后过程可以采用枚举二进制位，会更加好写一点。
这题，三重容斥，设枚举强制让 i 行全空、j 列全空、k 种颜色不出现，这时剩余可染色格子 (n−i)(m−j) 个，每格有 c−k+1 种选择（不染），然后合并预处理一下就可以了。