zhangxixi的博客

本质子序列个数 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133885848 fif_ifi​ 设为 iii 结尾的方案数 假设每次遇到 kkk fk=∑fi+1f_k=\sum f_i+1fk​=∑fi​+1 之前的所有情况和空集都可以接 kkk 可以结合矩阵进行一些奇奇怪怪的操作

本质不同01序列dp方法 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133885358 设 ggg 为本质不同方案， f0/1f_{0/1}f0/1​ 为以0/1结尾本质不同子序列的方案。假设遇到数字 iii fi′=gg′=2g−fif'_i=g\\g'=2g-f_i fi′​=gg′=2g−fi​ 第一条式子： 对于原先每种情况都可以接或不接 iii ，不会重复，因为我们钦定必须加（ ggg 中包含空集， fff 中不含） 第二条...

分治类dp：1017T3 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133884752 http://cplusoj.com/d/senior/p/SS231017C 感觉可以分治某个区间 [l,r][l,r][l,r] ，且他们都是在下面 kkk 已经选的基础上 然后肯定要枚举最大值，最大值越长越好 Hint 1 Hint 2 f(l,r,k)f(l, r, k)f(l,r,k) 可以通过枚举 midmidmid ，或者枚举 k′k'k′...

状压dp：Gym - 102832J 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133855597 https://vjudge.net/contest/587311#problem/G 认真读题，然后发现就是让区间不交，要么包含要么相离，长度为偶数，直接状压 状压就状压10位就行。转移发现长度为偶数，所以可能填法只有 252^525 。总复杂度 O(n215)O(n2^{15})O(n215) 代码不长，就是有点难调 12345678910111213...

转化限制+分析变量变化引起的答案变化：Gym - 104065D 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133844333 https://vjudge.net/contest/587311#problem/H 先转化一波条件： pi≥1Xp_i\ge \frac 1 X pi​≥X1​ pi≤11−Yp_i\le \frac 1 {1-Y} pi​≤1−Y1​ 所以我们按 ppp 排序， sumxsum_xsumx​ 必然是后缀， su...

限制条件加入构造范围：Gym - 102832L 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133840957 https://vjudge.net/contest/587311#problem/D 场上列方程求首项，假设是全部加1，然后一部分（后缀）减去 k+1k+1k+1 ，就用到了以下两个条件： 但在这两种情况符合情况下， 这个条件不一定满足 然后就不会了 我们为什么不能把第三个条件也加入到方程里呢？ 我们发现用减的方法很容易弄成负数，我们就...

博弈论：gym104065j 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133840922 https://vjudge.net/contest/587311#problem/J 我也不知道我在此题中学到了什么套路 结论：你选的数必须尽量接近 sum3\frac {sum} 3 3sum​ ，然后这个就是解 因为另外两人选的是和你的数相比不可能更接近，所以必然一个大一个小 唯一的套路只能必有解博弈/构造和假设法？（3个人，从三进制角度盲猜一波，然后发现完...

奇偶博弈 + 二分图博弈：Gym 102832H 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133840132 https://vjudge.net/contest/587311#problem/I 赛时想了好久，啥都没想到 博弈，在你啥都想不到时，就硬上套路。赛时想了好久假设法，但就是发了奇偶博弈。 从奇偶角度考虑。每转一位会使这一位的奇偶性改变，也会使和的奇偶性改变。 然后关键地方到了，发现Alice和Bob操作的奇偶性永远不变，也就是形成了一个 ...

二分图博弈 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133840227 一张二分图，Alice和Bob每人走一步，不能重复走，谁不能走谁输 结论：若存在最大匹配不包含初始点，则Bob赢，否则Alice赢 以上图为例，红色为最大匹配。 首先对于Alice第一步只能走黑边。而Alice无论走到哪个点，都有一条红边。（不然就不是最大匹配了 ） 那么Bob就走红边，此时回到左边，Alice就只能走黑边了。 实现上，我们先把初始点去掉跑一遍流，加上后在残...

序列中排列存在类dp问题+结合组合数学和拆贡献：1014T4 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133833513 http://47.92.197.167:5283/contest/412/problem/4 赛时就想到枚举开头来拆贡献。 先说一下，对于A我们不关心具体的值，我们只关心哪些位置相等，哪些位置不等，最后乘上一个系数就行 然后对于序列是否存在排列类问题有个常见的dp套路，而且我们可以观察特殊性质 dpi,jdp_{i,j}dpi...