训练日志
【本文章同步发表至个人博客】
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 的方案数，转移时枚举上一个区间更小的学校，拿前缀和 & 预处理组合数就可以过了，但这个卷积推式子什么的，我是真不会。