LightOJ 1027 A Dangerous Maze:
预先求出递推式，最后通过公式直接计算。
代码语言：javascript复制#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
int gcd(int a, int b){
if (b == 0)
return a;
return gcd(b, a%b);
}
int main(){
int T;
scanf("%d", &T);
for (int t = 1; t <= T; t ){
int n;
scanf("%d", &n);
int p = 0, q = n,num;
for (int i = 1; i <= n; i ){
scanf("%d", &num);
if (num < 0){
q--;
p -= num;
}
else{
p = num;
}
}
if (q == 0){
printf("Case %d: infn",t);
}
else{
int div = gcd(p, q);
printf("Case %d: %d/%dn",t,p/div,q/div);
}
}
}LightOJ 1284 Lights inside 3D Grid:
要判断经过k次变换后的开灯的数目，我们可以先计算对于每一个cell而言，在经历了k次变换后，仍然开灯的期望，最后将每一个cell的期望相加即可。
有一个M*N*P的立方体，每次随机选两个格子，把它们之间的灯全打开（如果已经是打开的就关闭），经过K次操作之后开着的灯的个数的期望是多少。
把每个灯经过K次操作亮着的概率P求出来，因为每个灯是独立的，最后的期望也就是:
对于一个灯来说， 设f[i]是经过i次操作亮着的概率，g[i]是经过i次操作不亮的概率，则有f[i] p[i]=1,f[i]=f[i-1]*(1-p) g[i-1]*p，这里的p是操作一次能操作到这个灯的概率。
通过这两个式子，能得到f[i]=f[i-1]*(1-2p) p，两边加上b/(a-1)，也就是0.5，成为等比数列，最后得到f[i]=0.5-0.5*(1-2p)^i。
那么只要对每个灯求出p就能算出答案了。能操作到这个灯等价于选的两个点的坐标在x轴，y轴，z轴都分别在这个灯坐标的两侧，对每个轴分别算符合的情况，然后相乘，最后除以所有情况就是概率。
代码语言：javascript复制#include <cstdio>
#include <cmath>
double Get (int a,int b)
{
return 1.0*b*b-(a-1)*(a-1)-(b-a)*(b-a);
}
int main ()
{
int T;
scanf("%d",&T);
for (int Cas=1;Cas<=T;Cas )
{
int x,y,z,n;
scanf("%d%d%d%d",&x,&y,&z,&n);
double ans=0,p,t=1.0*x*x*y*y*z*z;
for (int i=1;i<=x;i )
for (int j=1;j<=y;j )
for (int k=1;k<=z;k )
{
p=1.0*Get(i,x)*Get(j,y)*Get(k,z)/t;
ans =0.5-0.5*pow(1-2*p,1.0*n);
}
printf("Case %d: %lfn",Cas,ans);
}
return 0;
}
