zhangxixi的博客

二分+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...

分析性质题（集合类）：CF566E 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133870468 https://www.luogu.com.cn/problem/CF566E 感觉浪费了一道好题，没有好好分析性质 若非叶子节点有连边，则存在两个集合的交集为 {x,y}\{x,y\}{x,y} 然后就可以区分叶子和非叶子节点 对于叶子节点，包含它大小最小的集合就是对应的集合。 对于非叶只计算<=1距离的点，设为 GGG 显然在非叶>=3时...

对于从三个方向转移的期望dp式子移项方法 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133753059 fi=afi−1+bfi+cfi+1+vif_i=af_{i-1}+bf_i+cf_{i+1}+v_ifi​=afi−1​+bfi​+cfi+1​+vi​ ，其中 a+b+c=1a+b+c=1a+b+c=1 ，求 fff 考虑差分， gi=fi−fi+1g_i=f_i-f_{i+1}gi​=fi​−fi+1​ fi=a(fi−1+gi−1)+bfi...

去掉限制+让赢家保持局面不变：P4101 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133711268 假如没有限制，就和 n−1n-1n−1 的奇偶有关。 博弈论的构造我们做的是什么？无论对手做什么，我都可以通过一些操作使得某种形式的局面不变。 考虑一开始会怎样。第一步只能合并两个1。变成 2 1 1 1 1 ... 考虑现在有个人操作，他就有两种选择。合并两个1，或者合并1和2。分别变成 3 1 1 1 1... 或 2 2 1 1 1 1... ...