zhangxixi的博客

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... ...

用欧拉路径判断图同构推出reverse合法性：1116T4 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134444131 http://cplusoj.com/d/senior/p/SS231116D 假设我们要把 aaa 变成 bbb ，我们在 aia_iai​ 和 ai+1a_{i+1}ai+1​ 之间连边， bbb 同理，则 aaa 能变成 bbb 的充要条件是两图 A,BA,BA,B 同构。 必要性显然，因为无论如何reverse都不会改变图的形...

枚举连通块拆贡献+容斥：ABC321G 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133266690 https://atcoder.jp/contests/abc321/tasks/abc321_g 这种题都没看出来我要去退役了 看完题目，可以获得： 期望、连通块：显然拆贡献啊！ n≤17n\le 17n≤17 ：这不明显状压？结合前面连通块，就是枚举连通块啊！ 继续分析第2点，17这么小，显然枚举子集。为啥枚举？计数题只有容斥这个套路啊！...

缩点+图论路径网络流：1114T4 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134407471 http://cplusoj.com/d/senior/p/SS231114D 重新梳理一下题目 我们先建图 x→yx\to yx→y ，然后对点分类：原串出现点，原串未出现点。 假如我们对一个原串出现点进行了操作，那么它剩余所有出边我们立刻去操作必然没有影响。所以我们只要所有原串出现点都操作一遍即可（如果有出边），那么我们就把边问题变成了点问题。 考虑一次...