上周三讲了概率和概率dp。如果没有涉及其他综合算法，概率这种题主要是思维，先把这部分的东西写完
给个题目链接：https://vjudge.net/contest/365300#problem
HeadShoot
题目大意：玩打枪赌命游戏，已知装弹序列，且装弹和打枪的顺序同一方向，已知上一次是哑炮，打完机械会自动转一节，存活率最大，选择直接SHOOT还是ROTATE之后再射击，
思路：题目已经给了很明显的暗示，已知上一次是哑炮，说明上一次的发生的事件会影响我当前弹夹1/0表示，这是一个条件概率，
如果shoot优选，则0之后更有可能0，状态为，00，P1=00/（00+01）；
如果rotate优选，则0之后再移一位更有可能为0，有 010，000，
结果并不对，是因为题目还有一句话：“you can randomly rotate the gun’s cylinder”，这个旋转是随机的，没有规定只转一节！！！读题又先入为主了。。。
所以如果rotate优选，则此时相当于求一个混乱旋转后求概率，那么上一个是不是0这个前提后面的影响，就几乎没有了，所以，P2=0/（n）；
按照顺序，从头检查到成一个环（不是到尾），检查完整个长度，头可以从任意位置开始，检查0，01和00的个数，比较P1，P2，化成乘法即可
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<string> 6 using namespace std; 7 const string e="EQUAL",r="ROTATE",s="SHOOT"; 8 9 char a[1005]; 10 int x,y,t; 11 int main () { 12 memset(a,0,sizeof(a)); 13 while(cin>>a) { 14 15 x=0; 16 t=0; 17 int l=strlen(a); 18 19 for(int i=0; i<l; i++) { 20 if(a[i]=='0') { 21 t++; 22 int g=(i+1)%l; 23 if(a[g]=='0') { 24 x++; 25 } 26 } 27 } 28 29 if(x*l<t*t)cout<<r; 30 if(x*l==t*t)cout<<e; 31 if(x*l>t*t)cout<<s; 32 puts(""); 33 memset(a,0,sizeof(a)); 34 } 35 36 37 38 return 0; 39 }
------
Cows and Cars
大前提：主持人开的门后面只有可能是牛。主持人相当于排除了一部分牛，那剩下的工作就是算，排除之后，总的门数，含车的门数
一定换门，所以n-1-show为剩下的总数，车的数目为一个不确定的值，因为并不知道一开始选了什么，需要分情况
- 一开始是牛，那条件是cow/n，车总数不变，还是car，写成（cow/n）*car/（n-1-show）
- 一开始是车，条件是car/n，车总数-1，car-1，写成（car/n）*（car-1）/（n-1-show）
叠加两种情况即可（贝叶斯）保证精度，先乘后除
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<string> 6 using namespace std; 7 double cow,car,show; 8 9 int main() { 10 while(cin>>cow>>car>>show) { 11 double n=cow+car; 12 printf("%.5f ",car*(car-1.0)/n/(n-1.0-show)+cow*car/n/(n-1.0-show)); 13 14 } 15 return 0; 16 }
Joining with Friend（坑题）
题意：你会在[t1,t2]时刻到，你朋友会在[s1,s2]时刻到，两个人都停留w，问两人碰面的概率
就是很典型的几何概率，概率统计的原题，P=相交阴影面积（交集）/总面积（并集），
一开始，打算分开两条直线讨论，分类讨论阴影面积的情形，没有普遍性，算的要死掉
结果情况实在是太多了，写又写不全，实在是难受（占个坑后面看看能不能写上）
不是只有缺小三角形的情形！！！！上面那条直线可以划到下面！！WA到吐
所以可以用 上面直线下边的面积（s1+s2）-下面直线下边的面积（s1）
1 #include<cstdio> 2 using namespace std; 3 int t,s1,s2,t1,t2,w; 4 double solve(int w) { 5 if(t2+w<=s1) return 0; 6 if(t1+w>=s2) return (s2-s1)*(t2-t1); 7 if(s1-w<=t1) { // left 8 if(s2-w>=t2)//right 9 return 0.5*(t1+w-s1+t2+w-s1)*(t2-t1); 10 else//up 11 return (s2-s1)*(t2-t1)-0.5*(s2-(t1+w))*(s2-w-t1); 12 } else { //down 13 if(t2+w<s2) //right 14 return 0.5*(t2-(s1-w))*(t2+w-s1); 15 else //up 16 return 0.5*(t2-(s2-w)+t2-(s1-w))*(s2-s1); 17 } 18 } 19 int main() { 20 scanf("%d",&t); 21 for(int tt=1; tt<=t; tt++) { 22 scanf("%lf%lf%lf%lf%lf",&s1,&s2,&t1,&t2,&w); 23 double ans=solve(w)-solve(-w); 24 printf("Case #%d: %.8lf ",tt,ans/((t2-t1)*(s2-s1))); 25 } 26 }
Standard Deviation UVA - 10886
给定一个随机数发生器, 用以下代码实现;
1 unsigned long long seed; 2 long double gen() { 3 static const long double Z = ( long double )1.0 / (1LL<<32); 4 seed >>= 16; 5 seed &= ( 1ULL << 32 ) - 1; 6 seed *= seed; 7 return seed * Z; 8 }
输入seed的初始值，你的任务是求出它得到的前n个随机数标准差，保留小数点后5位(1<=n<=10000000,0<=seed<264)。
计算标准差，难点就是精度, 如果直接模拟, 用最高精度的 long double 试了一下,暴力可过
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<string> 6 #include <cmath> 7 using namespace std; 8 typedef long long ll; 9 unsigned long long seed; 10 const ll M=10000000+5; 11 long double gen() { 12 static const long double Z = ( long double )1.0 / (1LL<<32); 13 seed >>= 16; 14 seed &= ( 1ULL << 32 ) - 1; 15 seed *= seed; 16 return seed * Z; 17 } 18 int N; 19 int n; 20 long double a[M]; 21 long double sum; 22 long double ans; 23 int main() { 24 cin>>N; 25 int k=0; 26 while(N--) { 27 k++; 28 memset(a,0,sizeof(a)); 29 scanf("%d%llu",&n,&seed); 30 sum=0; 31 ans=0; 32 for(int i=1; i<=n; i++) { 33 a[i]=gen(); 34 sum+=a[i]; 35 } 36 sum/=n; 37 for(int i=1; i<=n; i++) { 38 ans+=(a[i]-sum)*(a[i]-sum); 39 } 40 ans/=n; 41 ans=sqrt(ans); 42 printf("Case #%d: %.5Lf ",k,ans); 43 } 44 return 0; 45 }
如果要优化, 关键是化简计算式子，因为如果按照先加再除的办法，肯定存不下，这个平方公式还是很明显的
分开算就可以了