zhangxixi的博客

善于拆约束条件+合并相关项+DS维护：0928T2 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133521713 http://cplusoj.com/d/senior/p/SS230928B 老套路了 考虑枚举0和2 m+j+min(fam−gaj,fbm−gbj)\large m+j+min(fa_m-ga_j,fb_m-gb_j) m+j+min(fam​−gaj​,fbm​−gbj​) 然后拆一下min，再分情况讨论一下，移项合并相同的 以其中一...

贪心找性质+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 转移过来。 然后这显然可以拿矩阵表示。 然后显然可以拿线段树维护。 后面三部分都是比较套路...

图论+博弈论上dp：CF536D 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133364509 此题其实比较板，只是我没看出来 首先肯定要跑个最短路，然后发现可以离散化把值域缩小 然后 nnn 很小，直接暴力列个 n2n^2n2 dp。 转移要注意的是必须从大往小dp。从小到大会产生后效性。 然后拿个双指针优化下转移就行。 123456789101112131415161718192021222324252627282930313233343536373...

博弈论（奇偶考虑法）+计数+DP（判定转dp）：CF838C 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133362167 首先题目有博弈，先分析一波最优策略（步骤：分析性质）。 两个人，所以显然考虑奇偶考虑法+递归考虑。 首先删就是使子问题-1，重新排列是在当前子问题里的。 一个串的排列是有限的，所以这里就可以上奇偶考虑法。如果有偶数种串，则必然是后手先“被迫“进入子问题（要算上初始情况） 考虑假设法：我们可以先假设进入子问题： 必赢。先手进！ ...

拆贡献与期望本质：CF1392H 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133355060 题目问牌数，但其实题面有另一个很明显的东西叫轮数 而如果我们每一轮单独考虑，其对应的期望牌数是确定的。 我们肯定会大胆考虑直接用期望牌数乘期望轮数，但为什么对？ 每轮牌数乘上前 i−1i-1i−1 轮未结束的的概率，后面的概率是第 iii 轮恰好结束的前缀和，而我们再求个和就是期望轮数。 考虑每一轮的期望牌数。首先肯定会抽到一种鬼牌，所以必然+1。然后考虑经典...

贪心+二分+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 未知？那如果已知怎么做，肯定是每次暴力选最长的。 ...

dp维护概率算期望+dp状态大小分析+dp状态维护前缀和：CF494C 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133343917 https://www.luogu.com.cn/problem/CF494C 首先无交，先建树，然后上dp，三个优化 dp维护概率算期望 发现期望很难直接维护，直接维护某种值得概率，最后乘起来算期望 dp状态大小分析 发现这样子第二维会很大。但其最大值范围只在 [mx,mx+q][mx,mx+q][mx,mx+q] 内，...

线性代数+分治：446E 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133336367 https://codeforces.com/problemset/problem/446/E 把官方题解翻译了一遍 考虑暴力，肯定想到dp，然后变成矩阵。设 用 代替 （这样子数之间的差值不会变化，但对于问题的处理能方便很多） 我们先令（也就是初始时的方案数） ，然后尝试构造转移矩阵 BBB BBB 的大小应该为 n×nn\times nn×n ，每个格子对...

分治常见Trick——启发式分裂+中间相遇法：CF1181E2 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133323437 https://www.luogu.com.cn/problem/CF1181E2 首先E1，也就是分治应该很好想 考虑到E2，首先看到题目是二维平面，有很多种分割方法，所以我们可以考虑拆维。 拆完之后我们考虑枚举分界点。枚举分界点暴力遍历过大，于是自然而然的，我们可以考虑中间相遇法。 但如果优雅的维护对应的集合呢？朴素思路使用s...

启发式分裂 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133321898 启发式分裂和启发式合并类似 对于一个数据结构，我们要对它进行分裂的时候，如果暴力拆成两个数据结构，很容易被卡 这个时候我们就可以考虑启发式分裂，把小的分出去，大的保留 在分治、set等题目中有广泛应用