普通环的构造计数——计数链，然后合成：1211T3
普通环的构造计数——计数链，然后合成：1211T3
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134929628
http://47.92.197.167:5283/contest/437/problem/3
我们要构造环，肯定要构造链，然后题目还和我们说了是个二分图，我们就让链的端点在同一边（假定在右边）
那样考虑左边每个点又什么用？很显然，粘！可以把两条链粘一起，或者把链变成环。
所有很明显了，我们直接dp。 表示右边前 个点，有 条链的方案数。右边每个点判断选或不选，左边可以不选、粘，成链，成链时计入答案即可。
转移时发现要分一些奇奇怪怪的情况讨论，我们干脆当做有向链，最后除个2即可。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2023-10-08
分析性质+DP计数：1007T4
分析性质+dp计数：1007T4 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133659409 http://cplusoj.com/d/senior/p/SS231007D 分析题目性质，有： 按编号顺序最短路必然为连续段 边只会在连续段内和相邻连续段之间连 iii 段 连 i+1i+1i+1 段， i+1i+1i+1 段中每个点恰有1条来自 iii 的边 然后肯定是考虑 f(l,r)f(l,r)f(l,r) 表示最后一段为 [l,r]...
2024-10-07
1006C简单题（计数式子的组合意义 + DP式子联立）
1006C简单题（计数式子的组合意义 + dp式子联立） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/142740338 http://cplusoj.com/d/senior/p/SS241006C 对于这个式子，我们可以从它的组合意义入手。 假设我们有 n+1n+1n+1 个白球要染色，中间有一个绿球，绿球左边有 aaa 个红球，右边有 bbb 球。染完后绿球左边每个白球有 xxx 的贡献，右边每个白球有 yyy 的贡献。 但接下来怎么做呢？这列出来...
2023-09-18
拆贡献算总和（抓住双射）+竞赛图与连通分量相关计数：arc163_d
拆贡献算总和（抓住双射）+竞赛图与连通分量相关计数：arc163_d 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132994501 https://atcoder.jp/contests/arc163/tasks/arc163_d 首先竞赛图有个性质： 然后有了这个性质，我们就可以考虑计数题的经典套路，拆贡献算总和。 考虑假如我们成功划分成两个集合 A,BA,BA,B ，其中一个可以为空（我们可以令 AAA 可以为空，防止算重），我们就记为算到一个新的...
2023-09-03
用树形DP+状压维护树上操作的计数问题：0902T3
用树形dp+状压维护树上操作的计数问题：0902T3 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132647373 发现操作数 k≤6k\le6k≤6 ，可以考虑对操作进行 状压 。 然后找找性质，发现要么删掉一棵子树，要么进去该子树。可以视为每种操作有两种情况。 然后分讨一下当前该如何转移。 树形dp的顺序： 合并子树 考虑当前往上的边的方向 然后发现只需要记住最早一次保留操作就行。 对于连通块大小的限制，就看一下当前操作之前有多少个子...
2023-09-18
对于每种情况分别统计概率来计算期望+树上连通块统计：ARC165E
对于每种情况分别统计概率来计算期望+树上连通块统计：ARC165E 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132971902 https://atcoder.jp/contests/arc165/tasks/arc165_e 考虑一个常见套路，我们对每个连通块统计其概率，设为 p(T)p(T)p(T) ，则答案为 ∑∣T∣>kp(T)\sum_{|T|>k} p(T) ∣T∣>k∑p(T) 可以想成对于每个大小大于 kkk 的连...
2023-09-27
博弈论（奇偶考虑法）+计数+DP（判定转DP）：CF838C
博弈论（奇偶考虑法）+计数+DP（判定转dp）：CF838C 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133362167 首先题目有博弈，先分析一波最优策略（步骤：分析性质）。 两个人，所以显然考虑奇偶考虑法+递归考虑。 首先删就是使子问题-1，重新排列是在当前子问题里的。 一个串的排列是有限的，所以这里就可以上奇偶考虑法。如果有偶数种串，则必然是后手先“被迫“进入子问题（要算上初始情况） 考虑假设法：我们可以先假设进入子问题： 必赢。先手进！ ...