by TheBigYellowDuck
CF11B Jumping Jack
由于左右对称，我们可以取绝对值，只考虑数轴正方向的做法。
设经过若干次向正方向的跳跃跳到了 \(X\) 的位置，分类讨论：
-
若 \(X=x\)，则已经达到了目标位置。
-
若 \(X>x\)，考虑 \(l=X-x\)，若 \(l\) 为偶数则让第 \(\dfrac{l}{2}\) 次向负方向跳跃就可以到达 \(x\)。
模拟扫一遍即可。容易说明这样是最少次数。
时间复杂度 \(\mathcal{O}(\sqrt{x})\)。
CF1276A As Simple as One and Two
简单题。考虑三种情况：
-
单独的
one出现，为了防止前面的o或后面的e补上来，删除中间的n即可。 -
单独的
two出现，同理删除中间的w。 -
出现
twone的结构，删掉中间的o就可以了。
时间复杂度 \(\mathcal{O}(n)\)。
CF631C Report
注意到一点：若存在操作 \(r_i\leq r_j\) 且 \(i<j\)，则第 \(i\) 次操作是无效的，因为会被第 \(j\) 次覆盖掉。
利用单调栈去掉无效的操作，这样能得到一个单调递减的 \(r\) 序列。
设 \(R=\max\limits_{i=1}^m\{r_i\}\)，则所有操作只会影响到 \([1,R]\) 的元素。我们把 \([1,R]\) 的元素升序排序，设排好序的序列为 \(b\)。
考虑处理单调递减的 \(r\) 序列。设上一次处理的操作为 \(r_i\)，这一次处理的操作为 \(r_j\)，容易发现：
-
若 \(t_i=1\)，则上一次是升序排序，所以最终序列 \([r_j+1,r_i]\) 这一段应该以升序填 \(b\) 序列的最大的 \(r_i-r_j\) 个元素。
-
若 \(t_i=2\)，则上一次是降序排序，所以最终序列 \([r_j+1,r_i]\) 这一段应该以降序填 \(b\) 序列的最小的 \(r_i-r_j\) 个元素。
这样就有了一个算法：从后往前确定最终序列，用双指针扫一遍 \(b\) 序列删除填好的元素即可。
时间复杂度 \(\mathcal{O}(n)\)。
CF468A 24 Game
带点诈骗的意味。
易知 \(n\leq 3\) 必然无解。
当 \(n=4\) 时，由于 \(1\times 2\times 3\times 4=24\) 成立。进一步注意到对于 \(n\geq 4\) 的偶数，都可以基于 \(n=4\) 的情况凑出 \(24\)，从 \(5\) 开始两两配对相减凑出 \(1\) 全部相乘即可。
当 \(n=5\) 时，由于 \(3\times 4\times (5-1-2)=24\) 成立。同理对于 \(n\geq 5\) 的奇数也全部成立。
时间复杂度 \(\mathcal{O}(n)\)。
CF906A Shockers
朴素模拟题。分别考虑三种情况：
-
对于没有被电击的演讲，把这句话中出现的所有字符标记为安全。
-
对于被电击的演讲，把没有在这句话出现的所有字符标记为安全。如果此时字符唯一确定就遭受过量电击
-
对于猜测，如果此时字符唯一确定而玩家猜测了安全的字符，就遭受过量电击。否则标记字符为安全。
每次操作过后，判断当前是否字符唯一确定。
时间复杂度 \(\mathcal{O}(|\sum|n)\)。
CF1110C Magic Stones
NOIP2021 T3 的结论（）
注意到 \(c_1\) 和 \(c_n\) 不能被修改，如果 \(c_1\neq t_1\) 或 \(c_n\neq t_n\) 直接错了，先特判掉。
考虑 \(c\) 的差分序列 \(d\)。发现对 \(c_i\) 操作就是交换差分数组中 \(d_i\) 和 \(d_{i+1}\) 的两项。
求出 \(t\) 的差分序列，只需要两个差分序列能够通过交换相等，这就非常显然了。
时间复杂度 \(\mathcal{O}(n\log n)\)。
CF455D Serega and Fun
分块。维护整块内的颜色出现次数。查询很容易维护，考虑一下怎么进行修改。
修改可以看作整体平移，只需要修改块头和块尾。考虑用双端队列装每个块，整块向后移位只需要弹掉队尾并把前一个块的块尾加入队首。
同时，std::deque 还支持随机下标访问，能够方便我们做不满整块的部分的移位。
时间复杂度 \(\mathcal{O}(n+q\sqrt{n})\)。
CF1555E Boring Segments
最小化权值极差，考虑把所有区间按权值排序，用双指针扫。
用跟这道题一样的思路，用线段树维护最小值。双指针扫的过程中，最小值为 \(0\) 说明还有位置没被覆盖上，需要扩展右指针。
仔细想想，会发现全覆盖上并不一定连通，比如 \([1,2],[3,4]\)。我们把右端点集体 \(-1\)，这样覆盖上但是不连通就会暴露出一些空点。当然 \(m\) 也要调整为 \(m-1\)。
时间复杂度 \(\mathcal{O}(n\log m)\)。
CF1242B 0-1 MST
考虑把所有 \(1\) 的边删掉，原图会断成若干连通块。那么答案就是连通块数量 \(-1\)。
完全图的边数有 \(\mathcal{O}(n^2)\) 级别，而我们只知道要断掉的 \(m\) 条。可以利用一个套路，将要断掉的边扔进一个 set，再用一个 set 维护还没有被合并的点。从任意一个点出发做 bfs，每次只合并还没有被合并的点。
这样就可以 \(\mathcal{O}(n\log n)\) 合并出所有的连通块。
注意实现细节。当你正在遍历一个 set 的时候，不能直接 erase 掉其中的元素，会 RE。可以拿一个辅助数组记下来要删哪些点，遍历结束一起删。
CF438D The Child and Sequence
典题。可以维护区间和以及区间最大值。取模操作直接大力取模，当一个子区间最大值比模数还小的时候就不用再向下递归了。
时间复杂度 \(\mathcal{O}(n\log n\log x)\)。
CF375D Tree and Queries
一眼树上莫队。然后是不是就做完了。
用 dfs 序把子树转成区间，对每个颜色开桶维护数量，再用一个桶 \(sum_i\) 维护出现次数 \(\geq i\) 的颜色数。加入和删除都易于维护了。
时间复杂度 \(\mathcal{O}(n\sqrt{m})\)。
CF1806B Mex Master
求 \(\text{mex}\) 的问题，先考虑能不能贪心。
发现序列中如果 \(0\) 不够多，那么我们把 \(0\) 插空放，答案就变成 \(0\) 了。具体地，如果 \(0\) 的个数 \(\leq\left\lceil\dfrac{n}{2}\right\rceil\)，我们就存在插空安排的方式让 \(a_i+a_{i+1}\gt 0\)。
现在序列中大于一半都是 \(0\)。我们同理来考虑 \(1\)。如果 \(1\) 的数量不够多，那么我们把 \(1\) 和 \(0\) 分开，中间插一个大于 \(1\) 的数作为分界，答案就变成 \(1\) 了。
只有当整个序列只由 \(0\) 和 \(1\) 构成时，答案才能是 \(2\)。特殊地，当序列全都是 \(0\) 是，答案为 \(1\)。
时间复杂度 \(\mathcal{O}(n)\)。
CF1806C Sequence Master
跟 MO 同学说这道题，发现撞了 ELMO 2016。
发现合法的好序列一共就以下几种情况：
- \([x,x]\)。
- \([2,2,2,2]\)。
- \([0,0,\cdots,0]\)。
- \(n\) 为偶数时有 \([n,-1,-1,\cdots,-1]\)。
考虑证明这件事情。
- 如果 \(a_1=a_2=\cdots=a_{2n}=x\)，则有 \(nx=x^n\)。直观感受，当 \(n\) 很大时，\(x^n\) 的增长速度会远大于 \(nx\)。只有当 \(n=1\) 时恒成立，且在 \(n=2\) 时存在 \(a_1=a_2=a_3=a_4=2\) 这一组解。
\[a_1+a_3+a_4+\cdots+a_{n+1}=a_2a_{n+2}a_{n+3}\cdots a_{2n} \]\[a_2+a_3+a_4+\cdots+a_{n+1}=a_1a_{n+2}a_{n+3}\cdots a_{2n} \]
- 当 \(n>1\) 时，不妨设 \(a_1\neq a_2\)，从而有
两式相减能够得到
\[a_1-a_2=-(a_1-a_2)a_{n+2}a_{n+3}\cdots a_{2n} \]因为 \(a_1\neq a_2\)，得到 \(a_{n+2}a_{n+3}\cdots a_{2n}=-1\)。类似地，可以得到 \(a_3,a_4,\cdots,a_{2n}\) 中任意 \(n-1\) 个乘积为 \(-1\)。从而有
\[a_3a_{n+3}a_{n+4}\cdots a_{2n}=-1=a_4a_{n+3}a_{n+4}\cdots a_{2n} \]得到 \(a_3=a_4\)，类似地得到 \(a_3=a_4=\cdots=a_{2n}\)。从而 \(n\) 为奇数时无解，\(n\) 为偶数时有 \(a_3=a_4=\cdots=a_{2n}=-1\)，进而得证。
这样好序列就有有限种情况了。枚举一下，找最小距离即可。
时间复杂度 \(\mathcal{O}(n)\)。
CF920E Connected Components?
1242B 的双倍经验。套路都是一样的，并查集多维护一个连通块大小即可。
时间复杂度 \(\mathcal{O}(n\log n)\)。
CF708E Student's Camp
很厉害的大力 dp 优化题。
由于每一行的格子相互独立，考虑设 \(d(i)\) 为 \(k\) 天之后消失 \(i\) 个格子的概率，从而有
\[d(i)=\dbinom{k}{i}p^i(1-p)^{k-i} \]令 \(P(l,r)\) 为 \(k\) 天之后只剩下 \([l,r]\) 格子的概率，则有
\[P(l,r)=d(l-1)\times d(m-r) \]设 \(f(i,l,r)\) 为第 \(i\) 行只剩下 \([l,r]\) 的格子且连通的概率。转移方程为
\[f(i,l,r)=\sum_{[l,r]\cap [l',r']\neq\varnothing} f(i-1,l',r')\times P(l,r) \]但是这样的状态数为 \(\mathcal{O}(nm^2)\)，一次转移复杂度 \(\mathcal{O}(m^2)\)，显然过不去。
枚举区间有交很难优化，考虑枚举无交，则需要满足 \(r'<l\) 或 \(l'>r\)。
转移方程为
\[f(i,l,r)=P(l,r)\left(\sum_{l'\leq r'}f(i-1,l',r')-\sum_{r'<l}f(i-1,l',r')-\sum_{l'>r}f(i-1,l',r')\right) \]维护三个求和号
\[F(i)=\sum_{l\leq r} f(i,l,r) \]\[L(i,x)=\sum_{l\leq r<x} f(i,l,r) \]\[R(i,x)=\sum_{x<l\leq r}f(i,l,r) \]转移方程就可以写为
\[f(i,l,r)=P(l,r)\bigg(F(i-1)-L(i-1,l)-R(i-1,r)\bigg) \]会发现此时的 \(F(n)\) 就是答案。
同时注意到，\(L(i,x)\) 与 \(R(i,x)\) 高度对称。只需考虑 \(L(i,x)\) 的处理，翻转一下就是 \(R(i,x)\)。也即
\[L(i,x)=R(i,m-x+1) \]由于 \(f(i,l,r)\) 可以对所有 \(x>r\) 的 \(L(i,x)\) 做出贡献，不妨记 \(S(i,r)\) 为所有右端点为 \(r\) 的 \(f(i,l,r)\) 之和。即
\[S(i,r)=\sum_{l\leq r}f(i,l,r) \]从而有
\[L(i,x)=\sum_{r<x}S(i,r) \]同时注意到
\[F(i)=\sum_{r=1}^m S(i,r)=L(i,x+1) \]所以我们可以只维护 \(S\)，一并计算出 \(F\)。
目前为止，我们得到了状态数 \(\mathcal{O}(nm^2)\)，转移复杂度 \(\mathcal{O}(1)\) 的做法。还需要继续优化。
考虑能不能更快地算 \(S(i,r)\)。我们把式子代入，将定值的部分提出来。
\[\begin{aligned} S(i,r)&=\sum_{l\leq r}f(i,l,r) \\ &=\sum_{l\leq r}P(l,r)\bigg(F(i-1)-L(i-1,l)-R(i-1,r)\bigg) \\ &=d(m-r)\sum_{l\leq r}d(l-1)\bigg(F(i-1)-L(i-1,l)-R(i-1,r)\bigg) \\ &=d(m-r)\bigg(\Big[F(i-1)-R(i-1,r)\Big]\sum_{l\leq r}d(l-1)-\sum_{l\leq r}d(l-1)\times L(i-1,l)\bigg) \end{aligned} \]到这里，发现只需要维护 \(d(l-1)\) 和 \(d(l-1)\times L(i-1,l)\) 的前缀和即可。
时间复杂度优化到 \(\mathcal{O}(nm+k)\)。
注意一些边界情况。\(f(0,1,m)=1\)，即 \(F(0)=S(0,m)=L(0,m+1)=1\)。
CF10D LCIS
考虑结合 LIS 和 LCS 的 dp 方式。
- 设 \(f(i)\) 表示以 \(i\) 结尾的 LIS，则有
朴素 dp 是 \(\mathcal{O}(n^2)\) 的，用线段树优化可以做到 \(\mathcal{O}(n\log n)\)。
- 设 \(f(i,j)\) 表示两个序列前 \(i\) 个与前 \(j\) 个的 LCS，讨论 \(a_i\) 是否等于 \(b_j\)，可以得到转移方程
时间复杂度 \(\mathcal{O}(n^2)\)。
我们尝试结合两种 dp 方式。设 \(f(i,j)\) 表示两个序列前 \(i\) 个和前 \(j\) 个且以 \(b_j\) 结尾的 LCIS。
考虑根据 \(a_i\) 是否等于 \(b_j\) 来转移。
- 当 \(a_i=b_j\) 时，枚举上一次的结尾 \(k\)，则有
- 当 \(a_i\neq b_j\) 时，我们不能选 \(a_i\)，则有
最终答案为
\[\max_{i=1}^m f(n,i) \]输出方案可以通过记录决策点解决。
时间复杂度 \(\mathcal{O}(nm^2)\)。
CF1187E Tree Painting
翻译一下题意，给无根树定一个根，使得每个点的子树大小之和最大。
这种根不固定的问题，不妨考虑换根 dp。
设 \(f(u)\) 表示以 \(u\) 为根的答案，考虑 \(u\) 的儿子 \(v\)，当 \(v\) 被提到根的时候，\(u\) 的子树大小会减少 \(sz_v\)，而 \(v\) 的子树大小会增加 \(n-sz_v\)。其他点子树不变。从而有
\[f(v)=f(u)+n-2\times sz_v \]时间复杂度 \(\mathcal{O}(n)\)。
定睛一看，诶？这和求深度之和的题一模一样啊？怎么会是呢。
考虑 \(u\) 在其到根的链上每个点的子树中都会做出一次贡献，而这些贡献恰好就是 \(u\) 的深度。所以这其实是五倍经验。
CF865D Buy Low Sell High
ABC250G 的双倍经验。
经典反悔贪心。
直接贪心，若第 \(i\) 天的价格比之前价格最小的一天 \(j\) 还要小，就在第 \(j\) 天买第 \(i\) 天卖。然而这样可能是错误的。如果 \(i\) 之后还有价格更高的一天，可能在之后卖会更优。
用一个小根堆维护所有没选择买的股票。当遇到一个新的股票价值 \(x\) 时进行两种决策：
- 如果 \(x\) 小于堆顶 \(y\)，选择不进行操作，将 \(x\) 存入堆中。
- 如果 \(x\) 大于堆顶 \(y\)，则应该进行反悔，买进 \(y\) 卖出 \(x\)，答案增加 \(x-y\)。而此时要将 \(x\) 存入堆中两次，因为后面的决策可以选择将 \(x\) 调整为不操作，也可以继续调整为买。
时间复杂度 \(\mathcal{O}(n\log n)\)。
CF1253F Cheat Robot
ABC250Ex 的双倍经验。
不妨先预处理 \(dis(u)\) 表示 \(u\) 到最近的充电站的距离。可以建一个超级源点，向每个房子连权值为 \(0\) 的边，跑一遍最短路就可以了。
把每条边的边权 \(w\) 换成 \(dis(u)+dis(v)+w\)，跑最小生成树，答案就是两点路径上边权最大值。
时间复杂度 \(\mathcal{O}(m\log m+n\log n)\)。
CF1092F Tree with Maximum Cost
换根 dp。先统计子树点权和 \(S_u\) 和点权总和 \(S\)。
令 \(f(u)\) 表示以 \(u\) 为根时的答案。当根从 \(u\) 换到 \(v\) 时，\(v\) 子树内的点的答案减少 \(S_u\)，\(v\) 子树外的点的答案增加 \(S-S_u\)，从而
\[f(v)=f(u)+S-2S_u \]时间复杂度 \(\mathcal{O}(n)\)。
CF817D Imbalanced Array
单调栈扫一下左右第一个大于/小于 \(a_i\) 的位置，算一下贡献即可。
时间复杂度 \(\mathcal{O}(n)\)。
CF1324F Maximum White Subtree
考虑把黑点换成 \(-1\)，我们要球的就是一个类似最大子段和搬到树上的东西。
考虑换根 dp。令 \(f(u)\) 表示 \(u\) 的答案，先通过一遍 dfs 求出根的答案以及每个点 \(u\) 向儿子部分的答案。第二遍 dfs 考虑 \(u\) 的儿子 \(v\) 的答案能否继承自 \(u\)。
如果第一遍 dfs 后得到 \(f(v)>0\)，说明 \(f(u)\) 中包含了 \(f(v)\)，那么就 \(f(v)\leftarrow\max\{f(u), f(v)\}\)。否则就有 \(f(v)\leftarrow\max\{f(v),f(v)+f(u)\}\)。
时间复杂度 \(\mathcal{O}(n)\)。
CF475D CGCDSSQ
固定左端点 \(l\) 时，随着右端点 \(r\) 的增加，\(\gcd\) 单调不增。这一点保证了二分的正确性。
用 ST 表预处理区间 \(\gcd\)。考虑把所有查询离线，枚举左端点 \(l\)，会发现右端点 \(r\) 在一段区间 \([r_0,r_1]\) 时 \(\gcd(a_l,a_{l+1},\cdots,a_r)\) 是同一个值，而这一段就会给答案产生贡献。这样就可以用类似双指针的思路，固定 \(r_0\) 二分 \(r_1\)，将区间 \([r_0,r_1]\) 计入答案。
时间复杂度 \(\mathcal{O}(n\log n\log a_i)\)。
CF295A Greg and Array
先在操作序列上差分，可以得到每个操作需要做的次数。再在原序列上再差分一次就行了。
时间复杂度 \(\mathcal{O}(n)\)。
CF1292B Aroma's Search
注意到 \(a_x,b_x\geq 2\)，坐标的增长成指数级，越靠后点的排布越稀疏。事实上，我们一共只能走到 \(\mathcal{O}(\log t)\) 个点。不妨先预处理出所有可能走到的点。
枚举从 \((x_s,y_s)\) 第一步走到 \((x_i,y_i)\)。由于 \((x_0,y_0)\) 方向的点更密集，而 \((x_{\infty},y_{\infty})\) 方向的点更稀疏，贪心地考虑，肯定是先向 \((x_0,y_0)\) 走，剩下还有时间就走回去。
时间复杂度 \(\mathcal{O}(\log^2t)\)。
CF1304C Air Conditioner
先把所有人按照时间排序。
考虑维护能达到的温度的上下界。如果从下界一直降温都过热，或者从上界一直升温都过冷，就不能满足当前的人。注意要用人的上下界更新全局的上下界。
时间复杂度 \(\mathcal{O}(n\log n)\)。
CF1322B Present
每一位拆开考虑，只需要求出有多少对 \((i,j)\) 满足 \(a_i+a_j\) 的第 \(k\) 位上是 \(1\)。如果有奇数对，答案的第 \(k\) 位上就是 \(1\)，否则就是 \(0\)。
由于 \(a_i+a_j\) 第 \(k\) 位上的值只与从低到高的 \(k\) 位相关。把 \(a_i\) 的后 \(k\) 位拿出来，设为 \(b_i\)。只需要找出有多少对 \(b_i+b_j\) 第 \(k\) 位上是 \(1\)。
如果没有进位，那么 \(b_i+b_j\in [2^k,2^{k+1}-1]\) 都是对的。如果有进位，要求 \(b_i\) 和 \(b_j\) 在第 \(k\) 位上都是 \(1\)，且后面还能再进上来一个 \(1\)。则有 \(b_i+b_j\in [2^k+2^{k+1},2^{k+2}-2]\)。
可以树状数组大力维护，时间复杂度 \(\mathcal{O}(n\log ^2 a_i)\)。
稳一点的做法是排序后用双指针扫。维护两个指针 \(l,r\) 表示合法的区间。\(i\) 从后往前扫，指针 \(l,r\) 从前往后扫。每一对会被统计两遍。
时间复杂度 \(\mathcal{O}(n\log n\log a_i)\)。
标签：log,记录,复杂度,CF,提交,mathcal,杂题,sum From： https://www.cnblogs.com/duckqwq/p/18132120