11.18 解题报告

A

考场用时：\(1\) h
期望得分：\(100\) pts
实际得分：\(100\) pts
不难推出：总代价即为所有逆序对的差的绝对值之和，这个直接树状数组维护就行了。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAX=1e6+10;
const int MOD=1e9+7;
inline int read(){
    int x = 0,f = 0;
    char ch=getchar();
    for(; !isdigit(ch); ch = getchar()) f|=(ch=='-');
    for(; isdigit(ch); ch = getchar()) x=(x<<1)+(x<<3)+(ch&15);
    return f ? -x : x;
}
int n,a[MAX],c[MAX],d[MAX];
inline void add(int x,int w,int t[]){
	for(int i=x;i<=n;i+=(i&-i)) t[i]+=w;
	return ;
}
inline int ask(int l,int r,int t[]){
	int ret=0;
	for(int i=r;i;i-=(i&-i)) ret+=t[i];
	for(int i=l-1;i;i-=(i&-i)) ret-=t[i];
	return ret;
}
signed main(){
//	freopen("1.in","r",stdin);
	n=read();
	int ans=0;
	for(int i=1;i<=n;i++) a[i]=read();
	for(int i=n;i>=1;i--){
		ans+=ask(1,a[i]-1,c)*a[i]-ask(1,a[i]-1,d);
//		cout<<ask(1,a[i]-1,d)<<endl;
		add(a[i],1,c);add(a[i],a[i],d);
	}
	cout<<ans;
	return 0;
}

B

考场用时：\(1.5\) h
期望得分：\(20\) pts
实际得分：\(0\) pts
爆搜写挂了，话说这题爆搜比正解难写的多啊。
设 \(X\) 为操作了多少次还没有选到位置1，那么
\(E = P(X ≥ 0) + P(X ≥ 1) + P(X ≥ 2)\) + . . .
而如果要保证操作了若干次后还没选到1，那么必须满足：

• [1, a1) 一次不能选。
• [1, a1) 至多选一次。
• [1, a2) 至多选两次。
  那么直接 dp：