排列 -＞ 位置与值域相对应：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-13
根号分治与多项式的巧妙结合：GYM-104386G
根号分治与多项式的巧妙结合：GYM-104386G 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132866002 使用范围：序列上对于 每种 数的计数问题 考虑对每种数的出现次数进行根号分治 如果出现次数很少，直接平方暴力即可 如果很大考虑任意 (i,j)(i,j)(i,j) ，我们拆一下，再移一下，然后就变成了卷积形式
2023-09-18
简单的反射容斥与多项式快速幂：Loj#6738. 王的象棋世界
简单的反射容斥与多项式快速幂：Loj#6738. 王的象棋世界 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132978606 首先看到不能走出边界，发现是个反射容斥 对于此题，我们可以采用循环卷积来实现反射容斥 也就是说，如果我们走出了边界，相当于就是走到了另一边 而实现这个过程我们可以把卷完后 i+pi+pi+p 的部分直接平移到 iii 就行 加速这个过程可以用多项式快速幂 1234567891011121314151617181920212223...
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-10-09
质因子拆贡献+朴素容斥：1007T3
质因子拆贡献+朴素容斥：1007T3 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133697910 http://cplusoj.com/d/senior/p/SS231007C 考虑枚举gcd，然后容斥，恰好转至少。 ggg 表示gcd恰好为 ddd ， fff 表示至少为 ddd 显然有 f(d)=∑d∣ng(n)f(d)=\sum_{d|n}g(n)f(d)=∑d∣ng(n) ，可以直接莫反成： g(d)=∑d∣nf(n)μ(nd)g(d)=\s...
2026-10-16
期望 + dp + 计数 + 策略转限制：ICPC2025沈阳E
期望 + dp + 计数 + 策略转限制：ICPC2025沈阳E Play It by Ear - Problem - QOJ.ac 令 posxpos_xposx 表示编号为 xxx 的牌在原先牌堆的位置。 设 fif_ifi 表示完成第 iii 步（aia_iai 牌打出），至少需要多少步。设对于 aia_iai 这张牌，上一次出现在 preipre_iprei 的位置，那样子有： fi≥fi−1+1fi≥fprei+n+1f_i\ge f_{i-1}+1\\ f_i\ge f_{pre_i} + n + 1 fi≥fi−1+1fi≥fprei+n+1 因为上一...
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...