训练日志

【本文章同步发表至洛谷】

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 月 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，那就直接无解了，然后又可以发现同层的点的答案是一样的，这就引导我们按层来推公式，然后推出来的式子加一个离线 & 双指针就可以过了，感觉这篇题解写的挺好的。