题目概述

有 $n$ 个有权值的物品，现在给出若干个询问：$m$ 个颜色，每种颜色有 $c_i$ 个且和为 $n-1$ ，现在要在 $K$ 这个位置选择一个颜色，然后从 $K$ 向两边以 $D$ 的间距选取到最远的和 $K$ 颜色均一样的位置并累加权值，求选择颜色使得期望权值最小。

解题报告

口头AC了解一下，这是假题，首先有很明显的贪心：选取个数最少的颜色。然后从 $K$ 开始向两边统计，距离 $x$ 个 $D$ 的时候概率为 $\prod_{i=1}^{x}{MIN-i+1\over n-i}$ ，会发现除了 $m=1$ 时（这时候可以用阈值优化，$D$ 比较小的时候预处理，否则暴力做），没到多远这个概率就变得很小了，差不多100来次就根本比不上精度了，所以暴搞。

示例程序

要么精度不够，要么TLE，我好绝望啊。

#include<cstdio>
using namespace std;
typedef long double DB;
const int maxn=100000,maxm=200000,S=100;
 
int n,m,K,D,te,v[maxn+5],c[maxm+5];DB sum[S+5][S+5];
 
inline double Solve(){
    if (m==1){if (D<=S) return sum[D][K%D];DB ans=v[K];
        for (int i=K-D;i>=1;i-=D) ans+=v[i];for (int i=K+D;i<=n;i+=D) ans+=v[i];return ans;
    }int MIN=2e9;for (int i=1;i<=m;i++) c[i]<MIN?MIN=c[i]:0;DB ans=v[K],now=1;
    for (int i=K-D,tot=1;i>=1&&tot<=S;i-=D,tot++) now=now*(MIN-tot+1)/(n-tot),ans+=now*v[i];now=1;
    for (int i=K+D,tot=1;i<=n&&tot<=S;i+=D,tot++) now=now*(MIN-tot+1)/(n-tot),ans+=now*v[i];return ans;
}
int main(){
    freopen("lzz.in","r",stdin);freopen("lzz.out","w",stdout);
    scanf("%d%d",&n,&te);for (int i=1;i<=n;i++) scanf("%d",&v[i]);
    for (int i=1;i<=n;i++) for (int j=1;j<=S;j++) sum[j][i%j]+=v[i];
    for (int tp,x,y;te;te--)
        if (scanf("%d",&tp),tp==1) {scanf("%d%d",&x,&y);for (int j=1;j<=S;j++) sum[j][x%j]+=y-v[x];v[x]=y;}
        else {scanf("%d%d%d",&m,&K,&D);for (int i=1;i<=m;i++) scanf("%d",&c[i]);printf("%.6f\n",Solve());}
    return 0;
}