2024.10 做题笔记

标签：2024.10 log 复杂度 矩阵 笔记 Cat 维护 Mouse

2024.10 做题笔记

10.2

随机化和搜索题还是太神秘

P9257 [PA 2022] Mędrcy

将每条咒语代表的不知道它的两个人连边，如果存在一个人不知道任何咒语，即图是菊花图，则第一天他就会离开

否则第二天相当于每个人知道了每个人都至少知道一条咒语，那么如果一个人发现自己知道的咒语中有人一条都不知道，就说明那个人知道自己不知道的咒语，则他就会离开，去掉这个人相邻的边后，图是菊花图

归纳地考虑，第 \(k\) 天相当于每个人都至少知道 \(k-1\) 条咒语，将问题转化为求图中的最小点覆盖，如果大小 \(\le x\) 则输出所有可能在最小点覆盖中的点

求任意图的最小点覆盖显然是不可做问题，只能搜索

环和链都能直接计算，如果想优化搜索的复杂度则每次找度数最大的点 \(x\)，此时 \(deg_x\ge 3\)，枚举 \(x\) 是否在最小点覆盖中，如果在则去掉 \(x\) 及其相邻的边，否则相邻边的另一端点必须在最小点覆盖中

这部分的复杂度写出递推式，最坏情况下不选 \(x\) 能确定 \(3\) 个点，\(T(k)=T(k-1)+T(k-3)+O(n)\)，由于最多只会选 \(30\) 个点，复杂度暴力算出来大概是 \(O(1.4656^k)\)

复杂度咋算的？把后面看成 \(O(1)\)，解特征方程 \(x^3=x^2+1\)，得到两个根 \(A,B\)，递推式大概是 \(aA^k+bB^k\)，取较大根是 \(1.4656\)

P4581 [BJOI2014] 想法

把组成新题目的两个题目向新题目连边，得到了 DAG，要粗略求每个点前驱中 \(1\sim m\) 的点数

点数太多了无法使用 bitset，考虑近似算法

需要知道一个前置结论，如果在值域 \([0,v]\) 上等概率均匀随机取 \(n\) 个数，则最小值的期望为 \(\dfrac{v}{n+1}\)

反过来，如果知道某些这样得到的数的最小值，能求出数的期望个数

那么将 \(1\sim m\) 中的每个点赋予这样的随机权值，对剩下点拓扑排序求出前驱中的最小权值，求出期望个数，多做几次取平均值，实测做了 \(200\) 次可以

P7450 [THUSCH2017] 巧克力

中位数最小则二分答案 \(x\)，\(\le x\) 的看作 \(-1\)，\(>x\) 的看成 \(1\)，要求选出的连通块权值非负

\(k\) 很小，随机将每种染上 \([1,k]\) 中任意一种颜色，要求选的颜色不同，正确率为 \(O(\dfrac{k!}{k^k})\)

然后就可以跑最小斯坦纳树，求最小权值即可，实测每次二分随机 \(T=150\) 次可以，复杂度 \(O(Tnm3^k\log V)\)

#3400. 「2020-2021 集训队作业」Storm

显然选出的街道集合不会成环，一定组成二分图，且最多涉及 \(k+1\) 个点

如果原图是二分图，可以建立费用流模型，\(S'\) 连左部点，右部点连 \(T\)，每个点由于只能贡献一次，连流量为 \(1\)，费用为点权和流量为 \(\infty\)，费用为 \(0\) 的边，左部点和右部点的连边，流量为 \(1\)，费用为负边权，\(S\) 连 \(S'\)，流量为 \(K\)，费用为 \(0\)，跑最大费用可行流

如果原图不是二分图，把所有点随机染成黑白两种颜色，忽略同色点之间的边，这样染色正确的概率为 \(\dfrac 2{2^{k+1}}=\dfrac 1{2^k}\)，随机跑 \(T2^k\) 次费用流即可，\(T=10\) 可以通过

费用流的复杂度 精细分析 可以得到为 \(O(k^2(n+m))\)，大概是因为每次 spfa 每个点入队次数为 \(O(k)\) 次

「NOI2022模拟赛czx1」链式进化

怎么 acc 上模拟赛还有这个题……居然题解还给了确定性做法

\(O(n^2\log n)\) 就是对每行单独二分答案做，二分答案后双指针统计区间数即可

优化掉这只 $\log $ 的方法第一种就是随机打乱所有行，因为随机排列的前缀最大值个数期望为 \(O(\log n)\)，每次只需要先 \(O(n)\) 判断这行比前一行大时的答案是否可行，如果可行再二分，期望复杂度 \(O(n^2+n\log^2n)\)

但这也给我们启发，我们不需要随机化的性质，由于 \(\operatorname{mex}\) 值域为 \(O(n)\)，因此我们直接把行按 \(w\) 从大到小排序，则后面的行取到的答案必须增加，维护当前取到的答案是多少即可，如果符合就不断将答案 \(+1\) 并判断，复杂度是确定的 \(O(n^2)\)

Warrior

答案显然具有可二分性，关键是我们无法知道字典序刚好为 \(mid\) 的子段是谁，也无法比较它和其它子段的字典序

于是我们随机一个子段作为基准，枚举其它子段开头为 \(l\)，则如果 \([l,r]\) 比它字典序小则 \([l,r'](r'>r)\) 也比它字典序小，同理 \([l',r](l'<l)\) 也比它字典序小

双指针维护 \(l,r\)，维护线段树表示区间内每种数的个数，每次移动即可线段树上二分

时间复杂度 \(O(n\log n\log )\)

但随机的 \(\log\) 常数较大，据说能被卡（

10.3

D. 小D与圣诞树

一开始没看到初始所有颜色不同，发现不会打暴力，由于只有修改到根链上的颜色为新颜色，因此每种颜色的点能组成一条路径

考虑点 \(u\) 到根链上的颜色数 \(f_u\)，即考虑多少个点与父节点颜色不同，这样路径查询也可以变成 \(f_u+f_v-f_{lca}\times 2+1\)

路径修改考虑树链剖分，在每条重链上相当于区间推平，可以用 set 维护连续段

查询子树中 \(f\) 的最大值，可以在维护连续段的过程中，用线段树维护 dfs 序一段区间 \(f\) 的最大值，要支持区间加减，区间查询，每次修改颜色时，先去掉原来的段的交界处对子树 \(f\) 的贡献，再加上新的

根据颜色段均摊，总共只会增加 \(O(q\log n)\) 段，复杂度为 \(O(q\log ^2 n)\)

10.6

A. CF1503E 2-Coloring

这种题肯定考虑刻画合法方案的形态，发现蓝色格子是上下两个单峰形状，有两种情况，一种是两个峰不挨着，另一种是上面峰的最左端紧靠着下面峰的最右端，或反过来上面的最右端靠着下面的最左端

第一种情况，上下独立，直接分别枚举上下中最大值最靠右的，最靠左的，不挨着就行，不是峰的位置就形如不降子序列的计数，最后前缀和优化一下

第二种情况同理，直接枚举交界的格子，用组合数算方案

注意对称性，两边如果只枚举上最靠右下最靠左记得乘二

赛时怎么只记得把第二种情况 \(\times2\) 啊，还死活看不出来啊

D. 棋盘

赛时看到矩阵乘法优化，直接一眼鉴定为转置原理，然后不会求逆，最后发现由于它的变换不是形如「某一行全部加到下一行」这种有先后顺序的操作，可以看作把矩阵复制一遍，再杂乱地执行很多次把原矩阵的一行加到新矩阵的某行这样的操作，无法用转置原理去求逆

好像有人告诉我本质原因是转移矩阵不是初等矩阵？不知道啊（

不过分析询问的性质，可以看作是先预处理处整个棋盘，询问的区间左端点，右端点均不降

转移矩阵中只有 \(O(n)\) 个非零元素，可以 \(O(n^2)\) 完成一次乘法

每次弹出左端点，如果维护了后缀信息就能直接做，加入右端点，维护了前缀信息就好了

于是用两个栈，左边栈维护从栈底位置开始的后缀信息，右边维护从栈底开始的前缀信息

唯一的问题是如果左边栈空了，就无法继续弹出

那暴力把所有元素放到左边，发现这样每个元素最多被重构一次，复杂度均摊还是 \(O(qn^2)\)

我只不过多存了一行的信息，导致转移矩阵大小 \(\times 4\) 既被卡时间又被卡空间，后来发现这种做法只需要把前一个、前两个转移矩阵都乘一下，代表从前一行、前两行转移，加起来就好了，分界点处维护相邻两种分界点……

10.21

B. P10093 [ROIR 2022 Day 2] 礼物

枚举第 \(k\) 大的数是多少，把 \(\ge\) 它的数看成 \(1\)，则区间内包含 \(k\) 个 \(1\)

从大到小加入数，每加入一个数就处理包含它的区间

那么每次只需处理 \(O(k)\) 个区间，然后用 ST 表维护区间最值，链表维护每个数的前面、后面一个已经加入的数

复杂度 \(O(nk+n\log n)\)

D. QOJ 6473 Cat and Mouse

直观的理解是 Cat 开始在 \(1\) 号点，Mouse 开始在 \(x\)，Mouse 先移动，要操作 Cat 的移动，在尽可能少的步数内使得 Mouse 无路可走

可以朴素设计 \(f_{x,y}\) 表示 Mouse 在 \(x\)，Cat 在 \(y\) 时最少移动步数，加上转移均摊复杂度为 \(O(n^2)\)，据说设计 A* 跑 BFS 可以通过？

发现 Cat 不在 Mouse 的相邻点或不是它下一步走的点时，它根本不会影响 Mouse 的移动，而且此时 Mouse 不会自己停止，设状态二元组为 \((x,u)\)，所以只有 \(F(x,x)=u\) 时是关键的，注意状态中 Mouse 即 \(x\) 先走，初始为 \((X,1)\)

这之后 Cat 一直会贴在 Mouse 的旁边，否则重新让 Mouse 自由移动不优，就有两种情况：

• Cat 在 \(u\)，一直跟着 Mouse 移动，\((x,u)\to (F(x,u),x)\)
• \(u\) 在 \(x\) 的移动方向上，使 \(x\) 转向，Mouse 移动至 \(w=F(x,u)\)，目标状态为 \((x,w)\)

剩下的问题是构造一种步数最少的方法，首先存在方案的条件是 \(F(w,w)=x\)，否则 Cat 追不上 Mouse，Cat 先在 \(u\) 不动，下一步 Mouse 到了 \(F(w,u)=x\)，Cat 再到 \(x\)，到达状态 \((x,x)\)

分类讨论 \(F(x,x)\) 的取值，根据上面的情况它只有两种可能：

• \(F(x,x)=w\)，此时最优情况下 Cat 移动到 \(w\)，到达 \((w,w)\)，然后不动即可到 \((x,w)\)，加上前面共花费 \(4\) 步
• \(F(x,x)=u\)，会到达 \((u,x)\)，但 Mouse 本来就是从 \(u\) 走过来的，让它返回不如早拦截，且若 \(u\) 不是第一格可以实现在早一格拦截，否则直接换一种相邻状态更优，舍去

于是把关键状态之间连边，跑最短路，点数和边数都是 \(O(n)\) 的，可以直接做也可以用桶维护最短路长度

最后枚举走了 \(i\) 步第一次到达关键状态，由于之前 Mouse 的移动不受限制，可以确定它的位置 \(p\)，枚举邻居即 Cat 的位置 \(q\)，此时若 \(q\)

为 \(p\) 的父节点则 \(dep_q-1\) 步走到即可，否则为了保持和 Mouse 之前错开，需要 \(dep_q\) 步

好像朴素枚举邻居虽然跑的很快但复杂度有点问题，不过这里应该就能随便优化了（

总复杂度为 \(O(n)/O(n\log n)\)

10.22

C. 歌剧演员

首先设计 DP，观察如果固定了某个空隙中的 LIS 对答案的贡献是哪一段，即要接在它前后哪两个数中间，则空隙中尽量使这段 LIS 最长最优

而且如果确定每个空隙的贡献，则它们产生贡献的值域不交，可以统计贡献

设第 \(i\) 个数前面有 \(a_i\) 个空隙，值 \(\le i\) 的有 \(s_i\) 个没确定位置，\(f_i\) 为序列第 \(i\) 个确定的数是 LIS 末尾时 LIS 最长长度

\[f_i=\max_{j<i,p_j<p_i}f_j+ \min(a_i-a_j,s_{p_i}-s_{p_j}) \]

拆开 \(\min\)，即强行钦定一个更小，则转移是三维偏序，用 CDQ 分治优化即可

10.23

啥逆天 4h 场三个 DS 一个神秘数数……

B. P7172 [COCI2020-2021#3] Specijacija

我赛时想出了大力 \(O(n\log^2n)\) 维护法，就是关注每个点在第 \(i\) 层是从左往右第 \(x\) 个，每个 \(a_i\) 相当于一次操作，若 \(x>a_i\) 则 \(x\gets x - 1\)

显然一次操作代表的变换是个只有两段的分段函数，\(n\) 个操作是有 \(O(n)\) 段的分段函数，大力使用线段树维护区间 \([l,r]\) 内的操作复合后得到的分段函数

每个节点只用存储哪些点处后面的函数值要 \(-1\)，相当于差分，建树时再用一棵线段树维护函数每个位置的取值，要线段树上二分找到第一个 \(>a_i\) 的位置，之后后缀减 \(1\)，处理完后撤销操作就避免了重新建树

查询时二分找出前面有多少个 \(-1\) 处即可得到经过区间内操作后的值

先查询一次，将 \(x,y\) 拉至同一层，然后在维护操作的线段树上二分，找到 \(x,y\) 经过变换后第一次相同的位置即是 lca

赛时最后的线段树二分没及时剪枝变成 \(O(n\log^3n)\) 了，赛后改对了，LG 上喜提最劣解（

官解是注意到分岔点只有 \(O(n)\) 个，只需要求出叶子构成的虚树的树，把每个点放到对应的链上，求对应点的 lca

从下往上可以维护出每层每个点所属的链底部节点，每层相当于下一层只做了删除一个数，修改一个数，还要支持查询第 \(a_i\) 个，由于强制在线使用主席树维护，注意特判两个点在同一条链上的情况，lca 是深度更浅的点，复杂度 \(O(n\log n)\)

D. QOJ5020 举办乘凉州喵，举办乘凉州谢谢喵

先考虑 \(y\) 为 \(x\) 祖先的情况，这种去掉一个子节点的计数一般先考虑重链剖分，设 \(g(x,d)\) 为 \(x\) 除重儿子子树外 \(x\) 子树内距离 \(x\) 为 \(d\) 点的数量，\(f(x,d)\) 为 \(x\) 子树内距离 \(x\) 为 \(d\) 点的数量

那么答案是路径上点的 \(g(\star,d)\) 之和，再特殊处理路径上轻重链切换处的答案，是新重链底部的点 \(u\) 的 \(g(u,x)\) 加上它重儿子的 \(f(son(u),d-1)\) 减去路径上前一个点即上一条重链的链头 \(v\) 的 \(f(v,d-1)\)

子树外的贡献则是对 \(y\) 做邻域数点，去掉 \(f(y,d)\) 即可，邻域数点使用点分治，维护每种深度点数量的前缀和即可 \(O(n\log n)\)

考虑计算 \(f(\star,d)\)，显然询问有 \(O(q\log n)\) 次，离线到每个点上使用启发式合并容易做到 \(O(n\log^2n)\)，但这里的信息与深度有关，考虑长链剖分，维护每种深度点数量的后缀和，就能方便地完成在长链前端增加一个数和查询的操作，复杂度瓶颈为查询，\(O(q\log n)\)

最后则是一条路径上 \(g\) 的和，由于所有节点轻子树大小为 \(O(n\log n)\)，将询问拆成两条到根的路径相减，dfs 的过程中直接暴力加入当前点轻子树，回溯时撤销就得到了到根路径上 \(g\) 之和，复杂度 \(O(n\log n)\)

于是整道题复杂度 \(O((n+q)\log n)\)

10.24

C. 换猫

首先我不知道需要知道结论，如果按顺序依次给每种字符交替赋值为矩阵 \(A_c,A_c^{-1}\)，则区间合法的充要条件是区间矩阵乘积为 \(I\)​

给每种字符随机一个可逆矩阵即可，这里取 \(2\times 2\) 正确率就足够了

每次交换的两个位置 \(l,r\) 会导致 \(l,r\) 处矩阵产生改变，\([l+1,r-1]\) 内矩阵变为原来的逆矩阵

设矩阵前缀积为 \(pre_i\)，后缀积为 \(suf_i\)，将矩阵变成原来的逆矩阵后的前缀积是 \(pre'_i\)

则交换后序列乘积是 \(pre_{l-1}\times A_r\times (pre'_l)^{-1}\times pre'_{r-1}\times A_l\times suf_{r+1}\)

枚举 \(l,r\) 分别对应的字符，则 \(l,r\) 剩下的矩阵乘积可以分开，维护每种矩阵出现次数，用哈希值存储即可

时间复杂度 \(O(|\Sigma|^2n\log n)\)

D. 爱丽丝猫

环上并不好做，考虑断开的位置，发现最大值比较关键，它所在的段的两边是独立的，考虑这个环的形态，如果钦定最大值后面接顺时针方向的数，则它逆时针方向的一段可以看作去除不选

因此把最大值放在序列最前面，逆时针、顺时针把环拉成链各做一遍，取最大值即可

然后设 \(f(i,j)\) 表示前 \(i\) 个数分成 \(j\) 段的最大值，维护单调栈，可以用线段树维护最大值做到 \(O(nk\log n)\)

做到 \(O(nk)\) 可以继续对这个东西优化，维护这个最值可以用链表维护差分配合并查集找到下一个在链表中的数，做到 \(O(nk\alpha(n))\)

重新考虑单调栈，单调栈中的数单调递减，将它抽象为树结构，每个点的父节点是将它从单调栈中弹出的点，树是动态构建的，此时单调栈中的每个点都作为根

则以点 \(x\) 为新划分区间左端点时，新区间前缀最大值个数是 \(x\) 到根的距离，后缀最大值个数为 \(x\) 的根到单调栈顶部数的个数

这些最大值可以在单调栈弹栈、入栈的时候维护，具体地，维护单调栈中 \(x\) 子树中 \(h1_{x}=\max \{g_y + dep\}\)，\(h2_x=\max g_y\)，单调栈上前缀 \(f1_x=\max\{h1_y\}\)，\(f2_x=\max\{h2_y\}+dis_x\)，其中 \(dis_x\) 为 \(x\) 到栈顶距离，复杂度 \(O(nk)\)

标签：2024.10,log,复杂度,矩阵,笔记,Cat,维护,Mouse
From： https://www.cnblogs.com/KellyWLJ/p/18509349