bzoj 3450 Tyvj1952 Easy

bzoj 3450 Tyvj1952 Easy

Output 一行一个浮点数表示答案 四舍五入到小数点后4位 如果害怕精度跪建议用long double或者extended

Sample Input 4 -? Sample Output 4.1250

n<=300000 osu很好玩的哦 WJMZBMR技术还行(雾),x基本上很少呢

HINT

Source 我们都爱GYZ杯

设dp[i]表示到第i位的答案 l[i]表示到第i位的长度的期望

从len->len+1 平方的增量仅仅是2*len+1 然后根据此dp即可

#include#include#includeusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f;}long double dp[2],l[2];int n;int main(){ freopen("bzoj3450.in","r",stdin); n=read();int now=1,pre=0; for (int i=1;i<=n;++i){ char ch=gc(); if (ch=='o') dp[now]=dp[pre]+l[pre]*2+1,l[now]=l[pre]+1; if (ch=='x') l[now]=0,dp[now]=dp[pre]; if (ch=='?') dp[now]=dp[pre]+l[pre]+0.5,l[now]=(l[pre]+1)/2; pre^=1;now^=1; }printf("%.4Lf\n",dp[pre]); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。