zhangxixi的博客

贪心+分类讨论完整性：ARC123C 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133772012 https://www.luogu.com.cn/problem/AT_arc123_c 场上就简单猜了个结论，[1,3]=>1, [4,6]=>2, [7,9]=>3，0=>4，若存在1则此时必须为1个数，否则为4。存在2则必须<=2，否则为4. 但我没对4进行完整讨论。如果4个数则不能凑3（此时可以判断是否进位，只有下一...

点向行列连边的网络流图优化成行列连边的二分图：CF1592F2 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133764633 https://www.luogu.com.cn/problem/CF1592F2 做完F1，然后用1的结论来思考。 场上推了几个性质。首先op4的操作行列必然两两不同，所以op4最多 max⁡(n,m)\max(n,m)max(n,m) 次。然后手玩发现只有除 (n,m)(n,m)(n,m) 的三个格子都为1，op4才有意义。 ...

区间dp之类似树形结构增加限制合并枚举状态：CF1107E 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133759674 https://www.luogu.com.cn/problem/CF1107E 场上想的思路是朴素 O(n5)O(n^5)O(n5) ，枚举区间和多少个0/1，转移则是枚举分界点和左边0/1数量 然后可以发现转移的 O(n2)O(n^2)O(n2) 似乎不那么必要（就是感觉上可以优化，但不知道怎么优化） 首先发现最后合并在一起的东...

归纳所猜半结论推出完整结论：CF1592F1 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133757947 https://www.luogu.com.cn/problem/CF1592F1 场上猜了个结论，感觉只会操作1。然后被样例1hack了。然后就猜如果 (n,m)(n,m)(n,m) 为1则翻转4操作，被#14hack了。然后就猜4操作只会进行一次，然后就不知道怎么做下去了。 上面猜的结论都正确，但是既然猜结论了，为什么不考虑先证明一波？ 考虑...

期望+拆贡献+充斥：CF1349D 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133753187 第一步：找性质 每个人的期望步数只与总数量 mmm ，总人数 nnn ，自己数量 aia_iai​ 有关 第二步：转化（难点） 拆贡献：拆成每个人win的期望步数，然后求 ∑E(i)\sum E(i)∑E(i) 容斥：肯定不能直接算。于是考虑算直到第 iii 个人拿完才结束的的期望步数 继续拆贡献：考虑具体容斥。就是算每个人对这个人拿完的贡献， ...

popcount相关性质+从低往高的数位dp：CF1734F 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133749334 https://www.luogu.com.cn/problem/CF1734F popcount有个性质： popcount(x)^popcount(y)=popcount(x^y) 考虑数位dp，发现很难 然后我们发现可以从低往高dp（当做套路） 只不过是否达到上界变成是否超出去 12345678910111213141516...

式子表达ds类——多用位置/值域表示未知数+区间覆盖转区间加：CF407E 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133749252 https://www.luogu.com.cn/problem/CF407E 多用位置/值域表示未知数 推出的式子中 nnn 表示长度，应该直接换成 r−l+1r-l+1r−l+1 区间覆盖转区间加 推出的式子有 mx,mnmx,mnmx,mn ，朴素思路是用单调队列+区间覆盖维护 那样就不能很方便地维护差 但既然都...

注意分类讨论完整性：CF1371F 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133745577 https://www.luogu.com.cn/problem/CF1371F 此题要分类讨论完全 容易漏掉 >>>>><<<<< 在左右或中间的情况 多对拍 123456789101112131415161718192021222324252627282930313233343536373839...

整数划分——DP 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133710641 用 jjj 个数表示 iii 的方案数，考虑dp 转移考虑最小值是否为1 无限制 若为1，则转移到 f(i+1,j+1)f(i+1, j+1)f(i+1,j+1) 不为1，则全部+1，转移到 f(i+j,j)f(i+j, j)f(i+j,j) 数之间不能重复 那么相当于每次整体+1 若为1，转移到 f(i+j+1,j+1)f(i+j+1, j+1)f(i+j+...

二维反射容斥：P9366 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133707260 https://www.luogu.com.cn/problem/P9366 构造循环矩阵，考虑反射容斥和将军饮马 考虑二维不太好做，我们曼哈顿距离转切比雪夫距离，变成一维的情况。 由于棋盘是正方形的，所以循环长度为 2n+42n+42n+4 。用多项式快速幂预处理，询问记得考虑正负两个方向。 123456789101112131415161718192021222...