据说，今年要考一道比换教室还难的概率/期望题。
有点慌。
那我就来学学概率和期望吧
以下中文名为自翻 文笔差见谅
A-A Dangerous Maze 危险的迷宫
就是你有n种选择，每次你会等概率选择其中一个。如果你选择了一个正数X，那X分钟之后游戏结束。如果选择的是个负数X，那X分钟之后重新选择。问游戏结束时间的期望。
样例：
3
3 -6 -9
Output：18
以该样例举例，设我们要算的期望是x，则有 x=(3+(6+x)+(9+x))/3
解释：如果选3的话，则在三分钟后游戏结束，期望时间是3/3.
如果选-6的话，那就是6分钟之后重新再选一次。因为六分钟之后重新再选的那次跟现在这次是一模一样的，所以重选期望跟当前期望相等，为x。同时我们还得等6分钟，所以期望是(6+x)/3.
-9同理；
所以我们解这个方程就得到了x的值。
#include<cstdio> #include<cstring> #include<cstdlib> #include<cctype> inline long long read(){ long long num=0,f=1; char ch=getchar(); while(!isdigit(ch)){ if(ch=='-') f=-1; ch=getchar(); } while(isdigit(ch)){ num=num*10+ch-'0'; ch=getchar(); } return num*f; } int w,tot; int gcd(int a,int b){ return (!b)?a:gcd(b,a%b); } int main(){ int T=read(); for(int l=1;l<=T;++l){ int n=read();w=tot=0; printf("Case %d: ",l); for(int i=1;i<=n;++i){ int s=read(); if(s<0){ w++; s=-s; } tot+=s; } int a=tot,b=n-w; if(!b){ printf("inf "); continue; } int c=gcd(a,b); a/=c;b/=c; printf("%d/%d ",a,b); } return 0; }
B-Discovering Gold 掘金
有n个数排成一排，你一开始在位置1。每次你等概率掷出1~6点，然后你将向前走你掷出的点数并且获得新位置上的数。如果新位置超出了n的范围，那你就再扔一次。求最后你期望获得多少。
发个聊天截图好了
这样。
#include<cstdio> #include<cstdlib> #include<cctype> #include<cstring> #include<algorithm> inline long long read(){ long long num=0,f=1; char ch=getchar(); while(!isdigit(ch)){ if(ch=='-') f=-1; ch=getchar(); } while(isdigit(ch)){ num=num*10+ch-'0'; ch=getchar(); } return num*f; } double f[100200]; int cnt; int main(){ int T=read(); while(T--){ cnt++; int n=read(); for(int i=1;i<=n;++i) f[i]=read(); for(int i=n-1;i;--i){ int now=std::min(i+6,n); int tot=0;double start=0; for(int j=i+1;j<=now;++j){ tot++; start+=f[j]; } f[i]+=start/tot; } printf("Case %d: %.10lf ",cnt,f[1]); } return 0; }
C-Race to 1 Again 分解竞速
这道题是我自己想出来的！
以6举例吧 好想点
首先设f(6)是对6进行操作的期望
那么有公式f(6)= ( f(1)+1+f(2)+1+f(3)+1+f(6)+1 )/4
很好想
然后对这个公式变形得到f(6)=( f(1)+f(2)+f(3)+f(6)+4 )/4
因此f(6)-f(6)/4= (f(1)+f(2)+f(3)+4)/4
因此f(6)=(f(1)+f(2)+f(3)+4)/3
这样就很好做啦
#include<cstdio> #include<cstdlib> #include<cmath> #include<cctype> #include<cstring> #include<algorithm> inline long long read(){ long long num=0,f=1; char ch=getchar(); while(!isdigit(ch)){ if(ch=='-') f=-1; ch=getchar(); } while(isdigit(ch)){ num=num*10+ch-'0'; ch=getchar(); } return num*f; } double f[200000]; double dfs(int x){ if(f[x]||x==1) return f[x]; double ans=0; int tot=0,s=sqrt(x); for(int i=2;i<=s;++i){ if(x%i==0){ tot++; ans+=dfs(i)+1; if(i*i!=x){ tot++; ans+=dfs(x/i)+1; } } } tot+=2; ans+=2; ans/=(tot-1); return ans; } int main(){ int T=read(),cnt=0; while(T--){ int n=read(); printf("Case %d: %.10lf ",++cnt,dfs(n)); } return 0; }