25.10-LCA-Week5-8 模拟赛题解

KSCD_ · 2025-10-19 19:52:56 · 题解

10.23

兵败如山倒。T3 Dijkstra 开成大根堆是什么玩意，T4 太难了不会，还挂了十分。还是要注意细节吧。

T3 暗符「Demarcation」（境界线）

题意

给出一个网格，给定起点和终点，每次移动会将当前位置标记为障碍，然后向某个方向走到障碍处停下，求走到终点的最少移动次数。n,m\le 10^3。

题解

考虑从起点开始走的情况，注意到通过来回走可以到达中间没有障碍的同行列点，代价从两边往中间递增，通过调整可证明以此为代价能取到最优解，且不会比答案小，直接 Dijkstra 可以做到 \mathcal O(n^3\log n) 的复杂度，用 n 个队列代替堆可以做到 \mathcal O(n^3)。事实上前者甚至都能过。

前缀和优化建图，注意到每个点向相邻所有点连 2，向一步能走到的点连 1 即可表示整张图。Dijkstra 复杂度 \mathcal O(n^2\log n)，用 3 个队列代替堆可以做到 \mathcal O(n^2)。

原题

AT_joisc2016_j。

T4 暗符「Dark Side of the Moon」（月的阴暗面）

题意

给定一个长宽均为 120 的网格，每个格有向下或向右的方向，初始均向右，且 (0,0) 位置有标记。每个时刻所有标记按照所在格的方向移动，并将原位置的方向变成另一种，之后在 (0,0) 生成一个新标记。q 次询问 t 时刻变化之后 (x,y) 上是否有标记。q\le 10^4,x,y\le 120,t\le 10^{18}。

题解

太难了，补完还是不知道为啥要这么做。整个变化非常抽象，难以对一个时刻的局面考虑，于是计算前 t 个时刻经过 (x,y) 的标记总数，差分一下就能得到 t 时刻是否有标记。只有前 (t-x-y+1) 个标记能到 (x,y) 点， 设 f_{i,j} 表示经过 (i,j) 点的标记数，有 f_{0,0}=t-x-y+1。显然若 (i,j) 被经过 x 次，有 \lfloor \frac x2\rfloor 个会向下走，其余向右走，容易递推出 f_{x,y}，时间复杂度 \mathcal O(\sum xy)。

太难了。

原题

CF1733E。

10.25

ICPC 赛制，三人三机打得还行，CSP 之后还得加练。

A. Azalea Garden

题意

给定 n 个怪物，每个怪物有 a,b 两个属性，若 a_i\ge b_j,i\ne j 则 i 可以消灭 j。有 q 次 (a_i,b_i) 的单点修改，初始及每次修改后求最少能剩多少怪物。n,q\le 4\times 10^5。

题解

先考虑不带修怎么做，找到 a 最大的怪物 x，则 j\ne x,b_j\le x 的所有怪物 j 可以全部被消灭，设这种 j 有 c 个。此时答案只可能是 c 或 c+1，关键在于能否在消灭 c 个怪的同时消灭 x，显然此时取 a 最大的怪物中 b 最小的为 x 最优，若此时还有 b_x\gt a_x 则答案只能为 c。

之后先找到 j\ne x,b_j\gt x 的怪中 a 最大的怪物 y，若 a_y\ge b_x 则最后可用 y 消灭 x；否则 y 可最终消灭 c 个中的 p_1,a_y\ge b_{p_1}，在此之前用 a_{p_1}\ge b_x 消灭掉 x；若仍不满足还可以用 p_1 消灭 p_2，用 p_2 消灭 x，以此类推。于是只要存在序列 p_k 使得 a_y\ge b_{p_1},a_{p_i}\ge b_{p_{i+1}},a_{p_k}\ge b_x 就可以消灭掉 (c+1) 个，否则就只能消灭 c 个了。冷静分析发现这等价于 p 中的 (b_{p_i},a_{p_i}] 依次将 (a_y,b_x] 完全覆盖，判断 c 个怪物是否完全覆盖即可。

至于带修，注意到判断到最后一步时已有 b_x\le a_x，而不在 c 个内的 b_j\gt a_x，一定不会影响到上述判断，于是维护全局覆盖情况即可。还需要动态维护 a_x,b_x,a_y,c 的值，考虑在 b 上开权值线段树，对于一个 (a_i,b_i)，在 b_i 上挂一个 a_i，维护区间 a 的个数和最大值。查询时可线段树二分出 b_x，之后容易查询其他值。区间覆盖也可以离散化后线段树维护区间最小值，总复杂度 \mathcal O((n+q)\log (n+q))。

B. Beautiful Dangos

题意

给出一个三色序列，可选择一个区间并任意重排其中的元素，要求最终序列相邻元素不同，求所选区间的最短长度。判断无解，构造方案。多组数据，\sum n\le 2\times 10^6。

题解

不难发现当且仅当最大出现次数 t 满足 2t-1\gt n 时无解，初始合法也容易判断，先判掉。之后对于原序列每对相邻相等元素 i,i+1，操作区间至少要覆盖两者之一。于是取这种元素的 \min(i)+1 作为 L，\max(i) 作为 R，则合法操作区间一定满足 l\le L,r\ge R。注意此处可能有 L=R+1，不过没有影响。

还需要具体判断区间是否合法。对于某种颜色 c，设 s_i 表示前缀 i 中 c 的出现次数，则对字符 c 来说区间 [l,r] 合法当且仅当 2(s_r-s_{l-1})-1\le {r-l+1-[a_{l-1}=c]-[a_{r+1}=c]}，实际意义与 2t-1\gt n 是类似的。移项并整理可得 (r-[a_{r+1}=c]-2s_r)+(2s_{l-1}-l-[a_{l-1}=c])\ge -2。设两括号内的式子分别为 g_r,f_l，合法条件即 g_r+f_l\ge -2，非常简洁啊！

之后对于最小操作区间 [L,R]，先用该方式判断三种颜色是否合法，可以发现非法颜色最多只会有一种。对该颜色尝试将区间向两边扩展，讨论一下可以发现此时 f,g 分别单调，双指针即可求出最短的操作区间。至于构造方案，每次填当前剩余次数最大的颜色即可，有多种时优先选 a_{r+1} 就好了，复杂度 \mathcal O(n)。

C. Catch the Monster

题意

给定一个森林，其中有一个怪物。每次操作可选择一个点 x 抓捕，若没抓到怪物，则其可以不动或移动到相邻非 x 的点。若存在一种抓捕序列，对任意的怪物初始位置和移动方式均能抓到怪物，则称该森林是好的。q 次询问，每次给出 [l,r]，求只保留编号在该区间内的点及两端均存在的边时，整个图是否是好的。n,q\le 10^6。

题解

考虑如何判定合法性。注意到若每个连通块均为毛毛虫形，即存在一条链使得每个点均在链上或与链相邻时一定是好的，构造可以从头开始遍历链，每个点 u 先抓一次，之后对于其每个链外邻点 v，依次抓 v,u 各一次即可。

于是最小的非法图即一个点连上三条长为 2 的链，只需判断图中是否存在该结构即可。于是对于多组询问，只需处理出 p_l 表示 r\ge p_l 的 [l,r] 非法，r\lt p_l 的 [l,r] 合法，也即极小非法区间 [l,p_r]，即可 \mathcal O(1) 回答询问。

考虑枚举中心点 u，之后对于其每个邻点 v，找到其非 u 的邻点中 v 的前驱后继 p,q，只要同时包含 u,v,p 或 u,v,q，则 v 就是某条长为 2 的链。三个点可以写成 [\min,\max] 区间，只要包含该区间即可。不妨令二者带上 v 的颜色，则所有包含的区间颜色数不低于 3 的区间均非法。

不难发现此时 L 递增时最小非法 R 仍不降，于是处理出所有区间后仍可以双指针求。另外此时只有区间端点有用，而区间数为 \mathcal O(d(u))，离散化后做就行。对于每个 L,R 先更新 p_L，最后求后缀 \min 即可。总复杂度 \mathcal O(n\log n+q)。

K. Killing Bits

题意

给定两个从 0 开始长为 n 的排列 a,b，每次操作可以选择一个排列 c，更新 a_i\leftarrow a_i \& c_i，这里是按位与运算。判断 a 能否在任意次操作之后变成 b。多组数据，\sum n\le 5\times 10^4。

题解

首先若存在 b_i 不是 a_i 子集则一定无解，若 a,b 相同则有解。对于其余情况，注意到只要存在 c 满足所有 b_i 均为 c_i 子集则有解，否则无解。证明考虑只要存在这样的 c，就可以分别将 b_i 换到对应位置上，此时另一边变成了 b_i 的超集，合法性不变，一定存在解。于是这个条件是充分的，必要性不会证，不管了。

这时需要求是否存在合法的 c，此时相当于一个二分图完美匹配，左部点是 n 种取值 x，右部点是 n 个 b_i，x,i 间连边当且仅当 b_i 是 x 的子集。考虑优化建网络流图，即建出中转点 y，对所有 y 向每一位 1 变为 0 的子集连流量无穷的边，之后 x,b_i 分别连向相等的 y 即可。最后 Dinic 跑一下是否有完美匹配就行，复杂度能过。

10.27

整体还可以，严肃学习 T4 的 MEX 性质。T3 有更好写的做法，如果不写平衡树会有更长的时间做 T4。

T4 隋唐测试

题意

给出长为 n 的序列 a，q 次询问某个区间 [L,R] 内长度不超过 k 的子区间的最大 MEX。n,q\le 10^6。

题解

MEX 定义为未出现过的最小值，考虑将每个值贡献到所有区间上。将区间按照 l,r 两维画到坐标系上，则每个 x 未出现的极长区间 [L,R] 会贡献到 L\le l\le r\le R 这个矩形（三角形）内，相当于其内部每个点对 x 取最小值。这样的极长区间共有 \mathcal O(n) 个。

由于是取最小值，直接从小到大考虑每个 x，则会将 (L,R) 右下角的所有没填过的点均填上 x。这个过程中填过的轮廓始终是一个左下到右上的折线，于是可以用 set 维护拐点快速处理。

另外，每个区域大概是一个倒过来的阶梯形，由于询问是一个贴着直线 y=x 的梯形，只要该区域能贡献给某询问，则询问的梯形一定包含某个阶梯拐点。于是只用阶梯拐点 (x,y,w) 计算即可，这个拐点数量也是 \mathcal O(n) 级别的。

之后把询问的梯形拆成右上方的三角形和剩余的平行四边形，前者对应 r-k+1\le x\le y\le r；后者将平行四边形向下压，即以 r-l 为纵坐标，可得 y-x\lt k,l\le x\le r-k+1。前者对 r,y 扫描线后是后缀查询，可以树状数组；后者对 y-x 扫描线后是区间查询，只能线段树。总时间复杂度 \mathcal O((n+q)\log n)。

10.29

最后一场了，出得有点烂，因为「斜二倍增」是树上算法的“新优选”！但是 T4 确实好题啊。

T3 树练习题

题意

给出 n 个点，分别有点权 a_i。q 次操作，每次随机出两个点 u,v，若不连通则加入边 (u,v)，连通则询问 (u,v) 路径上点权的非空最大子段和。n,m\le 3\times 10^6。

题解

最大子段和是半群信息，也就是说题目要求支持动态加边的树上路径半群信息查询。考虑暴力做法，即每次取出对应路径暴力查询。此时需要维护每个点的深度和父亲节点，使用启发式合并更新即可。由于随机加边的期望树高为 \mathcal O(\sqrt n)，复杂度为 \mathcal O(n\log n+q\sqrt n)，能过不少。

考虑静态树上路径半群信息查询方式，树剖难以动态加点，考虑使用倍增。传统倍增每个点有 \mathcal O(\log n) 的信息，套上启发式合并复杂度为 \mathcal O(n\log ^2n+q\log n)，空间也有 \mathcal O(n\log n) 的复杂度，爆炸了。

于是使用斜二倍增，设 w_i 表示 i 向上跳 F(d_i) 步的信息及其对应祖先。之后倍增求出 LCA，同时合并路径信息即可。这里 F(x) 定义为后树上其管辖节点长度，可以倍增预处理。这样每个点只需要维护一个信息，时间复杂度降为 \mathcal O((n+q)\log n)，空间复杂度 \mathcal O(n)，可以通过。

原题

P14302。

T4 无尽旅途

题意

若 T 时刻在 u 点，则该时刻结束时会传送到 c_{u,T\bmod d_u} 点。给定 c，q 次询问从 T 时刻在 u 起经过 x 个时刻后停在哪个点。n,\sum d\le 10^5,q\le 5\times 10^4。

题解

这种问题考虑倍增，设 f_{i,j,k} 表示在 i 点且 T\bmod d_i=k 的状态下走 2^j 步到达的点。然而这个状态是有问题的，一旦走到 d_u\gt d_i 的 u 点，k 记录的时间信息就不够用了，需要知道时刻对 d_u 取模的结果。于是 j 这一维需要开到 \max d，只能做到 \mathcal O(nd\log V) 的时空复杂度，无法接受。

但由于 d 为 2 的整数次幂，一共只有 \mathcal O(\log d) 种取值，于是信息不够用的情况只会发生这么多次。考虑改 f_{i,j,k} 为走过 2^j 个 d 与 i 相同的点时最终到达的点。由于可能卡在 d_u\gt d_i 的点 u 上，同时记录 g_{i,j,k} 表示此时走的步数，这些信息容易按 d 从小到大的顺序预处理。

查询时同样从高位到低位跳，如果被卡了就重新从最高位开始。注意过程中若跳不到 d 相同的下一个点，需要暴力向后跳一步。显然被卡和暴力向后跳的次数均不超过 \mathcal O(\log d)，总时间复杂度为 \mathcal O(\sum d(\log d+\log V)+q\log d\log V)，空间复杂度为 \mathcal O(\sum d\log V)。

原题

P10198。

11.06

CSP 之后第一场，感觉还行。T4 太难，胡出来一个比较假的做法，跟正解有点关系，但正解是人能想出来的吗？

T4 雪符「Diamond Blizzard」（钻石风暴）

题意

给出一个内向基环树，每个点有点权 a_i，每次更新将所有满足 a_i\le a_{p_i} 的 a_i 同时增加 1。q 次询问 d 次更新后 a_g 的值。n,q\le 2\times 10^5。

题解

设 f_{i,j} 表示 a_i 在 j 时刻的值，有 f_{i,0}=a_i,f_{i,j}=f_{i,j-1}+[f_{i,j-1}\le f_{p_i,j-1}]。考虑 p_i=\min(i+1,n) 的特殊性质，显然 f_{n,j}=a_n+j。考虑从后往前推出所有的 f_i，首先 f_{i,j} 关于 j 的变化可以画到坐标系里，且只有 0,1 两种斜率。

关注第一次满足 f_{i,t}=f_{i+1,t} 的时刻 t，若 a_i\le a_{i+1}，则 t 之前 a_i 一直增加，否则 a_i 一直不变。这部分斜率是相同的，可以区间覆盖实现。至于 t 之后，有 f_{i+1,j}\le f_{i,j}\le f_{i+1,j}+1，具体取决于 a_{i+1} 第 j 次有没有增加，画到图像上大概会形成若干平行四边形。

之后思路不太像人。注意到 t 之后部分的差分数组是位移得到的，具体来说是在 i+1 的差分数组开头插入一个 1，之后整体向后平移一位，手摸一下可以发现该结论是对的。整体向后平移可能能用平衡树维护，但比较困难，没有尝试。

尝试避免向后平移。考虑将 f_i 图像向左平移 1 得到 g_i，注意到现在有 g_{i,j}=f_{i+1,j}+1 了，可以区间加实现。然而前半部分维护的是斜率（即差分数组），好像还是很难做，考虑再将 g_i 向下平移 1，于是有 g_{i,j}=f_{i+1,j} 了，后半部分直接不用管了，赢。

然而细节仍然有一车，首要的就是给 g 一个更好的定义。令 i 的深度 d_i=n-i，我们令 g_{i,j}=f_{i,j+d_i}-d_i，这样就实现了 i 图像相对于 i+1 图像向左和向下分别平移了 1。同时由于用深度定义，这也可以拓展到树上。

当然这里需要维护 g_{i} 的差分数组 h_i。重新画图讨论转移，发现此时 g_i 图像的 j 点向上走需要 g_{i+1,j+1} 严格大于 g_{i,j}，这和题目条件 f_{i,j-1}\le f_{p_i,j-1} 是一样的。手推讨论之后发现若 a_i\le a_{i+1}，则找到 h_{i+1} 第 (a_{i+1}-a_i) 个 0，此处之前全覆盖成 1，后面不变；否则 a_i\gt a_{i+1}，需要找到 h_{i+1} 第 (a_i-a_{i+1}-1) 个 1，前面全覆盖成 0，后面不变。这可以用线段树二分和区间覆盖实现，这样就完成了特殊性质的做法。

至于基环树，由于环上最小值一定会一直增大，可以从此处断环变成一棵树。树上的话每个点只会受到根链上的点影响，同样用线段树维护，出子树时撤销修改即可，时空复杂度都是 \mathcal O((n+q)\log n)。然后会发现空间爆了，我的做法是部分标记永久化，大概是在修改时正常下传标记，查询和二分时均不 pushdown，而是直接用函数传参记录根节点到当前点路径上第一个覆盖标记，这样撤销次数大大减小，可以通过。

当然好像有区间赋等差数列的做法，那就是直接维护 g 数组了，应该差不多。

11.08

T3 爆了 lower_bound 返回值的语法错误，之后注意。T4 太神秘了，已严肃学习。

T4 学习

题意

给出一个森林，点有点权 a_u，边有边权 b_u。标记一个点需要花费 a_u 的代价，若其父亲已被标记，也可以花费 b_u 的代价。标记随时可清除，且不能同时存在超过 k 个标记点。要求树上的 m 个点均被标记过，求最小代价。多组数据，T\le 30,m\le n\le 5000,k\le 5。

弱化版：每个点只能被标记一次，T\le 5,m\le n\le 10^5,k\le 10。

题解

判掉 k=1，此时答案为 \sum a；将 b_i 对 a_i 取 \min，同时以 0 为树根且不标记，避免讨论。考虑标记点形态，k=2 时标记 u 点后可向下拓展到子节点，但是需要清除 u 点标记才能接着向下，最终能覆盖毛毛虫形状内的点。定义单点是 1 合法的，对于 i\gt 1，定义 u 子树 i 合法当且仅当存在一个儿子 i 合法， 且其他儿子均 (i-1) 合法，这也能解释 2 合法的形状。

于是对于弱化版，设 f_{u,i} 表示 u 子树内关键点均被标记过，且从 u 开始的拓展过程 i 合法的最小代价。状态不考虑 u 点代价，因为其取值受父亲影响。另外令 f_{u,0} 表示 u 不选时的最小代价。转移为 f_{u,1}=f_{u,0}=\sum\min(f_{v,k}+a_v,f_{v,0})，对于 i\gt 1，有 f_{u,i}=\min(f_{v,i}+b_v+\sum_{t\ne v}\min(f_{t,i-1}+b_t,f_{t,k}+a_t,f_{t,0}))，只需先对第二个式子求和，再找最优差值更新即可。最后若 u 必须被标记，将 f_{u,0} 赋为正无穷，复杂度 \mathcal O(nk)。

对于原题，同一个点可被学习多次，即可以从 u 拓展到 v，在 v 拓展的过程中扔掉 u，之后需要标记 v 或其他子节点时再把 u 标记回来。据此设 f_{u,i,j} 表示考虑 u 子树，用到了至多 i 的空间，过程中 u 的子节点拓展需要 u 点标记 j 次的最小花费。与上面相同，状态不考虑 u 点代价，这会在父亲节点上决策。

这个状态在定义什么？其包含子树内其他点的标记次数和方式，记录过程中的最大空间消耗和 u 用于拓展的标记次数，以便向上转移。由于空间越大越可操作，f_{u,i,j} 随 i 增大单调不增。另外 f_{u,i,0} 并非不标记 u，而是已经考虑的过程没有用 u 拓展，还没有因此标记过 u。最终 f_{u,i,0} 的值是无意义的，事实上代表的是 i'\lt i 的 f_{u,i',y}，该状态也不能转移给父亲。至于真的不标记，再设 g_u 表示 u 不用于拓展时子树内最小代价，此时子树内其他拓展过程均可使用 k 的空间，不用记录。

由于从某点开始同时向多个子树拓展不优，可以依次处理每个子树，这样可用空间更大。于是可依次将每个子树 v 的信息拼到 u 上。具体地，新拼上一个子树 v 时，有以下几种转移（t_v 表示 v 是否需要标记；均有限制 i\ge 2,j\ge 0,y\ge 1）：

最难理解的可能是转移 3，即 v 用了全部的 i 空间，此时每次从 u 拓展都要重新标记 u。这里状态第三维记录的是用于拓展的标记次数，理解了这一转移大概就能理解状态设计的方式了。

至于初始值，开始的时候只有单点 u，所有值均为 0。f_{u,1} 没有转移，注意到此时 u 同样不能向下拓展，全部赋成 g_u 即可。暴力实现的话，转移 2.4.5 的复杂度不超过 \mathcal O(n^2k)，可以接受；而转移 1 是 \mathcal O(n^3k) 的，转移 3 不限制上下界是 \mathcal O(n^4k) 的，均需优化。

对于转移 1，注意到是对所有 y 取最小值，于是设 h_{i}=\min(f_{v,i,y}+yb_v)，转移就变成了 f_{u,i,j}+h_{i-1}\rightarrow f'_{u,i,j}。这样转移和 h 的预处理都是 \mathcal O(n^2k) 的了，可以接受。

对于转移 3，注意到下标变化只与 x 有关，先用同样方法避免掉 y 的枚举。具体地，对于确定的 i,j,x，会用 y\ge x 的 f_{v,i,y}+xb_v+(y-x)a_v 转移。将 y 分离出来得到 f_{v,i,y}+ya_v，预处理其后缀最大值 h_{i,y} 即可，复杂度同样是 \mathcal O(n^2k) 的。之后转移为 f_{u,i,j}+h_{i,y}+x(b_v-a_v)\rightarrow f'_{u,i,j+x}。注意到 j 一维显然不会超过子树大小，可以套用树形背包，复杂度就是 \mathcal O(n^2k) 的了。

于是做到了 \mathcal O(n^2k) 的时空复杂度， 单组数据就能过了。然而原题是 30 组多测，根本不是人。不过还有常数优化！考虑一次 i 合法的拓展，若新覆盖的点数少于 i，则其一定也是 (i-1) 合法的，可以将其拼到某次 i 合法的拓展上。因此一次 i 合法的拓展至少新覆盖 i 个点，于是 f_{u,i,j} 的 j 一维可限制 j\le \lceil\frac {s_u} i\rceil。加上这个常数大大减小，可以通过。

原题

P12777。

弱化版：P12734。

11.10

打得还行，T4 太鬼畜，随机扰动乱搞无法战胜。

T4 昡符「积木流彩」

题意

给定长 n 宽 m 的网格，保证 n,m 均为奇数。局面定义为用 1\times 2 的积木不重叠地铺成只剩一个空格，每次操作可选择当前空格相邻的一个积木，将其移动到该空格及原来某格内。给出初始局面和目标局面，构造操作序列实现两者间的转化。n,m\le 2000，要求操作序列长度不超过 8\times 10^6。

题解

将棋盘黑白染色，注意到空格始终在同种颜色的格子里，且每个积木均跨过两种颜色。考虑将局面建模成二分图匹配，黑白格分别对应左右部点，积木对应边。考虑初始和目标之间的关系，求出两个匹配的对称差，上面每个点度数不超过 2，只会形成环和链。又由于除空格外每个点度数恰为 1，所以只存在两图空格之间一条链，其余均为环。

再考虑操作在图上是什么，发现是从空格（失配点）起走一条非匹配边和一条匹配边，并将两者状态互换。于是先把上面所说的链走完，对称差中就只剩若干个环需要修改了。由于对称差中边的状态交错，环长也一定是偶数。

此时两个局面的空格位置相同，考虑在目标局面图上 DFS，遍历每个格子。一旦搜索到某个两局面中连边情况不同的格，说明该格在交错环上，此时立刻停止搜索并绕环走一圈，将该环转化到目标状态，同时空格也回到原点，再接着进行搜索。注意到整个图是一个连通块，DFS 会搜遍所有格，因此最终一定得到了目标状态。

至于操作次数，每次操作走两个点，每个点会搜到一次，搜完之后还有回溯，这部分不超过 nm 次；清环操作经过每个点至多一次，这部分不超过 \frac 12 nm，总操作次数不超过 \frac 32nm，可以通过。

11.13

太困难了，T2 还不给大样例，暴力还挂了；T3 寒假做过同类题但还是没做出，大败而归了。

T2 毒瘤

题意

给定一个坐标系，初始有两个点一条边，所有边边权均为欧几里得距离。q 次操作，修改加入一个新点 c，给出其坐标 (x,y) 和两个点编号 A,B，保证 A,B 间有边，之后加入 A,c 和 B,c 两条边；询问求两点间最短路。q\le 10^5。

题解

非常抽象地，考虑建一张新图，其中的点表示原图的边。加入一个点 c 时，在新图中加入点 (A,c),(B,c)，并将这两个点向代表 (A,B) 的点连边。显然每个点有唯一父亲，于是新图是一棵树。

考虑将原图中的路径长度表示到新树上，定义新树的一条路径权值为，找到新树路径的两个端点，对应回原图中的各两个点，记录两两之间的四条路径距离，前提是只经过该路径上对应边两端的点，且每条边至少经过一个点。

这样的话每次询问 x,y 间最短路时，分别找出加入该点时对应的两条边，分别求四次树上路径信息，找到对应 x,y 距离的值取 \min 即为答案。有一些细节，若调到 LCA 之前的两个点与 LCA 在同一三角形内，需要特判直接走过去的情况。信息可以 \min + 矩阵乘法维护，复杂度大常数 \mathcal O(n\log n)。

T3 异或

题意

给定序列 a，每次操作可以选择 2\le i\le n 的 i，并修改 a_i 为 a_i\oplus a_{i-1}。判断任意次操作后是否能使整个序列不降，若可以再求出单调不降序列数字种类数的最大值。多组数据，T\le 30,n\le 10^4,a_i\lt 2^{30}。

题解

手玩一下发现可对任意 j\lt i 进行 a_i\leftarrow a_i\oplus a_j 的操作，且不改变其他值。于是最终 i 位置可以是 a_i 异或上 j\lt i 任意子集异或值。任意子集异或值可以用线性基维护，于是判定只需要贪心填最小数即可，每次求出 U_{i-1} 内 y\oplus a_i\ge f_{i-1} 的 y\oplus a_i 作为 f_i，其中 U_i 表示长为 i 的前缀对应的线性基，可以做到 \mathcal O(n\log V+\log ^2V)，后者是线性基标准化的复杂度。

至于求最大值，考虑暴力 DP，设 f_{i,j} 表示前 i 个数内有 (j+1) 种值时 i 位置的最小值，用线性基支持同样操作即可转移，复杂度 \mathcal O(n^2\log V+\log^2V)。

注意到前缀线性基只有 \log V 种，考虑对相同线性基整体转移。具体地，若 i\in[l,r] 内的 U_i 全相同，则在 l 处暴力转移，这样的位置有 \log V 个，复杂度 \mathcal O(n\log^2V)。对于 [l+1,r] 内的转移，由于 a_i 无法加入线性基，这部分的最终值均为 U_l 中的任意值。

设 d=r-l，需进行相同的 d 次转移，此时每次取相同数或线性基中后继最优。具体地，令 f'_{j} 表示目前 (j+1) 种数的最小值在 U_l 中的排名，g'_j 表示转移 d 次后最小值在 U_l 中的排名，有 g'_j=\min_{j-d\le t\le j} f'_t-t+j，用单调队列维护 f'_t-t 即可快速转移。f',g' 与值的转化需要在标准化线性基中查询排名和第 k 小，总复杂度 \mathcal O(n\log ^2V)。

T4 符板

题意

给定 n\times m 的字符矩形，有两个字符相同，方向不同的 1\times l,l\times 1 矩形，需要在字符匹配的前提下密铺整个矩形，求合法矩形对应的 l 集合。n,m\le 1000。

题解

注意到对于单个 l，合法字符串一定是第一列或第一行的前 l 个字符，只需要考虑如何判断合法。对某个位置考虑，猜测若能横着填就横着填是对的。原因是若 (i,j) 处能横着填，若这 l 个位置均竖着填则模板串全同，否则若 t 个位置竖着填，(i+t,j) 开始横着填，则模板串前 t 个字符相同且 t 是其周期，模板串也一定全同。而模板串全同的情况只能覆盖全同的矩形，容易特判。

于是可以从左上到右下依次进行覆盖，若某个位置未覆盖则从此处开始分别向右、向下判断长为 L 的串是否未被覆盖且合法，均不合法就寄了，否则能横着合法就横填，否则竖填。注意到字符矩形全同的情况也能判出来，不用特判。此时以 \mathcal O(l) 的复杂度覆盖 l 个点，所以单轮判断是 \mathcal O(nm) 的。又由于只有 n 或 m 的因数可能合法，直接枚举就是小常数 \mathcal O((d(n)+d(m))nm) 的，可以通过。

T5 法法

题意

给定 n 个点，坐标为 (x_i,y_i)，权值为 c_i。q 次询问给出 A,B,C，求 \max_{Ax_i+By_i+C\lt 0} c_i。n,q\le 10^6,-10^9\le x,y,c,A,B,C\le 10^9。

题解

求半平面内最大点权，比较困难，考虑二分答案，判断半平面内是否包含某个 c_i\gt mid 的点，这需要求 c 在一段后缀内的点与半平面是否有交。显然 B\ne 0 时 \max Ax_i+By_i 在凸包上，可分治预处理出每个可能区间的凸包，之后可以回答询问，每次在凸包上二分即可，总复杂度 \mathcal O(n\log n+q\log ^2n)。

考虑整体二分，注意到若将询问按斜率 \frac AB 排序，则切到的凸包点是单调的。于是预先排好序后整体二分，每次双指针求出所有询问在右区间切到的点即可，总复杂度 \mathcal O(n\log n+q\log q+q\log n)，细节一车。

11.17

T2T3 是啥阴间，太困难。T4 倒是会但没调完，不管了。

T3 路标

题意

给定 n 个长为 m 的序列 d_{i,j}，表示 \lfloor y_j-x_i \rfloor=d_{i,j}，要求对于任意 i,j 均有 x_i\lt y_j。求最多能选出多少行使得存在 x,y 序列满足所有条件，保证答案不低于 \frac n5。n\le 1000,m\le 200。

题解

由于对答案大小有保证，可以随机某一行 u 并钦定其必选，再尽量多选其他的。合法条件可转化为对于任意 i,j 均存在 e_{i,j}\in[0,1) 满足 d_{i,j}=y_j-x_i-e_{i,j}。然而最好让限制中不带 x,y，这样比较好处理。于是令 a_{i,j}=d_{i,j}-d_{u,j}=x_u-x_i+e_{u,j}-e_{i,j}，再令 p_i 表示 a_{i,j} 的最小值位置，有 b_{i,j}=a_{i,j}-a_{i,p_i}=e_{u,j}-e_{i,j}-e_{u,p_i}+e_{i,p_i}\ge 0。

由于 d,a,b 均为整数且 e\in[0,1)，b 数组只有 0,1 两种取值。移项可得 e_{i,j}=e_{u,j}-e_{u,p_i}+e_{i,p_i}-b_{i,j}。于是需要存在 e_{u,p_i}\in[0,1) 使得上式全在 [0,1) 内，这要求 e_{u,j}-b_{i,j} 的极差小于 1。又根据 b_{i,j} 只有 0,1 两种取值，这相当于要求所有 b_{i,j} 为 0 的 e_{u,j} 小于 b_{i,j} 为 1 的 e_{u,j}。于是令 S_i 为第 i 行为 1 的列号，要求选出最多的 S 使得两两之间存在包含关系。

于是按 1 的个数排序后 DP，单轮复杂度 \mathcal O(\frac{n^2m}w)，还要乘上随机次数的常数，这里取 25 就过了。

原题

P14055。

11.20

打得还行，手感火热！但是 T4 把没判特殊性质的暴力交上去了，之后要注意。

T3 幻幽「Jack the Ludo Bile」（迷幻的杰克）

题意