11月日志

26-11-2

To do.

26-11-3

100+45+64+40。

注意到 T2 是青，T3T4 分别是紫黑，但 cdo 场切 134 不会 T2。

T1 画图（paint）

Statement

原题。

给定一个长度为 的目标 01 串 ，和正整数数组 ，求通过至多 次区间置 1 操作，使最终生成的 01 串与目标串 的所有失配位置的代价 的最大值最小。

。

Sol

二分答案即可，忽略 的位置，需要次数就是连续 1 段数。

T2 下棋（chess）

Statement

原题。

在一个 个节点的， 条边的有向图中，Alice 想最快把棋子从 号点移动到 号点，Bob 想尽量拖延时间。
每一回合，Alice 可以二选一：删掉一条边，或让 Bob 沿着一条未被删除的边移动一步。
求在双方都采取最优策略的情况下，Alice 至少需要多少时间。

。

Sol

神秘。

记 为 Alice 从 号点移动到 号点所需的最少时间，显然有 ，考虑 能更新的位置，我们发现，对于一个点，要想走其 最小的出边，就需要花费 的代价先删掉 更大的出边，对于次小值，则需要花费 的代价，依此类推。

反图上做 Dijkstra，边权为删边的代价加走路的代价（）， 即为答案。

T3 编辑（edit）

Statement

原题。

给定一个长度为 的数组 和 个区间限制，要求每个限制区间内的正整数互不相同。

允许将任意一段连续区间 内的数全部修改为 （可消除冲突）。求满足所有限制条件所需修改的最短区间长度。如果初始即满足，输出 。

。

Sol

考虑对于每一个位置单独考虑其限制，记 为包含第 个元素的最左区间端点，显然 之间不能有重复的 。

对于出现重复的情况，显然要么保留最左侧的，要么保留最右侧的，只有这两种可能的决策，记最左侧的为 ，次之为 ，最右侧的为 ，次之为 ，注意不保证这四个元素两两不同，但是 。

• 左端点在 的操作区间，右端点至少要是 ；

• 左端点在 的操作区间，右端点至少要是 ；

• 左端点在 的操作区间不合法。

容易维护，二分找 ，线段树 chkmax 即可维护所有操作区间的右端点要求，最后取最小值即可。

T4 树（tree）

Statement

原题。

给定一棵 个节点的树和一个长度为 的标记关键点的 01 串 ，对于树上的每一个起点 ，求满足以下条件的最长顶点序列 的长度：

1. ；
2. 对于 ，满足 ，即序列中节点不重复；
3. 对于 ，满足，即序列中所有节点均为关键点；
4. 对于 ，满足 ，即序列中相邻两个点的距离至少是上一对相邻点距离的 2 倍。

若起点 不是关键点，输出 -1。

Sol

。

注意到第二个条件不用管，因为对于任意序列中的节点三元组 ，满足 。

而若要有 则 ，矛盾。

然后显然有 的 DP。 表示从 开始上一步距离为 的最远答案，然而状态数太大没前途，但是发现 是 的，考虑定义域值域互换，设 表示从 开始走 步，上一步距离最大是多少。

的转移是

现在的 显然可以做到 ，考虑优化转移，发现是个有关两点之间路径的问题，考虑点分治优化。

固定分治重心，转移变为 ，只需要支持单点 chkmax，后缀查询 max，容易树状数组维护，跑 遍转移即可，时间复杂度 。

卡常小技巧：分治结构是固定的，只需要先跑出来分治结构存好，之后就不需要递归和 dfs 了。

26-11-4

综合题训练。

CF559E。

这种我为人人并且更新的 DP 值还有可能更新出不优的错解的 DP 好怪啊。

本题难点在于区间重合，考虑记录当前已选区间的极右点来限制贡献，如果新选区间左端点完全包含了极右点所属区间，这个区间的限制就是错的，那么从更左的极右点转移显然更优。

按左端点排序。

设 表示考虑 的区间，极右点所属区间为 ，该区间方向为 （0 左 1 右）的答案。

考虑如何转移，从小到大枚举 后面的区间以及它的方向，同时维护枚举过的区间中最靠右的区间以及它的方向。

设区间 在 方向的右端点是 ；此时枚举到区间 ，它的方向为 ，长度为 ，右端点是 ；枚举过的区间中最靠右的区间是 ，它的方向为 ，右端点是 。

那么有转移 。

注意 不对 取 ，因为这里 时，最靠右的区间贡献不是 而是 。

AT_agc007_d。

最简单题。

考虑我们的方案，显然是处理完一个前缀后，向右走一段，在向左走一段（可能不走），走之前可能还要等一下硬币。

设 表示处理完前缀 的答案，有 。

后面那个 可能有点迷惑，想一下可以发现，对于 到 后直接向左走再向右走回来，每个熊最后一次被经过时刚好实在在被给糖果之后 单位时间。

如果在向左走之后等一会，则 中的每个熊都会延迟相同的时间被经过。

递增，满足 的 递增，满足 的 是个窗口，前者最优转移值容易直接维护，后者最优转移值单调队列维护。

P3239。

设 表示考虑 的牌，做 轮的期望。

有 。

怎么理解？

第一种情况就是 始终未被选择，相当于在 中选了 轮的期望，第二种情况就是 在某一轮被选择，即在 中选剩余的 轮的期望加上 的贡献。

第一种情况的概率就是 ，第二种情况的概率就是 。

QOJ15189。

To do.

CF1781F。

To do.

26-11-5

【高2025级 + 高2026级】261105 NOIP 模拟测试（代码源精选2）。

CWOI 链接。

总结链接。

26-11-6

P2495。

虚树模板题。

P10013。

先考虑如何求 一个点的答案。

显然，拓扑序可能在 前面的元素一定在 子树外，且祖先链上元素拓扑序。必定在 前。

考虑逐个将 祖先链上的点及其不包含 的子树纳入考虑。

设 表示只考虑 及其子树，有 个点拓扑序在 之前的方案数。

初值 。

从下往上转移，研究 往 转移的过程。

我们要从 不包含 的子树中，选出拓扑序前 的点放到 之前，其余放到 之后，由于不在同一子树所以不包含 的子树的拓扑序与 的子树的拓扑序互不相关，两个组合数以算出把新点插入原方案的方案数。

所在子树 一定是拓扑序最小的，位置固定。

有转移方程：

后面那个分式可以预处理后 计算。

对于每个 做一次， 枚举到 ， 枚举到 ，时间复杂度就是 的。

答案 则等于 。

发现这个转移式子与 完全无关，中间转移的过程可以看做 到 的有向图边权乘积，完全可以反过来做，初始化 ，转移系数不变，转移方向变为从 转到 ，，时间复杂度 。