2020-2021:teams:legal_string:jxm2001:contest:agc_054

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:legal_string:jxm2001:contest:agc_054 [2021/06/28 09:48]
jxm2001 创建
+++ 2020-2021:teams:legal_string:jxm2001:contest:agc_054 [2021/06/28 10:33] (当前版本)
jxm2001
@@ 行 59: / 行 59: @@
 </hidden>
+===== C - Roughly Sorted =====
+==== 题意 ====
+给定一个 $1\sim n$ 的排序 $P$，每次操作可以交换相邻两个元素的位置。
+要求用最少的操作使得对每个 $i$，最多有 $k$ 个 $j\lt i$ 满足 $P_j'\gt P_i'$。
+现已知 $P'$，问存在多少个可能的最初的 $P$。
+==== 解法 ====
+记 $f_i=\sum_{j=1}^{i-1}[P_j\gt P_i]$，不难发现对每次操作最多可以使得某个 $f_i$ 减一，于是最少操作数的下限为 $\sum_{i=1}^n \max(f_i-k,0)$。
+考虑找到最小的 $i$ 使得 $f_i\gt k$，不难发现此时一定有 $P_{i-1}\gt P_i$，否则一定有 $f_{i-1}=f_i\gt k$，与 $i$ 的最小性矛盾。
+交换 $P_{i-1},P_i$，可以使得 $f_i$ 减一。于是可以证明 $\sum_{i=1}^n \max(f_i-k,0)$ 这个操作下限是可以取到的。
+根据离散数学知识，知逆序数与排列存在一一对应关系，同时有 $f(i)\le n-P_i$。
+同时，为了使得步数最少，对 $f(i)\lt k$ 的位置，他的初值应该不变。对 $f(i)=k$ 的位置，他的初值只需要满足 $f(i)\le n-P_i$。
+于是不难发现答案为 $\prod_{f(i)=k} (n-P_i-f(i)+1)$，时间复杂度 $O(n\log n)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=5e3+5,mod=998244353;
+int c[MAXN];
+#define lowbit(x) ((x)&(-x))
+void add(int pos){
+	while(pos<MAXN){
+		c[pos]++;
+		pos+=lowbit(pos);
+	}
+}
+int query(int pos){
+	int ans=0;
+	while(pos){
+		ans+=c[pos];
+		pos-=lowbit(pos);
+	}
+	return ans;
+}
+int a[MAXN],p[MAXN];
+int main()
+{
+	int n=read_int(),k=read_int(),ans=1;
+	_for(i,0,n){
+		a[i]=read_int();
+		p[i]=i-query(a[i]);
+		add(a[i]);
+		if(p[i]==k)
+		ans=1LL*ans*(n-a[i]-p[i]+1)%mod;
+	}
+	enter(ans);
+	return 0;
+}
+</code>
+</hidden>

2020-2021/teams/legal_string/jxm2001/contest/agc_054.1624844916.txt.gz · 最后更改: 2021/06/28 09:48 由 jxm2001