2018.2.26 国家集训队选拔考试

考试

1.彩色圆环

BZOJ 2201(别试了，权限题) 清橙A1202
O(N^2)戳我有题解

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int _=205;
inline int read()
{
    char ch='!';int z=1,num=0;
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')z=-1,ch=getchar();
    while(ch<='9'&&ch>='0')num=(num<<3)+(num<<1)+ch-'0',ch=getchar();
    return z*num;
}
int N,M;
long double ans,g[_],dp[_][2];
//dp[i][1/0]表示长度为i的序列，第一个和第二个球颜色不同，第一个和最后一个颜色相同/不同的期望美观程度 
int main()
{
    //freopen("circle.in","r",stdin);
    //freopen("circle.out","w",stdout);
    N=read();M=read();
    g[1]=1;dp[1][1]=1;
    for(int i=2;i<=N;i++)g[i]=1.0*g[i-1]/M;
    ans+=g[N]*N;
    for(int i=2;i<=N;i++)
    {
        for(int j=1;j<i;j++)//枚举序列长度1-i转移
        {
            dp[i][0]+=dp[i-j][0]*(1-2.00/M)*j*g[j]+1.0*dp[i-j][1]*(1-1.0/M)*j*g[j];
            dp[i][1]+=dp[i-j][0]*j/(double)M*g[j];
        }
    }
    for(int i=1;i<N;i++)ans+=i*i*dp[N-i+1][0]*g[i];//枚举上半环长度
    //只能枚举dp[][0]，因为第一段和N-i段必须是不一样的
    printf("%.8Lf\n",ans);
    return 0;
}

2.剪枝

清橙A1212