注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ2134]单选错位  

2014-12-28 16:26:22|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2134: 单选错位

第一眼看上去让人感觉无从下手的题。。
题解在代码下方

#include<cstdio>
#include<cstdlib>
const int N = 1E7+100;
//for C/C++
int n,A,B,C,a[N];
double f[N];
int min(int a,int b){return a<b?a:b;}
int main(){
int i,j;
scanf("%d%d%d%d%d",&n,&A,&B,&C,a+1);
for (int i=2;i<=n;i++) a[i] = ((long long)a[i-1] * A + B) % 100000001;
short t=1;
double ans=0;
for (int i=1;i<=n;i++){
a[i] = a[i] % C + 1;
if(i>1){
f[i] = f[i-1]/a[i-1]*a[i] + 1.*min(a[i-1],a[i])/a[i-1];
}
t^=1;
}
ans = f[n]*a[1]/a[n] + 1.*min(a[n],a[1])/a[n];
//for(i=1;i<=n;i++)printf("%f\n",f[i]);
ans/=a[1];
printf("%.3f\n",ans);
return 0;
}





题解:
DP
这题最让人蛋疼的地方就是有环。
通常的处理方式就是枚举第一个位置的情况,然后分别DP。
所以易得n^3的DP:
枚举第一道题的答案,AA f[i][j]表示第i题答案是j的期望。
 j<=a[i-1] 
f[i][j]  = (f[i-1][j]+1)/a[i-1] + f[i-1][els]/a[i-1] 
 = 1/a[i-1] + f[i-1][all]/a[i-1] else f[i][j] 
      = f[i-1][all]/a[i-1]; 
注意到前一项全是f[i-1][all].. 
所以f[i][all] = f[i-1][all]*a[i]/a[i-1] + min(a[i-1],a[i])/a[i-1]
f[1][all]=0
最后统计答案:
f[n+1][AA] = (f[n][AA]+1)/a[n] + f[n][els]/a[n] 
  = f[n][all]/a[n] + 1/a[n] f[n+1][els] 
  = f[n][all]
ans = f[n+1][AA]/a[1]
对于f[2],如果AA > a[2] f[2] = 0,否则f[1] = 1
最后把头和尾的情况分类讨论之后加起来,发现2和ans的位置也满足通式。
问题解决
  评论这张
 
阅读(38)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017