首页 > 代码库 > Tyvj1952 Easy

Tyvj1952 Easy

%%http://hzwer.com/2838.html

比较巧妙的是原来L^2->(l+1)^1=L^2+2*L+1这样就可以递推了

“?”的贡献及时“o”贡献的1/2。

 1 #include<bits/stdc++.h>
 2 #define LL long long
 3 #define LD long double  
 4 #define  N 100005
 5 using namespace std;
 6 inline int ra()
 7 {
 8     int x=0,f=1; char ch=getchar();
 9     while (ch<0 || ch>9) {if (ch==-) f=-1; ch=getchar();}
10     while (ch>=0 && ch<=9) {x=x*10+ch-0; ch=getchar();}
11     return x*f;
12 }
13 char s[N<<2];
14 double f[N<<2],d[N<<2];
15 int main()
16 {
17     int n=ra();
18     scanf("%s",s+1);
19     for (int i=1; i<=n; i++)
20     {
21         if (s[i]==x)
22             f[i]=f[i-1],d[i]=0;
23         else if (s[i]==0) f[i]=f[i-1]+2*d[i-1]+1,d[i]=d[i-1]+1;
24         else f[i]=f[i-1]+d[i-1]+0.5,d[i]=(d[i-1]+1)/2;
25     }
26     printf("%.4lf",f[n]);
27     return 0;
28 }

 

Tyvj1952 Easy