二分+DP优化：CF1550E
二分+dp优化：CF1550E
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135117074
https://www.luogu.com.cn/problem/CF1550E
一眼二分，然后有个朴素dp， 表示在 位置满足已经存在 是否可行。发现记录的值只有0 / 1，直接状态如dp， 表示满足 的最前位置。
继续优化。状态明显不可以优化，只能优化转移了。这种东西的转移显然预处理，只是看预处理在二分里还是二分外。因为二分里能够接受，那么就在二分里面预处理。直接处理一个 表示从 开始颜色 出现连续 的最左右端点位置。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2023-12-02
二分+DP：[ARC120E] 1D Party
二分+dp：[ARC120E] 1D Party 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134754875 https://www.luogu.com.cn/problem/AT_arc120_e 考虑二分时间，然后设 dp(i,0)dp(i,0)dp(i,0) 表示第 iii 个人开头往左走，掉头后剩余步数。 dp(i,1)dp(i,1)dp(i,1) 表示第 iii 个人先往右走，最多走多少步就有掉头。 然后在纸上画一画就是小学的相遇问题，直接转...
2022-02-15
【一本通OJ 1603：绿色通道】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15897506.html 题目链接 题目 高二数学《绿色通道》总共有 nnn 道题目要抄，编号 1…n1\ldots n1…n，抄第 iii 题要花 aia_iai 分钟。小 Y 决定只用不超过 ttt 分钟抄这个，因此必然有空着的题。每道题要么不写，要么抄完，不能写一半。下标连续的一些空题称为一个空题段，它的长度就是所包含的题目数。这样应付自然会引起马老师的愤怒，最长的空题段越长，马老师越生气。 现在，小 Y 想知道他在这 ttt 分钟内写哪...
2023-09-27
贪心+二分+DP+矩阵快速幂：CF461E
贪心+二分+DP+矩阵快速幂：CF461E 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133316261 https://codeforces.com/contest/461/problem/E 第一步：捕捉题目信息 四种字符 →\to→ 矩阵 n≤1018→n\le 10^{18}\ton≤1018→ 矩阵快速幂 →\to→ dp 最小值最大 →\to→ 二分 第二步：分析性质 sss 未知？那如果已知怎么做，肯定是每次暴力选最长的。 ...
2024-08-20
8.20T1 星图（拆贡献+DP+暴力卷积）
8.20T1 星图（拆贡献+dp+暴力卷积） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/141361722 http://cplusoj.com/d/senior/p/NODSX2301A 给定 nnn 个实数的取值范围，求其笛卡尔树节点深度总和的期望。 场上搞了一大轮区间dp，结果大方向就错了。 拆贡献，考虑 jjj 对 iii 是否有贡献。若 jjj 对 iii 有贡献，则 jjj 是 iii 的祖先，此时贡献为1。所以我们只需要计算 jjj ...
2021-12-04
2021.12.4 上课笔记（DP专题）
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15640975.html cf1110e 给定一个序列 A{}，每次可以选择 1 < i < N 的一个元素，更新 Ai=Ai−1+Ai+1−AiA_i = A_{i-1} + A_{i+1} - A_iAi=Ai−1+Ai+1−Ai。 问是否可以是序列 A{} 变化得到序列 B{}。 判断差分、首项是否相等即可。 poj1191 题面 对于式子中一些没影响的东西去掉，原式就是求 ∑n2a2−n(∑aj)2\sum n^2 a...
2022-01-14
【P2014 [CTSC1997]选课】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15802233.html 题目链接 题目 在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有 NNN 门功课，每门课有个学分，每门课有一门或没有直接先修课（若课程 a 是课程 b 的先修课即只有学完了课程 a，才能学习课程 b）。一个学生要从这些课程里选择 MMM 门课程学习，问他能获得的最大学分是多少？ 思路 对于没有祖先的，就连向一个虚点，...