zhangxixi的博客

0115C补充 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135640069 前 ： https://blog.csdn.net/zhangtingxiqwq/article/details/135612739 这题的图是和很特殊的图，它是一个竞赛图扣去了 mmm 条边，且剩下的边满足传递封闭性。 在这种情况下，我们每个点暴力往自己可以匹配最小的点去匹配，则最多有 m\sqrt mm​ 个点无法匹配。（这一步的证明用到了封闭性） 对于这一步的匹配，我们可...

矩阵树定理 + BEST定理 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135639913 行列式性质： 交换两行，符号取反 一行整体加上另一行的 kkk 倍，行列式不变 求一个图的内向生成树个数： 令度数矩阵为 DDD ，邻接矩阵为 KKK 。设 P=D−KP=D-KP=D−K ， PPP 去掉一行一列的行列式即为答案，我们设为 TTT 。 求一个欧拉图的欧拉回路个数，我们有结论： 如果每个点最后走的一条出边形成一棵内向树，则剩下的边...

质因数递推 + n^2+1质因数个数很少：0116A 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135626247 http://47.92.197.167:5283/contest/452/problem/1 考虑能不能不独立，预处理呢？假设我们知道 a2+1=pqa^2+1=pqa2+1=pq ，考虑有 (a+x)2+1≡0(modp)(a+x)^2+1\equiv 0\pmod p(a+x)2+1≡0(modp) ，一个合法的 xxx 是 ppp ...

传递闭包 + dilworth定理 + 二分图求最小链覆盖 + 模拟匈牙利 ： 0115C 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135612739 http://47.92.197.167:5283/contest/451/problem/3 求一个特殊图最大独立团，相当于是补集的最大独立集。然后这个补集（是个偏序集）满足传递闭包性质，根据 最大独立集 = 最长反链 = 最小链覆盖，题目等价于求最小链覆盖。这个可以直接网络流跑60分的。 对于正解，...

原根 + 背包 + bitset优化 + 二进制分组：0115B 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135609260 http://47.92.197.167:5283/contest/451/problem/2 原根： g1,…,gp−1g^1,\dots,g^{p-1}g1,…,gp−1 在  mod p\bmod pmodp 意义下取遍 1∼p−11\sim p-11∼p−1 。在 ppp 为质数时， ggg 不超过 p14p^{\fr...

对上面有要求的树形dp：0115A 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135608809 http://47.92.197.167:5283/contest/451/problem/1 我初始的思路是维护一个 dp(i,j)dp(i,j)dp(i,j) ，表示以 iii 根，向下染黑最远 jjj 层，但这样子统计贡献就很难维护。 不妨换个思路，这个 jjj 变成往上钦定要至少 jjj 层。那样子每个染黑的时候的贡献是已经确定了的。 而对于儿子的 ...

枚举LCA+分类讨论列式子：0111B 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135540375 http://47.92.197.167:5283/contest/447/problem/2 考虑部分分，枚举LCA 先单纯考虑一个点 iii 作为 xxx 祖先的概率。打表 / 推式子得 xxx 失无关变量。 我们现在预处理了期望深度 depidep_idepi​ 和期望祖先 fif_ifi​ 然后现在要努力列式子。 对于 xxx 要同时是 u,vu...

改变枚举顺序二分斜率时考虑斜率单调性来去掉log：0111A 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135540204 <47.92.197.167:5283/contest/447/problem/1> 考虑区间dp，然后每个点维护下凸壳，转移时在凸壳上二分 这样子是带log的。考虑区间dp时改变枚举顺序，就可以满足斜率递增，不用二分了

观察性质 + 奇偶分类构造二分图+ 二分图匹配：0109C 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135489832 http://cplusoj.com/d/senior/p/SS240109C 通过手模可知 f(a)+2C=f(a+2C)f(a) + 2C = f(a + 2C)f(a)+2C=f(a+2C) 于是这题很多时候要在模 2C2C2C 意义下讨论。 假设 iii 位置放 kkk ，则 2k−i+12k-i+12k−i+1 位置 k+c...

根号分治优化dp——暴力dp +类整数划分：0103C 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135402981 http://47.92.197.167:5283/contest/441/problem/3 首先有个暴力dp。 f(i,j)f(i,j)f(i,j) 和为 iii ，末项为 jjj 。 看到这种和达到平方级别，比如初项和长度成反比的题目，应该要想到根号分治 我们随便分，比如初项 ≤B\le B≤B ，那 jjj 不超过 2B2B2B ...