Spark
P6082
-
图是树状的
-
没有必要在向父亲走之后再回到其儿子
-
如果遍历一个节点的 n 个子树，会消耗 1+n 次次数（加一次进来）
-
令 1 节点进入限制是 inf
-
故对于一个节点，若它限制进入 k 次，那么最多遍历他的 k-1 个子树
-
设遍历 x 的子树并且回到 x 的最高收益 \(f_x\)
-
那么存在：
-
求解这个方程式，时间复杂度是 \(\mathcal O(N\log N)\)
-
再设 \(g_x=0/1\) 表示 \(f_x\) 的最优解是不是唯一的
-
那么存在：
-
同样的，这个也是上面的复杂度
-
注意 0 情况的特殊判断
-
在根节点处特判是从子节点来的答案0还是不巡回来的答案0
P1973
- 设活动按照时间排序
P4767
-
设 \(f_{x,p}\) 是在 \(x\) 处建立第 \(p\) 个邮局，1-x 村庄的最小距离和
-
那么存在：
令：
\[\forall x\in[0,n],y>x\quad f_{x,y}=\inf \]\[f_{0,0}=0 \]有：
\[f_{x,p}=\min_{0\le i<x}\{f_{i,p-1}+\sum_{i+1\le j<x}\min\{\lvert x_j-x_i\rvert,\lvert x_j-x_p\rvert\}\} \]时间复杂度是 \(\mathcal O(N^3)\)
-
考虑优化，注意到对于所有 \(j\in[i+1,x)\) ，\(\lvert x_j-x_i\rvert\) 的值是单调变化的
故这一部分可以单调队列优化掉
-
总共的时间复杂度是 \(\mathcal O(PN^2)\)
Exam 2024/03/12
T1
-
显然，当经过一个彩蛋时，必将其捡起来
-
之前做过一个关灯的区间 DP
-
这几乎完全等价于那个问题，只要把下落速度看成单位时间费用即可
-
设 \(f_{l,r,0/1,0/1}\) 是从最左/右开始，收集了 \([l,r]\) 内的所有彩蛋，并且最后在最左边/右边停住得到的最小费用，类似的 \(t_{l,r,0/1,0/1}\) 代表这样的用时
-
思考这样做为何是正确的，原因是我们回头可能只是因为这样的原因：
a x b c
其中 \(v_c<<v_c<<v_b\) 那么要先走 b 再走 a 再走 c
从递归的意义上说，本题所有的回头都是这个性质
-
存在：
T2
-
之前，使用 KMP 继承 fail 的性质和对顶栈解决了这个问题的简化版
-
现在，有多个字符串，可以把该过程放上 AC自动机，可以记录对于位置 x，遍历到的 AC自动机上的位置，删除后直接继续遍历，当找到一个 end 时，从对顶栈中删除这个串
-
如果，一个前缀子串被完全删除，从根开始遍历
-
注意 AC 自动机的建立优化，采用 BFS 并直接融合next和fail来避免遍历
-
Expected 100pts at 15:44
Exam 2024/03/13
T1
-
思考选定一个仓库专门存放 x 的费用：就是把其他的 x 搬过来，把别的货物搬走
-
在确定这个排列的过程中，这样算肯定重复计算了
-
网络流？
-
建模成功
-
共 \(n^2+3n\) 条边，\(3n\) 个点，时间复杂度 \(\mathcal O(3nmf)\) 其中 \(f=n\) ，即为 \(\mathcal O(3n^2m)\)
T2
题意是，合并两个集合，查找一个集合内的第 \(k\) 大数
-
可并堆？不行
-
平衡树？不行
-
启发式合并？可以，合并复杂度至多 \(\mathcal O(n\log n)\) 查询是可以先缓存答案的，总共就是 \(\mathcal O(n\log n+q\log n)\) 。能过。
Exam \(\pi\mathcal{Day}\)
T1
-
分析子结构，显然有子结构
-
做完了
T2
- kdt，记不得了
Date: 2024/03/15
P1973
完全想不到这么“暴力”的DP思路。
思考路径还原：
-
考虑等价安排活动的操作为划分元素为两个集合且不交
-
发现合法的划分序列中，两个集合的可选区间是间隔的：
不会出现两个不连续但是相邻的红色或者绿色区间，就是说，红色或者绿色区间一定交替出现
-
所以可以依次处理每个前缀，把它的一个后缀分配给一个会场，就可以解决了
-
但是如果直接维护答案，是不能转移的，因为我们发现此时没有最优子结构
-
这是因为信息不足，维护的状态不能覆盖整个状态空间
-
比如，你在前一个最小值最大的情况下，不一定直接推得下一个最小值最大，那是因为取的是最小值最大，最小值在你推导的时候是可以变化的，原先的最小值现在可能不是最小值，这时由于取不到这个更大的值，做些让步可能不会变劣，甚至由于少占用了一些资源会变优。
-
所以，必须确定要让步多少，对于这种问题，把答案直接加入状态进行枚举，能够简化问题甚至是把问题转化成判定问题
-
推演结束
Exam 2024/03/14
T1
-
如果称第一次阻碍一头奶牛的奶牛为直接阻碍
-
那么我们可以处理出谁是直接阻碍的
-
阻碍共两种类型
-
本行阻碍
-
其他行上的阻碍
-
-
可以发现，如果有两头奶牛行动路线交错，必然有其一阻碍另一个
-
谁阻碍谁取决于距离交错点的距离
-
我们把一个阻碍事件的发生时间定义为： \(t(x,y)=\min\{dist(cross(x,y),x),dist(cross(x,y),y)\}\) 并排序后一个一个处理，如果其中一个或两个已经被阻碍，忽略该事件，随后再建图，拓扑排序
-
这样做的复杂度是 \(\mathcal O(N^2\log N^2)=\mathcal O(N^2\log N)\)
错误的，这是因为使用这个发生时间不能刻画之前留下的路径，所以考虑：
先从不会受影响的部分出发，即先从左下角开始模拟
通过这种遍历顺序，可以确定当前交点的可行性
T2
-
不可能动态找出 LCA
-
试转化问题，求 \(\sum_{i=l}^r (dep[i]+dep[z]-path(i,z))/2\)
-
问题转换成，怎么高效求 \(path(i,z)\) ，容易发现如果换根，那么就等价于深度
-
LCT 不行
-
令 \(f_{x,y}\) 表示在根为 \(x\) 的情况下， \(y\) 节点的深度
-
可以发现转移时：
父亲那边不属于我子树的都要加1，我这边不变
-
可以转换为全部加1但是我子树再全部减去1
-
但是不能暴力维护这个数组，否则不会改变时间复杂度
-
所以可以把这个东西变成一系列的操作序列，需要 \(f_{x,?}\) 的答案时，就是要：
\[f_{x,y}=f_{1,y}+dep[x]-cover[y] \]化为:
\[\sum_{i=l}^r (dep[i]+dep[z]-f[1][i]-dep[z]+dep[i]+1)/2 \]等于：
\[\sum_{i=l}^r (dep[i]+1)/2 \] -
错了错了
-
但是我们可以按 DFN[z] 对询问排序，然后动态维护 cover[y] 换言之，不断执行：
-
全局+-1
-
子树+-1
-
深入向下或者向上退出
-
这样子均摊是对的
-
就是说我们每次移动完之后就求 depSum(l,r)+dep[z]*(r-l+1)+segSum(l,r)+(r-l+1) 的和除以2
-
-
不行不行
-
cover[y]
思考路径还原：
-
两个点 \(u,v\) 的 \(\operatorname {LCA}\) 的深度就是从根这两个点公共路径的长度
-
所以可以通过从根到每一个 \([l,r]\) 中点的路径加1的方式，最后从 \(z\) 出发就能统计到公共长度
-
但是这样就会需要每次清空线段树，过不去
-
发现对于同一个 \(z\) ，如果有多个区间询问关于这个 \(z\) ，它们满足可差分的性质
-
这样就无需删除之前的贡献。
-
在信息可差分的时候，可以通过前缀和避免从数据结构中删除
Date 2024/03/18
P4407
爆搜
P3966
模板
P4762
- 加入某串的逆串，这构成了回文
Exam 2024/03/19
T2
-
对于 \((a,b,c)\) ，他们都一定在一条链上
-
说， \(a\) 与 \(b\) （\(a\neq b\)）是 “\(k\) 彼此彼此”的，当且仅当他们的距离小于等于 \(k\)，若 \(a\) 还比 \(b\) “更加厉害”，则说 \(b\) 是比 \(a\) "下 \(k\) 彼此彼此"的
-
令每个点的权值 \(val(x)\) 指的是它子树的大小减去 \(1\)
-
对于一个点的所有 下 \(k\) 彼此彼此的点，那么可以树形DP求解
-
对于一个点的所有 上 \(k\) 彼此彼此的点，可以倍增求解
-
现在的时间复杂度是 \(\mathcal O(n^2+q\log n)\)
-
主要是 DP 很慢
-
试图离线询问
T1
-
背包问题
-
令 \(f_{i,j,k}\) 指的是前 i 个py中，花费j mn，k cream的答案
-
有
-
考虑优化
Exam 2024/03/20
T2
-
一棵树，树上每个点带颜色，给定非递增序列 \(w_i\) ，两种操作：
-
单点修改颜色
-
路径查询，令颜色 \(i\) 在 \(x\to y\) 上的出现次数是 \(ocr(i,x,y)\) 则答案
\[=\sum_{i=1}^n V_i\sum_{j=1}^{ocr(i,x,y)}w_j \]
-
-
sum[x]-sum[y] <> sum[x-y]
-
树上莫队
-
K，忘了
T1
-
可以预见，由于 \(\mathcal O(T^2)>\mathcal O(T)\) 必然不会出现可以无限赚钱的情况，肯定到某一个时间之后就必然亏钱
-
花费是不均匀的，现在可以思考如果确定旅行时间？
-
这样就可以去除时间的影响
-
现在能够求出最高的收益吗？
-
注意到必须返回 1
-
结论：在走的过程中只会转一个环，该环转一圈的平均收益最大
2024/03/21
T1
-
区间DP是可以做的
-
时间是 \(n^3\) 的，大大滴过不去
-
空间也被卡，但是无法转化为更低空间复杂度的 DP 问题，考虑不用DP
-
发现由于不能用浅色覆盖深色，所以有些更小的字母就形成一种阻碍关系
-
考虑最优方案是将整个区间先全涂上最小的颜色，然后再按照最小颜色分治
-
考虑证明：
-
如果不是先涂最小颜色，那么还有操作可以选择：
-
可以涂更浅颜色，这完全没有用
-
可以选择涂更深颜色，你不能跨越这些最小颜色的点
这时候的合法操作集是和上面最优策略操作之后的大小一样的，具有决策包容性
-
可以选择涂这些最小颜色的点，那还不如直接涂一整个区间
-
证毕
-
-
故可以分前后缀来考虑
-
ABCBDC
T2
- 最大流
T1
-
KMP 求出在所有前缀中 \(s_2\) 的出现次数
-
使用 manacher，前缀和维护前缀和区间和
T2
-
基环树？
-
可以有自环？
-
添加城堡，答案只减小不增大
-
可以发现每一步都是独立的
-
贪心的解决，算法是 \(\mathcal O(n^3)\) 的
T1
-
FJ 希望尽可能少的命令，所以应该尽可能把草聚集起来再搬运
-
随便选一个根
-
单考虑把草往上搬，不会对于同一条边下多次向上命令
-
单考虑把草往下搬，不会对于同一条边下多次向下命令
-
所以对于一条边，如果他下面子树里总数多了，肯定要经过一次向上
-
如果他下面子树里总数少了，肯定要下一次向下命令
-
推出，每一次一条边至多被下一次命令
-
对于命令顺序，可以先从下向上输出向上命令再从上向下输出向下命令
T2
-
不考虑贪心，这个肯定不行
-
没有二分单调性
-
太大，不能使用状态压缩 DP
-
感觉像网络流或二分图方面的问题
-
这个答案太不常规，考虑离散化之后枚举答案
-
通过最大流来判断可行性，这样由于这个图是一个单向的流图而且边都是单位容量，复杂度应该是较好的
-
不，有二分性
-
注意到不会有两个奔袭区间的尾端或首端重合
-
破环成链
-
令 \(f_x\)
存在：
\[f_x=\min_{l(x)\le i\le r(x)}\{f_i\}+1 \]- 可以利用单调队列优化，复杂度是 \(\mathcal O(n\log n)\) ，离散化是时间复杂度瓶颈
-
与最短路只有一点差距：把点按 \(k\) 分块，边一定是从上一个块连向下一个块的
-
图无环
-
用 \(k\) 分块，设方程
-
令 \(f_{x,i,y,j}\) 代表 \(x\to y\) 并从 \(x.i\) 入 \(y_j\) 出的最小花费
-
区间DP预处理 \(n^2\)
-
再分块，摊一下复杂度
-
区间DP预处理 \(n+n\sqrt n\) ，询问总 \(q\)
-
emm
-
咋复杂度就对了？
-
不行，空间搞不定
-
可以搞个倍增优化
-
那就不再分块了
-
复杂度是 \(k^2n\log \frac{n}k+q\log n\)
Spark.md Monthly Report: 2024 March
Remarkable Problems
P2573 [SCOI2012] 滑雪
注意到题目是求一个特殊有向图的最小生成树。
考虑 Prim 与 Kruskal 算法的精髓，实际上是考察了所有可能扩大生成树的转移，所选择的最小的一个可以扩大生成树的转移。
让我们考虑直接按照边权选取会发生的事情， 1-4-5 会被选择，实际上，答案应该是 1-5-1 。这是因为，这种算法并没有考虑最下面那个节点的所有可能转移，实际上最下面 1 的那条边是不可以反向使用的，在正常的图里它可以扩大生成树，这个图里不能。所以前面我们这个转移是没有考虑完善的，我们没有考虑所有转移就草率地做出了决策，这就有问题了。所以，MST贪心的正确性，就是在于已经考虑了所有可能转移。
P4516 [JSOI2018] 潜入行动
是一道大背包
但是比较关键的Trick就是要利用子树的大小来限制转移的上下界，背包问题就是合并子树的贡献，跟启发式合并类似的，利用大的不会多的原理保证了合并的复杂度。
P8575 「DTOI-2」星之河
关键思想是把子树限制用DFN的大小关系来表达，然后转换成偏序问题，使用 cdq分治解。
由于DFN序是只有可能包含或者不交的，所以DFN大小的四维偏序可以转换成三维
P2466 [SDOI2008] Sue 的小球
关键技巧是 费用提前计算 。应该在作出当前决策的时候把对后续决策的负面影响计算在当前决策的费用中，避免了难以表出损耗的问题。
以上就是所有的书中对该技巧的解读。
我觉得，其实还不是能不能表的出这个问题，考虑暴力这个问题，在没有加入时间到状态时，你做的所有决策都是一个贪心式的纯考虑当前最优不顾全局最优的一种决策，之后你没办法用这种决策转移，因为它很可能不是全局最优的。把费用提前计算，就相当于加了一个状态，把它压到答案里，相当于是贪心了，把各个状态之间的干扰去掉了，比如我之前这个时间是要影响下一个转移的代价的，现在我先计算了，下一个状态可以看作是基于某个转移之后所在的一个新起点开始转移。对于DP，你子问题要有依赖关系，但是不能有干扰，就是要保证有最优子结构性质。
所以我认为不能叫做提前计算，因为这本来就是这个转移带来的代价，是后续要选择这个转移的代价，是在当前综合了全局的最优决策，这样做保证了有最优子结构性质，所以这个Trick更像贪心（所以这个题加一个时间维应该也是有正确性的）。
P3224 [HNOI2012] 永无乡
FHQTreap+启发式合并
总结两种可以把不可合并数据结构换成可并或者把不可在线数据结构换成在线的方法：
-
不可并换可并：启发式合并，复杂度多一个log
-
不可在线换在线：二进制分组
所以我们所说的暴力数据结构，就是在平衡操作次数和数据结构大小，而前者常与这个数据结构的数量有关（这令人想到根号分治），这种通常是元素数量是固定的时候才是对的（想想线段树合并）。
关键就是：
大的不会多，小的不会大
P7150 [USACO20DEC] Stuck in a Rut S
本题是按照“拓扑序”模拟。
这样就不必考虑已经转移的状态再被影响，这就是更新成环的情况。这个就是“无后效性”，其实上面第一题也有这样类似的想法。
P4211 [LNOI2014] LCA
首先把所有的贡献叠在一张图上可以看出答案就是 \(path(i\to root)\cap path(z\to root)\)
在信息可差分的时候，可以通过前缀和避免从数据结构中删除
P8903 [USACO22DEC] Bribing Friends G
这道题的关键在于要发现性质。。。
当问题困难的时候，思考通过枚举答案的方式转换成判断问题或者帮助发现性质。
可以发现如果确定了答案的集合，那么考虑调整答案的集合能否更优，发现答案集合中 \(x\) 较大的如果用了冰淇淋就完全可以把冰淇淋用在 \(x\) 更小的奶牛上面置换出一个mooney，这样既没有改变mooney的总数又节省了一部分冰淇淋，所以就可以推出冰淇淋一定是集中使用在 \(x\) 更小的奶牛上。
P6005 [USACO20JAN] Time is Mooney G
这道题体现了DP与SSSP问题之间的关系。
首先时间肯定是非常重要的一个状态（这点通过思考暴力容易得出），所以如果建成分层图就是分出若干时间层，此时已经可以做了，然后转成DP，也是自然的。
典中典 P2802 回家 和去年没做出来的 P9751 [CSP-J 2023] 旅游巴士
P3899 [湖南集训] 更为厉害
题面amazing啊
线段树合并的做法显然。
用DFN序转化为序列上问题，就得到了一个特殊的三维偏序问题，正如上面“P8575 「DTOI-2」星之河”的第一篇题解所说，DFN序的这种特殊的n维偏序是可以看作n-1维偏序做的。
P7300 [USACO21JAN] No Time to Paint S
本题中有贪心结论如下：
-
考虑最优方案是将整个区间先全涂上最小的颜色，然后再按照最小颜色分治
-
考虑证明：
-
如果不是先涂最小颜色，那么还有操作可以选择：
-
可以涂更浅颜色，这完全没有用
-
可以选择涂更深颜色，你不能跨越这些最小颜色的点
这时候的合法操作集是和上面最优策略操作之后的大小一样的，选择先涂最小颜色，这是具有决策包容性的
-
可以选择涂这些最小颜色的点，那还不如直接涂一整个区间
-
证毕
-
-
故可以分前后缀来考虑
然鹅之前的 P4170 [CQOI2007] 涂色 ,就是没有颜色深度限制的此题中，就没有这个性质。
这是因为题目的限制不够强，可能的转移决策不止这些，就是说你是可以跨越最小颜色的点，就是不满足了上面的决策包容性。仍然考虑可以节省操作次数的方法，就是要大段地涂上一个颜色把整个区间同一颜色的覆盖，可以发现先给一段区间涂上一个底色是没有影响的，之后答案不会变劣，还会变好，这里就颇有一种DP的感觉，就像上面那个 “P2466 [SDOI2008] Sue 的小球” 中我说的这样，这就是一种状态，做出这个决策之后不影响之后做出的决策，所以又想到DP就是优化搜索的枚举顺序，我可以先涂一个底色然后再进入小区间涂色，这不影响，然后小区间涂色的答案又能够组合成大区间的答案，只要我给他提供所有的可能性，枚举了所有的小区间划分，就行了，还有要注意到无后效性，我最少就只要2个区间就能拼成一个大区间，如果分三个那就可以组合其中任意两个，这就是为什么区间DP里面都是枚举断点。这就是递归地分析。
写不下去了，这个只能自行领会。抱歉用了太多逗号。
P3163 [CQOI2014] 危桥
其实这个交换两个点的方法可以这样理解：
-
第一次 \(a_1\to b_2\) ，错误的
-
第二次如果还是乱流，就是 \(b_2\to a_2\) ，那我就可以把第一次乱流的流量通过这条路径送到正确的 \(a_2\) ，这样不就行了吗？你可能会觉得万一路可以走的次数不够呢？那显然把两条路径合成一下就没必要重复走一段路了，就是这样：
P8900 [USACO22DEC] Barn Tree S
简单贪心，显然子树内如果能够自己补充自己那最好，基础的思想就是尽量堆积到一定量之后再移动干草。
P6573 [BalticOI 2017] Toll
可以发现每一次走一步肯定会到达下一层，所以要走几步到达目标层的步数是固定的，走一步是可以到哪里是可以知道的，这种一个大的转移目标可以由若干小的决策步数拼起来的，就可以适用倍增优化，当然，如果空间允许，这个问题也可以在层数上分块
标签：复杂度,sum,区间,mathcal,Spark,可以,DP From： https://www.cnblogs.com/haozexu/p/18299325