51nod 1839 Lin的游戏

1839 Lin的游戏

• 1.0 秒
• 131,072.0 KB
• 160 分
• 6级题

在51nod上面一道冷门题
观前提示：本文章内使用的编程语言是c++，且代码毫无可读性就像爪子用狗刨的，请慎重观看

首先我们可以知道以下信息：

• 根据数据范围n*d+6位小数=17位，所以需要开
• 限时为1s，所以最差时间复杂度为
• Lin只知道自己在当前回合所选的数字在所有已选过的数字里有多大
• Lin的选择只和当前回合的状态有关系，和之前的什么关系也没有
• 如果一直移除，那么最后得分期望就是

基础版（12/20）

期望，动态规划，前缀和

我们可以设dp[i]为第 i 回合结束游戏时的期望得分
那么dp[n]=
我们就从n-1开始往下推到1

以最大期望为例：

对于每个回合，决定一个阈值k，倘若此回合选中的数字大小排名小于 k，就结束游戏，否则就继续下一回合。
众所周知，从题目中的数字中选出 i 个数字中第 j 大的数字的值期望
不信自己推
Lin在这一回合决策停止游戏的得分贡献值
这里的可以用前缀和来弄

此时继续进入下一回合的概率为

综合亿下
另一种期望则按平均值取反

代码O(n²)：

#include<bits/stdc++.h>
using namespace std;
long long n,d,a,k;
double c[1002356],dp[1002356];
int main()
{cin>>n>>d>>a;dp[n]=((n-1)*d+2*a)/2.0;for(int i=n-1;i>0;i--){for(int j=1;j<=i;j++)c[j]=c[j-1]+1.0/i*(a-d+((i-j+1)*(n+1)*d)/(i+1.0));for(int k=0;k<=i;k++)dp[i]=max(dp[i],c[k]+(1-(double)k/i)*dp[i+1]);}printf("%.6lf\n%.6lf",2*a+(n-1)*d-dp[1],dp[1]);return 0;
}

别问我为什么不用，因为这样会再少得2个点

膏级版（14/20）

膏斯求和

不难看出，中只有一个分子是改变的，所以可以用膏斯求和来求的值
经简化，得
不信自己推

照样

代码O(n²)：

#include<bits/stdc++.h>
using namespace std;
long long n,d,a,k;
double dp[1002356];
int main()
{cin>>n>>d>>a;dp[n]=((n-1)*d+2*a)/2.0;const long long f=a-d,g=(n+1)*d;for(int i=n-1;i>0;i--){const double p=1.0/i,q=g/(i+1.0);for(int k=0;k<=i;k++)dp[i]=max(dp[i],k*(2*i-k+1)*0.5*p*q+f+(1-(double)k*p)*(dp[i+1]-f));}printf("%.6lf\n%.6lf",2*a+(n-1)*d-dp[1],dp[1]);return 0;
}

虽然这样得分还是0，但这两个点的意义你看到下面就懂了

满分版（20/20）

双调数组，二分

由前面的分析可得：
在k的循环中

• 是递减的，所以减速递增
• 是等差数列

所以是双调（即中间最大，两边依次减小的）数列

这时就可以用二分，每次选择连续2个数据，更小的所在的那一边就可以排掉了

代码O（nlogn）：

#include<bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;
ll n,d,a;
ld dp[1002356];
int main()
{cin>>n>>d>>a;dp[n]=((n-1)*d+2*a)/2.0;const ll f=a-d,g=(n+1)*d;for(int i=n-1;i>0;i--){const ld p=1.0/i,q=g/(i+1.0)*0.5,s=dp[i+1]-f;ll l=0,r=i,k;ld c,e;while(l<r){k=(l+r)/2;c=k*(2*i-k+1)*p*q+f+(1-k*p)*s;k++;e=k*(2*i-k+1)*p*q+f+(1-k*p)*s;if(c<=e)l=k;else r=k-1;}dp[i]=l*(2*i-l+1)*p*q+f+(1-l*p)*s;}printf("%.6Lf\n%.6Lf",2*a+(n-1)*d-dp[1],dp[1]);
}

//尸米山代码，不喜勿喷