排列 -＞ 位置与值域相对应：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-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-09-03
环上计数+计数转概率：ABC318EX
环上计数+计数转概率：ABC318EX 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132650494 https://atcoder.jp/contests/abc318/tasks/abc318_h 先转为概率， fif_ifi 表示 iii 个点两人都AC的概率， gig_igi 表示恰好一个人AC的概率。 两个人都AC，只能为全部自环， fi=1i!f_i=\frac 1 {i!} fi=i!1 现在求 gng_ngn 。然后有个定理， ...
2023-09-03
用树形DP+状压维护树上操作的计数问题：0902T3
用树形dp+状压维护树上操作的计数问题：0902T3 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132647373 发现操作数 k≤6k\le6k≤6 ，可以考虑对操作进行 状压 。 然后找找性质，发现要么删掉一棵子树，要么进去该子树。可以视为每种操作有两种情况。 然后分讨一下当前该如何转移。 树形dp的顺序： 合并子树 考虑当前往上的边的方向 然后发现只需要记住最早一次保留操作就行。 对于连通块大小的限制，就看一下当前操作之前有多少个子...
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) 表...
2023-12-19
斐波那契的平方、立方问题——考虑几何立体意义（数形结合法）：P9510
斐波那契的平方、立方问题——考虑几何立体意义（数形结合法）：P9510 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135094722 https://www.luogu.com.cn/problem/P9510 关于斐波那契和的平方，其实就是正方形的面积和： 也就是 f(i)∗f(i+1)f(i)*f(i+1)f(i)∗f(i+1) 我们现在要求立方，但我们可以可以发现红色部分的结果是一样的： 直接三条棱表示除了，就是 f(i)∗f(i−1)∗f(i...
2023-10-18
杨辉三角按列求和
杨辉三角按列求和 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133906909 假设求杨辉三角这一列 我们考虑这个格子： 然后对其不断展开 综上： ∑i=0n(ik)=(n+1k+1)\sum_{i=0}^n\binom i k=\binom {n+1}{k+1} i=0∑n(ki)=(k+1n+1) ∑i=lr(ik)=(r+1k+1)−(lk+1)\sum_{i=l}^r\binom i k=\binom{r+1}{k+1}-\binom...