幻影彭的彩虹

0927考试总结

考试

T1

题意超级钢琴。

真的是非常经典的题目了，可以说是开创了处理同一个问题 \(1-k\) 优解的先河。

将解空间拆分成二维，枚举其中一维，考虑第二维的选择并计算答案，用 priority_queue 选择最优答案，选择答案后将当前的第一维按第二维剩下的情况拆分。

动态点分治也是一样的思路。

T2

非常经典的题目，严格递增转不降是经典套路，最优解一定取到每个数值也是经典结论。

本题保证数据随机，应该是需要利用随机序列单调上升子序列长度为 \(O(\sqrt n)\) 的性质，但实际上可以 \(O(n^2)\) 轻松通过。

哦，应该是考虑补集转化，然后考虑哪些点固定，然后 \(dp_i\) 表示第 \(i\) 个点固定的最优代价，转移只能从能完成 LIS 转移的点转移过来，中间合法的条件是要么大于右边要么小于左边，根据经典结论一定可以调整成一段和左边相等，一段和右边相等，然后随机的情况下转移点个数 \(O(1)\)，长度 \(O(\sqrt n)\)，总复杂度 \(O(n\log n+n\sqrt n)\)。

简单证明经典结论

假设有一种最优解包含了不是原有数的数。

考虑第一个不是原有数的数，如果它被调大了，那么把它调小成上一个原有数一定更优。

如果它被调小了，就把它调到第一个比调整后的数大的原有数的位置，如果因此导致后面若干个数小于它了，那么不难得知这些数现在都被夹在两个原有的数之间，而且都是从两个原有数区间的外面调整过来的。从左边第一个数开始，找和它相同的数，如果相同的数中，被调小的数较多，那么全部调到第一个和它不同的数，否则调回第一个原数，变成子问题。

T3

最大值最小显然二分。

考虑一个划分合法的条件，发现只能在某些合法的位置断开，而且在这些位置是否断开不影响第一个条件的合法性。

所以考虑对这些位置动态规划，直接转移是 \(O(n^2)\) 的，然后考虑维护所有可能的转移，发现如果拿个单调栈记录 \(a\)，那么转移的改变可以描述为 \(O(n)\) 次区间加，线段树维护即可。

一个数组，考虑每个前缀的后缀最大值，可以被描述为 \(O(n)\) 次区间加。

20220924 考试总结

考试

T1

中规中矩的动态规划题。但我选择读错题。

求最长周长可以用一列一列考虑，处理出每个点向上延申的最上面的位置，用单调栈维护这个东西，然后可以做到 \(O(点数)\) 处理。

T2

又是逆向考虑的标准题目。

考虑最终答案的直径，对于直径这种东西，它的中点是非常特殊的，因为从中心到两边的距离是相同的。

这道题又要最小化直径生成树，也就是最小化中心到两边的距离，那从中心到某个点最小距离的最大值恰好就是直径的一般，所以对每个点跑一遍 BFS，求出 BFS 树的直径即可。

不难得到一个结论：最小直径生成树的直径中点（有可能在一条边上）是图的绝对中心，其中图的绝对中心可以存在于一条边上或某个点上，该中心到所有点的最短路的最大值最小。

T3

算是套路的反向转对穿。

称将反向视为对穿后形成的局面为对照局面，那么对照局面的周期为 \(2L\)，故问题周期为 \(2L\)，转化为 \(T\le 2L\)。

考虑往回走比较恼火，转化为撞墙后继续走，然后有一个相同颜色的人在此时出发，即在最初在一个对应的位置准备出发，容易发现仍然没有两个点在同一位置。

扩大了 \(n,m\) 的范围以及数轴的考察范围，但是不用考虑转向了，难度实际上降低了。

由于有颜色差别，所以可以分出两种思考方向。

换衣服

两个 Heren 相遇后换衣服，从左往右依次考虑每个向左的 Heren，除了第一次之外，都是右边的 Heren 在相邻之间换衣服（向左的那个 Heren 和第 \(i\) 个换衣服之后马上和第 \(i+1\) 个换），相邻向左的 Heren 换衣服是可以快速计算区间答案的（或者说用扫描线后是均摊 \(O(1)\) 的）。

回到初始局面

考虑将对照局面的相遇和原局面的相遇，只需要求出相遇位置的排名，就可以对应回原局面的情况，注意从 \([0,L]\) 之外出发的点，是什么颜色其实并不重要，因为排名落在这些区间的相遇，一定在 \((0,L)\) 外面，注意是开区间，所以还需要妥善处理边界。

发现每一个向左的点的所有相遇事件，其位置的排名单调递增，对应的坐标也单调递增，回到原序列相邻元素是一个区间加。

思考这个方式的本质，和换衣服的思路没有太大差异。

敲下"相遇"的时候，差点又掉眼泪....

T4

考场上想到了处理移动相交转图上问题搞，但是相交关系比较多，这个思路走不动。

首先得发现一件事，如果用一个方向的移动完全可以移动完，证明考虑找左端点最靠左然后最靠上的，所以左端点一定不会被遮挡，然后如果这条线段被另一些线段遮挡，那么找到遮挡它的线段中左端点最靠左然后最靠上的，依次找下去，左端点递增，所以一定会找到一个不被遮挡的线段，移除它就行。

考虑构造一种方案，不妨要求必须往上移动，对每个方向分别求最早的一次不合法，其它情况可以转坐标系。

考虑求出一个方向上，遮挡限制关系构成的图，首先它一定是个 DAG。我估计我是想不到的，但可能确实平面组合几何问题应该考虑扫描线，由于线段不交，所以扫描线与对应线段交点的相对位置永远不变，用 set 维护扫描线即可，加入时会多出 \(O(1)\) 条边。这样构建出来的图是可以正确描述遮挡关系的，感性理解挺容易的，证明有点难写。

拓扑排序之后第二问做完了，第一问的话，如果出现了拓扑序较大的先被移动了，那么就是不合法的，但是需要注意拓扑序只是一个比较松的限制，还需要加上横坐标区间有交才是两条线段存在先后限制的充要条件，证明是显然的。

需要注意的是，这道题用了 set 去维护边，其中涉及到了浮点数的运算和比较，所以 erase 的时候需要考虑浮点误差。

声明和定义

正常情况下，函数的声明和定义可以分开写，如果函数参数有默认参数，写在声明或定义处都没问题，如果函数为模板参数，那么默认参数只能写在声明处

模板函数

模板函数用于将同一个函数对不同类型生效，一般来说，最好不要用 auto 来捕获，写模板函数才是正确的方式。

模板函数的声明和定义一般不能分开。

隐式指定

如果你想偷懒，就是调用的时候不想写 <T1,T2...>，那么你调用的时候必须能让编译器推断出每个模板类型参数是什么，而且同一种类型不能冲突。

这里需要注意字面量的类型问题。

注意，如果你使用了默认参数，那么调用的时候可能就无法让编译器推断出类型从而出现 CE。

template<typename T1,typename T2>
void add(T1 x,T1 y,T2 len=30);
add(1,1);//CE
add(1,1,30);//OK
template<typename T1,typename T2>
void add(T1 x,T2 y,T2 len=30);
add(1,1.5);//OK
add(1,1.5,30);//CE

类型参数捕获比较阴间的例子，可以发现它会先捕获"简单"的，不太想深究这个：

template<typename T1,typename T2>
void add(vector<T1> a,T1 b,T2 c);
add({1.5,3},1.5,5);//ok
add({1.5,3.5},1,5);//CE

显式指定

如果显示指定参数，那么会出现类型强制转换，和正常的函数调用完全相同。

例子就不举了，和正常函数没差别。

指针

常量指针

1 2	const int* p = &a; //指向常量的指针 int* const p = &a; //p 指向的位置不可变

T1

中规中矩的一道题，但是我的做法比较蠢。

考虑最终那些序列可以成为答案的方式没有问题，但是我考虑的条件是对于 \(a_i\)，大于等于它的数必须多余 \(n-i+1\) 个。这样需要记录的东西是 \(2\) 维的，然后转移还不是优雅的前缀和形式。实际上可以考虑 \(b_i\ge a_i\) 这个条件，也就是多想一想的事，这样的转移可以写成优雅的前缀和。

像这种转化后考虑条件的题，一定要找一个简易的条件去做。

T2

中规中矩的一道状压题。

我考虑直接爆搜联通块，但是这样的做法不是很优雅。转移时其实仅和当前选了哪些点有关，所以其实可以动态规划，做到 \(3^n\)，这种联通块相关的题，一定要考虑联通块之间有没有关系，能不能用动态规划搞定。

T3

中规中矩的一道数据结构优化动态规划的题。

一种比较经典的动态规划优化方式是拿数据结构维护可能的转移，这题本身有着比较优美的性质，可以将对转移代价的贡献拆成两个区间加。

对于修改独立的情况，如果要快速求出答案需要预处理序列，不妨考虑二进制分组。

T4

有意思的二分题。

最大值最小还是可以考虑二分的。

对于这种两者加起来不超过一个数的题，往往可以考虑每个数与 \(\frac{s}{2}\) 的关系。

这种题，显然最终的答案序列是很多个不超过 \(\frac{s}{2}\) 的，中间夹着不超过一个大于 \(\frac{s}{2}\) 的，所以容易证明不超过 \(\frac{s}{2}\) 的数是必选的，如果不选，一定可以调整过去。

然后二分之后需要 check 一下总个数。一个区间中存在合法的大于 \(\frac{s}{2}\) 的数，当且仅当最小值合法。但是如果真的要检查区间最小值个数，那是非常困难的，因为我们需要先得知每个区间的位置，这个位置个数是 \(O(n)\) 的。

所以不妨从合法的数本身的性质考虑，容易发现，合法的数，与它左右两边第一个小于它的数的和一定是小于 \(s\) 的，如果出现相等那么为了避免重复需要设一个第二关键字。

这样就可以做到 \(O(\log)\) check 了，对于两边的边界，可以特判掉。

我们发现需要 check 的东西形如 \([l,r]\) 中 \(\le x\) 的数的个数，这是整体二分擅长处理的东西，所以考虑整体二分，二分的时候将原来的有序组有序的分裂下去，就变成了一维偏序，而且不需要排序（已经有序了）。求左右区间端点也可以类似的做。

对于边界，可以用 ST 表特判，时间复杂度 \(O(n\log n)\)。常数比较大。

整体二分的卡常是有一些技巧的，比如巧妙处理归并，归并的同时分裂数组，通过下标分裂而不是 vector 等。

树上链领域修改问题

发表于 2022-09-21 更新于 2026-05-05 分类于算法竞赛

还没写完，估计是个论文级别的大坑

问题引入

NOI2021 中的《轻重边》，一种比较经典的解法是将操作视为点染色，然后处理相邻点颜色相同的数量得到答案。但还有一种真正的树链剖分做法，这种做法能够体现树链剖分的本质——将树划分成 \(\log n\) 条链，依次处理它们。

这一类题本质上都是树上邻域修改问题，即给定一条链，修改这条链的邻域。

单点邻域修改

条件：操作存在结合律。

给定一个点，修改其树上邻域。

这个是比较好做的，分两种情况讨论，操作是否存在逆元（且逆元容易求解）。

操作存在逆元

将一个点的操作视为两个部分，自身+父亲，对一个点的邻域操作时，在自身上打一个标记，暴力修改自己父亲的值，如果操作存在交换律则没有问题，如果不存在，则需要先得到父亲的真实值，然后操作后再放一个父亲的父亲标记的逆元。

共需进行 \(O(n)\) 次操作和求解逆元。

操作不存在逆元

如果操作只有结合律，那么会比较麻烦，如果是邻域赋值这类和之前的值无关的操作，可以记录一下每个点操作时间戳，清空一下树上标记，还是有救的。

如果和之前的值有关，并且查询只在最后做，那么可以开线段树记录一下

操作不存在结合律

没救了，暴力吧。

单点 \(k\) 阶邻域修改

树剖的优势

首先处理的操作必须具备结合律

首先处理在链上的情况是比较容易的，因为邻域只涉及额外 \(O(1)\) 个点，我们需要将这个优势拿到树上去。

考虑每次处理的 \(\log\) 条重链，对于每条重链，它只会在 \(top_u\) 处对其它，或者受到其它重链的影响。不妨将对一个点的修改放到两个地方，它自己和它父亲

某场考试总结

考完了一个月之后再来写总结也是没谁了。。。

考试

T1

简单题，随手构造出来就行。

可以加强，比如弄成质数个，或者干脆 \(10^{18}\) 个。

然而有个结论，考虑往一个字符串后添加 \(k\) 个 \(0/1\)，那么本质不同子序列个数一定可以写成 \(k(x-b)+x\) 的形式，其中 \(x\) 为该字符串的本质不同子序列个数，\(b\) 为上一个 \(0/1\) 前一个位置的答案。根据这个玩意来构造，不会太好做。

T2

发现本质不同子序列个数随 \(n\) 的增长近乎呈指数增长，猜想满足条件的不会太多，所以暴力处理即可。

实际上设 \(DP\) 状态，\(dp[i]\) 表示考虑到前 \(i\) 个字符，本质不同子串个数，有转移 \(dp[i]=2\times dp[i-1]-dp[lst[i]-1]\)，\(lst\) 表示 \(i\) 处字符上一次出现的位置。

于是设 \(dp[i][j][k]\) 为考虑前 \(i\) 个字符，上一个 \(0\) 处本质不同子序列数量 \(j\)，上一个 \(1\) 处本质不同子序列数量为 \(k\)，枚举 \(0,1\)，直接转移。

T3

我想的是折半之后爆搜，然后剪一下枝，比 \(std\) 快 \(5\) 倍。

确实也是折半，但是其实可以考虑偏序关系，两个 \((x,y,z)\) 三元组合并，不妨要求 \(x_1+x_2\le y_1+y_2\le z_1+z_2\)，然后值为 \(z_1+z_2-(x_1+x_2)\)，本质上是个二维偏序。

还可以剪个枝，强制要求 \(x_1\le y_1\le z_1\)。同样能对应上去。

实际上还可以发现强制要求 \(z_2\le y_2\le x_2\) 也没有问题，证明比较繁琐，故省略。

T4

很妙的一道题，我想的是，需要将相同城市联系起来，考虑它们在虚树上的关系，每个点需要和它倾向的所有点连边，然后实际上只会连 \(O(n)\) 条边，连好之后 \(tarjan\) 求下 \(SCC\) 就行。

有一种非常神奇的做法，考虑点分治，暴力求分治中心的答案，然后考虑其它点，发现之后的所有点的答案都不会跨过分治中心，可以暴力计算。

某场考试T2

比较套路的题，先弄出一个 \(t\times n^4\) 的凑合做，然后发现两维转移系数独立，转移答案为三角形和形式乘上两维系数，可以考虑固定第二维，单独计算第一维不同转移系数对应的式子，每一种系数的变化量为 \(O(1)\)，所以一次转移可以做到 \(O(n)\)。

某场考试T3

神仙题，考场上猜到树一定有解，但是想的是通过背包来构造解，事实上，可以归纳的证明每棵子树带来的差异可以取 \([-sz_u,sz_u]\) 中的任意值，所以对于树暴力构造一条从根到某个点的路径，可以满足路径两边大小相等。

考虑图上的结果。

09 年的一篇集训队论文告诉我们对于图上的问题，往往可以考虑其生成树的解法，从而进行拓展，发现无向图的生成树没有横插边，所以直接选取生成树上的答案，由于没有返祖边，所以原来合法的同样合法。

某场考试T4

也是比较套路的题。

很明显本质上是给你个一次函数做路径边权，然后 \(k\) 的值为 \(1\)，所以计算出每个点每个 \(k\) 的值即可。

我选择分层图跑 \(dij\) 外加大力卡常，但这是一种非常 \(SB\) 的行为，\(dij\) 本质上还是保证了转移的无环性，但 \(TM\) 这个转移本来就无环还跑你大爷的 \(dij\)，暴力 \(dp\) 出来做凸包就行。

然后从 \(n\) 的各个在凸包上的 \(k\)，倒推回去看那些点可能被用到，倒推可以写成记搜，这样只用存一遍边。

某道 GCD 题

给一个 \(n\times m\) 矩阵，元素为 \(1-n\times m\) 的排列，问你所有子矩阵的 GCD 之和。

反正我想的是考虑一个右下角，移动左上角来统计答案，这样的话考虑到 gcd 的变化次数是\(\log\) 的，说不定有救，但是需要完成区间取 GCD，这个不好做。

想一下，这个做法没有利用到每个数只出现一次的性质，通常这种只出现一次的性质往往和倍数这些相联系，不妨换个思路考虑，考虑 \(i\) 的倍数的子矩阵的数量，然后发现容斥一下就可以得到答案。统计 \(i\) 的倍数的子矩阵数量不难。

NOI2021D1T1

我想了一下，链是会做的，树链剖分，就是把树变成 \(\log\) 个链来做。

然后其实每条重链按照链的方式来做，重链的交汇处需要特殊处理。

不妨把边下放到点，发现如果一个点的父亲的修改时间晚于该点的修改时间，那么这个点所代表的链就没用，所以对每个点维护两个东西，一个是该点的修改时间，另一个是该点代表的边是否被修改成重边。

查询的时候对链的交界处需要查修改时间判断是否有效。

其实有个更简易的方式，就是把修改看成染色，一条边有贡献当且仅当其两个端点颜色相同，这个很容易用树剖维护。

这两种方式其实体现出处理边的两种方式——下放到点考虑，考虑两个端点的状态。

需要灵活运用这两种方式解题。

随记20220904

双膝折叠，跪坐在算不上柔软的沙发上，两臂枕在凸起的窗沿。我有些懒散的将下巴靠在小臂，又竭力不让窗沿压迫小臂，以免有些脆弱敏感的手部神经受到刺激，\(P=\frac{F}{S}\)，一个非常优美的公式。我开始估算手臂和窗沿的接触面积，我脑袋的半径，以便带入人体平均密度计算出手部受到的压强相当于几个大气压。

不得不说，物理和数学公式都是优美的，只需要用上统一的几个名字，就能尽情将身边的一切等效。或者说，公式本身不够优美，但是人们设计的物理单位是那么的精巧，避免了那些繁杂的常量，一些无比熟悉的数字又飞入脑海，\(e\approx2.718\),\(\pi\approx3.1415927,G\approx6.67\times 10^{-11}m^3kg^{-1}s^{-2}\cdots\)。

将越跑越远的联想收回来，生活不是科学，生活不需要那些能精确到小数点后几十几百位的数字。生活的美感，是一种无法用任何数学语言描述的美感。

陶渊明的 “采菊东篱下，悠然见南山”，带来田园的悠然自得。

王维的 “大漠孤烟直，长河落日圆”，给出荒凉的独特答案。

马致远的 “枯藤老树昏鸦，小桥流水人家，古道西风瘦马。”，留下秋日的那份伤感。

但我只是一个平常的理科生，对感性的语文并不敏感，但窗外的宁静，也足以让我有感写下一些拙劣幼稚的文字。

我不知道今年的干旱具体给天府之国带来了多大的影响，但是从居民区的停电和学校的被迫放假还是能够管中窥豹。刚回到学校没多久，COVID 就横扫四川所有中学，没有一所逃过延迟开学的结局，即使是强硬如某校，也只不过多坚持了半天，就匆匆将神兽们赶了回去——就在高温假结束后的 2 天。

所以我就在这个时候，趴在了窗前，半夜的街道很冷清，只能听见百草路地铁口 “握紧扶手，注意脚下” 的提醒。目光向上 90度，我甚至能分辨出夜空中的云朵，它们和蓝色的天空还有一丝界限，但其实都很暗，它们一起向目光尽头的高楼收敛。如果你想具体的体会一下，你可以打开 mspaint，天的颜色是 0 60 85，云的颜色是 212 212 212，而它们收敛向 69 24 34。RGB 空间还是很无力，区区 3Byte 无法描绘出世界上的，甚至无法描绘出人肉眼可以分辨的所有颜色。

黯淡的云朵没有动作，视野的右侧有一颗明亮的光点，它是星星。按照不知道从哪里得知的观星技巧，我快速的扫过窗口狭小的天空，又有数十的光点在视野中闪过，但我尝试正眼捕捉，它们又藏入了深色的天空，像是一个个纯黑背景下的白色像素点，于缩放后在显存中被彻底删除，我再也找不到它们。即使有着凹透镜的帮助，变形略显严重的晶状体也失去了精确的将波长仅有 \(300-500nm\) 的可见光折射到每一个感光细胞的能力。

一段时间的沉寂后，波浪状的云遮住了唯一那颗被轻易捕捉到的星星，视野渐渐下移，移过 “立德树人” 四个大字，是熟悉的水泥路。很突然，沥青从路面翻起，回到工人的铲子，回到工程车辆，回到工厂，最后在分馏器中重新变成原油，再顺着磕头机的管道流入地底。远处的高楼被荒芜的草地替换，眼前的工地，正热火朝天。。。

又重归沉寂，只有略冷的风打在脸上，我看了看最近都在 1.5km 之外的高楼，并细细感受周遭的气温，思考着这股风的来历，但已经有些陌生的地理和物理知识不再能闪着光告诉我答案。

shutdown -f，我告诉大脑，但又用留在海马体里的数据恢复了这段文字，像是被设置了关机命令为休眠的计算机。

从2D1D到1D1D

发表于 2022-09-03 更新于 2026-05-05 分类于算法竞赛

从区间 DP 到线性 DP

题目

你有 \(n\) 个区间，每个区间是 \(l,r,w\) 三个参数描述，表示左右端点和权值，如果区间有交（包括端点），那么就在有交的两个区间连边，形成一张无向图，有个参数 \(k\)，你需要删去一些区间，使得每个联通块大小不超过 \(k\)。

\(n\leq 500\)
\(n\leq 2500\)

思考

首先这肯定不是一个图论问题，给一张图做这个问题是 \(NP\) 的，所以要利用好区间的性质。

先把区间离散化。

发现可以考虑一段区间 \([l,r]\)，只考虑在区间内的区间，计算其答案，有两种方式，第一种是将区间继续划分成两个子区间，划分区间的过程，体现出了全局最优的思想，即我们假定了当前区间内的所有线段全部联通，这样不一定能在此处取到最优解，但一定可以在向下动态规划的过程中得到最优解，另一种是直接在当前区间选最大的 \(k\) 个保留。

划分区间的方式，就是选一个地方断开，删掉越过这个地方的所有区间，变成两个子问题。

有了这样的思路，我们很容易设计出一个 \(O(n^3)\) 的区间动态规划出来。

优化

\(O(n^3)\) 可以通过 \(n\leq 500\) 的数据点，但是无法通过 \(n\leq 2500\)，所以需要优化为 \(O(n^2)\)，其中预处理 \([l,r]\) 的复杂度是 \(O(n^2\log n)\) 的，但是常数较小能够接受。

于是可以考虑利用区间 \(dp\) 的一些常见优化手段，打个表，发现决策点并不单调，所以对于这类 \(2D1D\) 问题我们有点束手无策。但是感觉上记录区间有点浪费，于是考虑能不能线性的搞出来。发现如果设 \(dp[i]\) 表示考虑前 \(i\) 个的答案，从 \(j<i\) 转移，\([j,i]\) 采用直接减少到 \(k\) 的方式，也能得到和区间DP方式相同的转移考虑。

所以被优化成了 \(O(n^2)\)。越过每个点的区间总数，是可以动态维护的，均摊 \(O(1)\)。

从2D1D到1D1D

其实这类问题，是伪区间DP问题，比较它和真区间DP问题，比如《石子合并》，《优雅的闪电》的差异。它本质上是 1D1D 问题，石子合并很明显就是需要体现区间合并的顺序，所以必须采用区间DP。优雅的闪电的转移，无法被 1D1D 的转移考虑完全，所以仍然需要区间 DP。

关于一些 2D1D 的问题，可以仔细考察它的转移，能否被 1D1D 的形式描述，以便优化。