专栏文章
11.10 ~ 11.16
个人记录参与者 1已保存评论 0
文章操作
快速查看文章及其快照的属性，并进行相关操作。
- 当前评论
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @min6lawr
- 此快照首次捕获于
- 2025/12/01 21:24 3 个月前
- 此快照最后确认于
- 2025/12/01 21:24 3 个月前
11.10 ~ 11.17 集训记录
11.10 限时训练
T1
P10206 [JOI 2024 Final] 建设工程 2 / Construction Project 2 - 洛谷考虑新的最短路一定是 , 于是考虑正反两遍最短路，枚举每个点之后拼起来即可，要注意最开始就合法要单独计算。
T2
考虑实际上是对于一段 的前缀和要 ，于是线段树维护前缀和，每次变化后缀修改即可。
T3
发现对于配对的 ,他们之间最多拿上一张牌，否则 就会被扔掉，因此设 表示以 结尾，强制 配对的最大贡献，那么转移分为中间有没有牌，线段树维护一下即可。
实现上还有个小细节，对于区间取 ，询问区间最大值，可以少维护一个 tag，递归修改为循环查询即可。
T4
考虑倒着做，每次就是钦定两个位置相邻，直接维护 表示 位于时刻 的哪个点的位置，每次交换并连边，如果出现点度数 即不合法，环也不合法，否则直接字典序最小输出链即可。
lca NOIP
T1
考虑可以删掉一段长度为奇数的区间，于是分奇数偶数分别维护最优决策即可。
T2
连续段 dp 好题，首先发现最后中间是一段区间，然后把空白位置插进去即可，于是考虑对长度为 的方案计数，如何做呢？
从小到大插入，设 表示插入了 个，分成 段，花费了 的空间，共有三种转移：
- 新开一段
- 合并两段
- 接在一段后
最终答案就是 。
T3
比较简单，难点在于复杂度分析，树形 dp 维护子树内同色节点数量，注意树形 dp 转移上下界优化到平方即可。
11.11 模拟赛
T1
最开始以为是 ABC 的 F 题，容易想到一个贪心，维护一个 set，每次找到最大合法的删掉，但是会发现大样例 #1 就寄了，问题在于可能会取到一些过大的值，这些值可以作为后续新的段的起点。
如何解决呢？我们考虑二分答案，接下来问题在于如何 check，我们考虑先把每一组第 个元素全部填完，再填第 个元素，这样类似一行一行填，当一个数在当前不能被匹配，则在所有当前可以接上的位置都无法匹配，由于我们是顺着填下来的，所以其他位置一定 当前位置，于是排完序直接枚举 ，不合法直接扔掉就行了，时间复杂度 。
T2
考虑到了前面很多的性质，唯独没有发现最后的性质，考虑每次操作相当于向右压缩整个连续段，但是最终无法删掉连续段，最短也会留下 的长度，而我们可以在左边任意添加新的元素，因此只要对于任意位置均满足 X 的后缀连续段数量 Y 的后缀连续段数量即可，使用线段树维护，每次只会修改 个位置。
维护最小的差值，可以转化为一个加一个减，维护区间最小值。
T3
考虑最优策略一定是打 轮，最后会额外有一些，贪心的按照 从大到小依次填进去即可。
考虑如果 很大，我们可以不枚举 ，观察这个式子是类似整除分块的形式，我们可以按照整除分块，对每个块内同一计算答案，具体的维护出每个块合法 区间 ，找到和区间有交的 统计答案即可。
T4
考虑图实际上是一个竞赛图，有一个比较好的性质是，从一个点出发能到达的所有点，均可以在同一条链上，于是问题转化为了从三元组 出发能到达的三元组数量，考虑 BFS 如何更新。
发现条件看似是一个三维偏序，实际上只需要满足其中两维，我们考虑分讨三种合法情况，以 为下标，另一个为值建立线段树，每次暴力找合法的点即可，每个点只会被删除 次，因此总时间复杂度 。
11.12 限时训练
考虑贪心如何做？按右端点排序，每次尽量在最右边种树，这样可以对后面区间贡献尽可能大，现在问题变成了维护区间内已经覆盖的点的数量，以及找到范围内最右端的点，分别使用树状数组和 set 维护，由于每棵树只会被种 次，总复杂度 ，记得离散化一下，处理一下细节。
考虑从哪个 过来其实不重要，对于每个点我们只关心 个有用的点，因此可以直接在状态多加一维表示从哪个 转移过来，如果一个点已经被转移了 次那么这个点就没有用了，因为走前 个一定更优，用 map 维护即可。
考虑 dp， 是好想的，方程如下
考虑如何优化，发现限制条件其实是 对和 对的限制，考虑枚举 ，另外两维可以双指针维护。
对每个位置维护状态 表示是否可以作为前缀严格最大值，考虑一个限制 实际上是 这段区间一定不能作为前缀最大值， 一定是前缀最大值。
然后设计 dp，设 表示前 个位置，前缀 为 ，转移分 分别转移，可以用前缀和优化。
发现一个连续段内是互相不影响的，于是考虑对每个连续段去做，于是就变成了 ，其中 是快速幂，具体 dp 方程比较好推，是在推不出来可以看题解，式子很详细。
首先考虑 作为两个合法首领的充要条件是 ，其中 表示选 的人数， 表示 ，要不然肯定要选 这个。
于是可以想到对每种 去双指针找到 ，用 set 维护 的所有编号，取最大最小即可。
想一下，发现 最多只会有 种，想要卡满就是每个人分别有 票，其实就是等差数列求和，所以是 的，于是我们维护一下序列里当前有哪些 ，直接按上面的做，总时间复杂度 ，可能要带个 set 的 ？应该不需要。
11.13 模拟赛
T1
首先考虑无解的情况，由于每种颜色刷子只有一个，因此考虑对于一种颜色，设他最前面出现的位置为 ，则若出现 ，则无解，也就是两个区间交但不包含，剩下的则直接维护出每种颜色区间 ,直接从前往后染色即可。
T2
考虑设每次取出的三个位置为 ，考虑每次操作，一定让最小值放到 上，于是如果 ，则不变，若 则交换前两个，否则我们发现 我们不能确定如何分配，此时我们记忆化搜索下去，由于交换形成了类似完全二叉树的结构，因此复杂度有保证。
T3
考虑当确定 ， 和 之间是成二次函数关系的，因此最优一定取到 或 ，枚举 ，可以得出 ，随后找到最优符合条件的 a 即可。
T4
考虑每次归并，实际上是形成了若干个有序连续段，这里有序指的是最开始的一个元素有序，连续段则为，从最开始的数，以它作为开头且最大值的极长区间，随后每次操作变成了拆开一个区间，由于最多 个区间，每个区间只会被拆一次，因此可以直接维护，使用权值线段树维护每个段的长度，查询时线段树二分即可。
11.14 限时训练
T1
比较简单的一道题，首先考虑无修改，贪心去做肯定让效率高的多产几天，于是我们排序，每次修改找到原来的位置和新的位置，计算一下增量即可。
T2
给定一棵树，对树上不超过 的点 ，单点询问。
首先考虑一个比较暴力的，每次跳父亲，对其子树能覆盖的范围区间乘，但是发现会重复，观察重复部分，发现每个父亲会覆盖向下 和 两层，每次跳父亲时 都要 ，于是可以直接维护 ，每次询问暴力跳父亲即可。
T3
第一问拓扑是好做的，考虑第二问，实际上我们可以考虑整个过程，在每一步转移都是取字典序最小转移，因此我们每次只考虑 和 的这些点即可，每次处理出排名，按照先边权，后排名的顺序取即可。
T4
之前题单里的一道题，考虑从大到小取，如果一个人同时作为多个集合的最大值，则只能把他删掉，要不然不合法，贪心用堆维护即可。
Luogu NOIP 模拟 T1，起来比较晚，发现其实合法的一定是在最大能凑出来之内，首先特判掉一些边界情况，剩下的肯定贪心从大到小取比较优，这里还需要注意到 是假的，最多只有 的级别，然后二分答案就做完了。
性质题，首先如果最开始 直接搞到最左边然后一直向右平推即可，否则看看能不能吃掉右边第一个，如果此时右边能吃回来则 必败，否则则是要比较两边的和，注意到只会攻占一个位置就做完了，前缀和维护一下。
比较简单的题，看到性质 ，考虑实际上每个点的区间，维护一下从根到这个点的前缀和，对路径上限制取更紧的，然后就可以求出每个点合法限制区间，相当于是给定若干个区间，每次询问这个点在多少个区间内，差分一下就行，这里还写了树状数组的差分。
哇，非常难的一道题！
其实是性质题，考虑当区间出现了超过 个数字，则一定可以取到 ，于是先计算这些区间，具体的使用一个单调栈，然后考虑小区间如何计算，发现式子可以拆成 ，此时只有 某一位只有一个 才能产生贡献，我们直接枚举区间一维，枚举 ，然后计算贡献即可。
具体计算，我们需要满足 和 按位与的结果这些位置是不合法的，同时对于区间内不存在的这些位置，只保留这些位置，然后计算贡献即可。
要注意当我们需要使用单调栈统计每个数作为最大值的区间，统计贡献时，需要注意钦定相等的贡献算在左边或右边，否则会算多或算少，这里可以在从前往后单调栈时使用 ，从后往前使用 即可。
11.15 ABC
掉大分了，E 是一个比较简单的线段树，考虑算一下贡献就做完了，G 貌似是多项式科技，据说要用 NTT，不会。
F 写了一个 IDA*，最后 TLE 了没卡过去，D 题怎么还是大模拟，这场输麻了。
相关推荐
评论
共 0 条评论，欢迎与作者交流。
正在加载评论...