周赛Round29

D.小红的中位数

开始想用堆顶堆，但很快就发现每次都只是自在初始序列上删一个之后的查询，中位数只会跟中间几个数有关，只要根据初始序列长度的奇偶和删去元素的位置讨论一下就能以O(1)算出每次查询

如果是偶数，删去元素位于左半边，会让右半边第一个成为中位数，位于右半边，会让左半边最后一个元素成为中位数。

如果是奇数，删去元素位于右边，会让中间数和左边最后一个数得平均数成为中位数，如果位于左边，会让中间数和右边第一个数的平均数成为中位数，如果是中间，那么会让左边最后一个和右边第一个的平均数成为中位数。

	rep(i,1,n){
		cin>>a[i].val;
		a[i].num=i;
	}
	sort(a+1,a+1+n,cmp);
	if(n%2){//奇数
		m=(n+1)/2;
		rep(i,1,n){
			if(i==m)ans[a[i].num]=(a[i+1].val+a[i-1].val)/2.0;
			else if(i<m)ans[a[i].num]=(a[m].val+a[m+1].val)/2.0;
			else ans[a[i].num]=(a[m-1].val+a[m].val)/2.0;
		}
	}
	else {//偶数
		m=n/2;
		rep(i,1,n){
			if(i<=m)ans[a[i].num]=a[m+1].val;
			else ans[a[i].num]=a[m].val;
		}
	}
	rep(i,1,n)printf("%.1lf\n",ans[i]);

E 小红构造数组

给一个x，构造一个数列，满足数列所有元素乘起来等于x,相邻元素不等，每个元素都是质数。首先数列的所有元素就是x的所有质因子，问题在于怎么构造一个数列让相等的元素不相邻。

对于每一种质因子，如果有n个，那么需要n-1个其它元素把它们隔开。因此数列存在的必要条件是数量最多的质因子也可以被全部隔开，也就是sum-max(n)>=max(n)-1

如果满足这个条件，数列一定是存在的。由于数量最多的质因子也只有max(n)个，需要max(n)个区域，那么我们可以分出max(n)个区域，先把最多的因子分别放进这些区域内，每个区域放一个，然后对于剩余的因子，在1-max(n)这些区域内挨个放，每个区域也是只放一个，到达max(n)区域后再从区域1开始放。这样每个区域内，每种元素最多都只存在一个，使得所有相同元素都被隔开了。

vector<ll>ans[N];
map<ll,ll>mp;
struct node{
	ll val,times;
};
vector<node>a;
bool cmp(node a,node b){
	return a.times>b.times;
}
void solve(void){
	cin>>n;
    if(n==1){
        cout<<-1;
        return;
    }
	rep(i,2,sqrt(n))
		for(;n%i==0;n/=i)mp[i]++,cnt++;
	if(n!=1)mp[n]++,cnt++;
	ll mx=-1e9;
	for(auto i:mp){
		mx=max(mx,i.second);
		node t;
		t.times=i.second;
		t.val=i.first;
		a.push_back(t);
	}
	sort(a.begin(),a.end(),cmp);
	if(mx<=(cnt+1)/2){
		int pos=0;
		for(auto i:a){
			rep(j,1,i.times){
				ans[pos++].push_back(i.val);
				if(pos>=mx)pos=0;
			}
		}
		cout<<cnt<<'\n';
		rep(i,0,mx-1)
			for(auto j:ans[i])cout<<j<<' ';
	}
	else cout<<-1;
}

F小红又战小紫

有n堆石子，可以进行两种操作：所有堆都拿走一个；某一堆拿走一个。操作后没有石子的一方获胜。显然，如果所有堆都只有一个石子，直接全拿走。如果有的堆石子数为2，如果所有堆都拿走一个，剩下的堆就都只有一个石子了，对方全拿走就赢了，因此此时只能随机选一堆拿一个。

设dp(i,j)表示一共还有i堆，其中两个石子的堆有j堆时，当前操作者的获胜概率。如果j=0，全是一个石子的堆，直接胜利，dp(i,j)=1；否则，在全部i堆里随机选一堆拿走一个石子，如果选中的是一个石子的堆，转移到dp(i-1,j)，如果选中的是两个石子的堆，转移到dp(i,j-1)

需要注意的是，虽然说是转移到dp(i-1,j)和dp(i,j-1)，但是，此时是轮到对方操作的，也就是说dp(i-1,j)和dp(i,j-1)是对方胜利的概率，而我们在这一步要求的是我方胜利的概率。我方在这一步的胜率=sigma(转移到情况i的概率 * 我方在下一步情况i的胜率)，因此计算dp(i,j)时应该是用的是(1-dp(i-1,j))和(1-dp(i,j-1))

	cin>>n;
	int c[3]={0};
	rep(i,1,n){
		int x;
		cin>>x;
		c[x]++;
	}	
	rep(i,1,n){
		dp[i][0]=1;
		rep(j,1,i){
			dp[i][j]=(i-j)*inv(i)%mod*((1-dp[i-1][j]+mod)%mod)%mod;
			dp[i][j]+=j*inv(i)%mod*((1-dp[i][j-1]+mod)%mod)%mod;
			dp[i][j]%=mod;
		}
	}
	cout<<dp[n][c[2]];