zhangxixi的博客

信息合并类+ST表：CF1707E 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134982534 https://www.luogu.com.cn/problem/CF1707E f([l1,r1]∪[l2,r2])=f(l1,r1)∪f(l2,r2)f([l_1,r_1]\cup [l_2,r_2])=f(l_1,r_1)\cup f(l_2,r_2)f([l1​,r1​]∪[l2​,r2​])=f(l1​,r1​)∪f(l2​,r2​) f([l1,...

普通环的构造计数——计数链，然后合成：1211T3 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134929628 http://47.92.197.167:5283/contest/437/problem/3 我们要构造环，肯定要构造链，然后题目还和我们说了是个二分图，我们就让链的端点在同一边（假定在右边） 那样考虑左边每个点又什么用？很显然，粘！可以把两条链粘一起，或者把链变成环。 所有很明显了，我们直接dp。 f(i,j)f(i,j)f(i,j) 表...

1211T2：分层图跑最小割（要割几次的最小割） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134926699 http://47.92.197.167:5283/contest/437/problem/2 k=1k=1k=1 就是个最小割 发现我们可能要割很多次，我们可以直接建分层图，在分层图上完成

二分+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 个人先往右走，最多走多少步就有掉头。 然后在纸上画一画就是小学的相遇问题，直接转...

每个点取值拆成多个点的最小割问题：CF1430G 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134751924 https://vj.imken.moe/contest/597216#problem/I 题目等价于求 min⁡∑uau(outu−inu)\min \sum_{u}a_u(out_u-in_u)min∑u​au​(outu​−inu​) 发现每个数的取值范围最多到 nnn ，然后又有一堆限制，考虑拆点+网络流。 每个点拆成 n+2n+2n+...

最小割构造 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134750195 考虑跑完最大流，我们再从源点跑一遍bfs，所以能跑到的点都属于点集A，否则属于点集B

FWT+高维前缀和：Gym - 103202M 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134749229 https://vj.imken.moe/contest/597216#problem/F 考虑两个人的集合分别为 i,ji,ji,j ，那么我们令 f(i⊗j)++f(i\otimes j)++f(i⊗j)++ ，其中 f(s)f(s)f(s) 表示两个人不同集合 恰好 为 sss ，显然 f(s)f(s)f(s) 可以FWT求。 假设 g(t...

贪心+计数：CF1612G 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134747631 https://www.luogu.com.cn/problem/CF1612G 贪心考虑如何放最优。 假设当前出现次数最多为 iii ，有 kkk 个这样的数，打表可得左边 kkk 个随便放，右边 kkk 个随便放，然后递归下去即可，当前层方案数为 (k!)2(k!)^2(k!)2 。 在这个过程中顺便维护最大值即可。 123456789101112 m=read...

NOIP前题目整理 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134253896 动态规划/dp 常见类型 背包 背包类最经典的一类dp问题。 容量很大体积很小的背包问题 完全背包 https://www.luogu.com.cn/problem/P9140 多重背包 http://zhengruioi.com/problem/2620 题解： https://blog.csdn.net/zhangtingxiqwq/article/deta...

扩展dp记录内容减少dp状态：ICPC2021区域赛沈阳G 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134379201 https://vjudge.net/contest/593228#problem/I 场上想的思路是 dp[s][i]dp[s][i]dp[s][i] 现在还有 sss 的没填，从 iii 位置开始，最后的串，通过记忆化搜索来减少状态，但是还是过不了。 我们考虑继续扩展dp状态存的东西。 dp[s]dp[s]dp[s] 表示 ss...