（口胡）DP+四边形不等式优化+矩阵优化：P8864
（口胡）dp+四边形不等式优化+矩阵优化：P8864
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135116753
https://www.luogu.com.cn/problem/P8864
一个经典套路，只是以前是用在差分上，现在是异或，所以我们设前缀异或和序列为 ，每次操作相当于交换 和 。区间内原先1的个数相当于 的段数。
我们考虑 中的1的连续段，可以是 段。我们显然可以设计一个区间dp来做，转移就是士兵站队，往中间站，预处理即可。
考虑优化。我们抛开段数，因为段数相当于是一层一层来枚举。决策单调性是显然的，我们要证明四边形不等式，也就是交叉小于包含。如果 或 有一个是0，直接取等。此处我们采用数形结合的思路：
最后那个dp是可以变成一个min+矩阵的形式。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2023-09-30
贪心找性质+DP表示+矩阵表示+线段树维护：CF573D
贪心找性质+dp表示+矩阵表示+线段树维护：CF573D 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133437456 比较套路的题目 首先肯定贪心一波，两个都排序后尽量相连。我一开始猜最多跨1，但其实最多跨2，考虑3个人的情况： 我们发现第3个人没了，所以可以出现跨2的情况 然后直接上dp，由 i−1,i−2,i−3i-1,i-2,i-3i−1,i−2,i−3 转移过来。 然后这显然可以拿矩阵表示。 然后显然可以拿线段树维护。 后面三部分都是比较套路...
2023-08-27
二分队列+决策单调性优化DP：P6246
二分队列+决策单调性优化dp：P6246 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132522515 https://www.luogu.com.cn/problem/P6246 决策单调性 若 dpidp_idpi 由 jjj 转移，则 dpi+1dp_{i+1}dpi+1 转移点 kkk 满足 k≥jk\ge jk≥j 发现决策点满足单调，但遍历的点不满足单调，不能用双指针，考虑二分队列。 二分队列 假设前 iii 个已定，只考虑从前转移到后...
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 未知？那如果已知怎么做，肯定是每次暴力选最长的。 ...
2023-12-16
决策单调性 =＞ 二分队列：P3515
决策单调性 =＞ 二分队列：P3515 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135033351 https://www.luogu.com.cn/problem/P3515 pi=maxj=1n(aj+∣i−j∣)−aip_i=\max_{j=1}^n(a_j+\sqrt {|i-j|})-a_ipi=maxj=1n(aj+∣i−j∣)−ai ， ppp 之间独立，直接拆绝对值，到时候reverse再做一遍即可。 拆绝对值后，显然具有决...
2023-09-17
数位DP+判定转状态：Loj #6274. 数字
数位dp+判定转状态：Loj #6274. 数字 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132950029 https://loj.ac/p/6274 和位运算有关，然后值域范围又非常大，位之间关联不大，显然考虑数位dp 然后有上下界限制，直接来个4维 然后每一位考虑，先满足or的性质，然后考虑and 发现有冲突只会是（1,0）和（0,1） 首先如果发生冲突，则要么无限制，要么上界为1，下界为0 所以某位0的以后不会受上界影响，某位为1以后不会受下界...
2023-11-14
枚举连通块拆贡献+容斥：ABC321G
枚举连通块拆贡献+容斥：ABC321G 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133266690 https://atcoder.jp/contests/abc321/tasks/abc321_g 这种题都没看出来我要去退役了 看完题目，可以获得： 期望、连通块：显然拆贡献啊！ n≤17n\le 17n≤17 ：这不明显状压？结合前面连通块，就是枚举连通块啊！ 继续分析第2点，17这么小，显然枚举子集。为啥枚举？计数题只有容斥这个套路啊！...