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