排列 -＞ 位置与值域相对应：1006T2
排列 -＞ 位置与值域相对应：1006T2
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133611553
http://47.92.197.167:5283/problem/5513
考场上转化后的是max（每个数的位置 - 其应该的位置）
但对于排列问题，此题可以直接转化为每个数之前有多少个数比他大
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2023-09-03
用树形DP+状压维护树上操作的计数问题：0902T3
用树形dp+状压维护树上操作的计数问题：0902T3 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132647373 发现操作数 k≤6k\le6k≤6 ，可以考虑对操作进行 状压 。 然后找找性质，发现要么删掉一棵子树，要么进去该子树。可以视为每种操作有两种情况。 然后分讨一下当前该如何转移。 树形dp的顺序： 合并子树 考虑当前往上的边的方向 然后发现只需要记住最早一次保留操作就行。 对于连通块大小的限制，就看一下当前操作之前有多少个子...
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 可以为空，防止算重），我们就记为算到一个新的...
2024-01-11
枚举LCA+分类讨论列式子：0111B
枚举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...
2026-08-02
容斥思想辅助mex计数+CDQ分治：26暑杭电 3-11
容斥思想辅助mex计数+CDQ分治：26暑杭电 3-11 1011 Mex 感觉这道题最巧妙的地方是，用每个位置 iii 去计算对答案的贡献。 也就是钦定0、1、2、3个为位置为mex，然后用容斥计算是否可行 0个位置的贡献为1（即全选） 1个位置的话有 nnn 种，而且显然合法 2个位置，有 (n2)\binom n 2(2n) 种。不合法的情况是形成三维偏序。 3个位置，有 (n3)\binom n 3(3n) 种，不合法的情况是形成二维偏序，根据容斥，要加回三维偏序。 于是总方案为： 1+n+(n2)−∑iABC(i)+(n3)−∑i((AB(i)2)+(AC(i)2)+(B...
2023-12-02
贪心+计数：CF1612G
贪心+计数：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...
2023-12-11
普通环的构造计数——计数链，然后合成：1211T3
普通环的构造计数——计数链，然后合成：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) 表...