有 \(n\) 次点击要做，成功了就是\(o\)，失败了就是\(x\)，分数是按\(comb\)计算的，连续\(a个comb\)就有a \times a分，\(comb\)就是极大的连续\(o\)。比如ooxxxxooooxxx，分数就是\(2 \times 2+4 \times4=4+16=20\)。
\(Sevenkplus\)闲的慌就看他打了一盘，有些地方跟运气无关要么是\(o\)要么是\(x\)，有些地方\(o\)或者\(x\)各有\(50\%\)的可能性，用\(?\)号来表示。比如\(oo?xx\)就是一个可能的输入。
那么\(WJMZBMR\)这场\(osu\)的期望得分是多少呢？比如\(oo?xx\)的话，\(?\)是\(o\)的话就是\(oooxx => 9\)，是\(x\)的话就是\(ooxxx => 4\) 期望自然就是\((4+9)/2 =6.5\)了
输入格式第一行一个整数\(n\)，表示点击的个数
接下来一个字符串，每个字符都是\(ox？\)中的一个
输出格式一行一个浮点数表示答案
四舍五入到小数点后\(4\)位
如果害怕精度跪建议用\(long double\)或者\(extended \)
样例 样例输入4
????
4.1250
数据范围与提示\(n<=300000\)
\(osu很好玩的哦\)
\(WJMZBMR\)技术还行(雾),\(x\)基本上很少呢
分析第 \(4\) 题的弱化版
代码 #include<bits/stdc++.h> using namespace std; typedef double dd; const int maxn=1e6+5; dd g[maxn],f[maxn]; char s[maxn]; int main(){ int n; scanf("%d",&n); scanf("%s",s+1); for(int i=1;i<=n;i++){ if(s[i]==\'o\'){ f[i]=f[i-1]+2*g[i-1]+1; g[i]=g[i-1]+1; } else if(s[i]==\'x\'){ f[i]=f[i-1]; g[i]=0; } else{ g[i]=(g[i-1]+1)/2.0; f[i]=0.5*f[i-1]+0.5*(f[i-1]+2*g[i-1]+1); } } printf("%.4lf\n",f[n]); return 0; } 7、单选错位 题目描述题目传送门
分析我们考虑 \(gx\) 期望做对的第 \(i+1\) 道题的概率
如果 \(a[i] \geq a[i+1]\) ，则有 \(\frac{a[i+1]}{a[i]}\)的概率落到正确答案的区间内，同时答对的可能性为 \(\frac{1}{a[i+1]}\)
如果 \(a[i] < a[i+1]\) ，则有 \(\frac{a[i]}{a[i+1]}\)的概率落到正确答案的区间内，同时答对的可能性为 \(\frac{1}{a[i]}\)
因此最终的答案为 \(\sum_{i=1}^n \frac{1}{max(a[i],a[i+1])}\)
代码 #include<cstdio> #include<algorithm> #include<cmath> const int maxn=10000005; int n,A,B,C; long long a[maxn]; double ans; int main(){ scanf("%d%d%d%d%lld",&n,&A,&B,&C,&a[1]); for(int i=2;i<=n;i++){ a[i] = ((long long)a[i-1] * A + B) % 100000001; } for(int i=1;i<=n;i++){ a[i]=a[i]%C+1; } a[0]=a[n]; for(int i=1;i<=n;i++){ ans+=1.0/(std::max(a[i],a[i-1])); } printf("%.3f\n",ans); return 0; } 8、洛谷P2059 [JLOI2013]卡牌游戏 题目描述题目传送门
分析这道题正着不好处理，倒着设比较方便
设 \(f[i][j]\) 为 \(i\) 人形成的环中，第 \(j\) 个人获胜的概率
已知 \(f[1][1]=1\)
那么我们就可以模拟抽走每一张牌，计算出剩下的人在更小的环里对应的位置
然后用之前已经求得的值更新当前值
代码 #include<bits/stdc++.h> using namespace std; const int maxn=55; double f[maxn][maxn]; int a[maxn]; int main(){ int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ scanf("%d",&a[i]); } f[1][1]=1.0; for(int i=2;i<=n;i++){ for(int j=1;j<=i;j++){ for(int k=1;k<=m;k++){ int p=a[k]%i; if(p==0) p=i; if(p>j) f[i][j]+=f[i-1][i-p+j]/m; else f[i][j]+=f[i-1][j-p]/m; } } } for(int i=1;i<=n;i++){ printf("%.2lf%% ",f[n][i]*100.0); } return 0; } 9、洛谷 P3232 [HNOI2013]游走 题目描述游走
分析因为要使获得总分的期望值最小
所以我们肯定要给经过次数少的边赋大权值
但是边的期望经过次数不好直接求
但是我们可以求出点的期望经过次数
边的期望经过次数就是它所连点的期望经过次数除以点的入度再加和
我们设点 \(u\) 的期望经过次数为 \(f[u]\)
那么 \(f[u]= \sum_{v-u}f[v]/du[v]\)
其中 \(du[v]\) 是节点 \(v\) 的入度
初始化 \(f[n]=1\)
要注意的是当 \(u=1\) 时，还要把 \(f[u]\) 加上 \(1\)
因为一开始是从 \(1\) 号节点出发的