从这半周刷博客来看，有点着急了，一些基础的概率知识还没完全弄明白就看博客还是有点吃亏的，就连基本的概率集邮问题都没完全弄明白。更尴尬的是前天牛客比赛也有不太难的概率题，但是。。。QAQ。
整理下题目吧。
Wannafly7 小Q与氪金游戏
题意：在这个游戏中，氪一单可以得到x个宝石，而抽一次卡需要花费y个宝石，由于游戏策划十分“良心”，抽卡是独立重复实验，单次抽出目标角色卡的概率是p且不存在所谓的“保底”。
为了尽可能省钱，小Q同学只会在抽卡所需宝石不足的情况下再氪一单，并且抽出目标角色卡之后会立即停止抽卡，他想知道为了抽出目标角色卡期望要氪多少单。
其实这就是一个离散概率类的题，抽1次单就成的概率是p，2次是p*(1-p)，3次是p*(1-p)^2......n次是p*(1-p)^(n-1)，然后用它们乘以分别氪金的单数就是期望，因为这个数越来越小，所以一直算当它的波动远远小于精度要求的时候跳出来输出答案就可以了。我居然一直纠结应该算到抽几次，导致一直没输出正确答案。。感觉快被自己蠢哭了。
#define ll long long
#define epx 1e-15
using namespace std;
int main()
{
int x,y,p;
scanf("%d%d%d",&x,&y,&p);
double ans=0;
long long i,j;
for(i=1;;i++)
{
double res=((p*1.0)/10000)*pow(((10000-p)*1.0)/10000,i-1);//p*(1-p)^(k-1)
long long cnt;
if ((i*y)%x==0) cnt=(i*y)/x;//算出氪金单数
else cnt=(i*y)/x+1;
res=res*cnt;
if (res<epx) break;//精度达到要求
else ans+=res;
}
printf("%.13f\n",ans);
return 0;
}
总结下面这道题前先补充一下最近新学的一块板子——高斯消元法
其实高斯消元也没什么稀奇的，就是和高代讲的一样的思路，将方程组用矩阵表示出来，用最上面的元素化简下面的最后形成一个上三角矩阵，然后回带。我讲的不好，还是推荐下面几位大佬讲的博客吧。顺便存一下模版。
http://blog.csdn.net/u010182633/article/details/45225179
http://blog.csdn.net/qq_26025363/article/details/53027926
#include<iostream>//这是第二个博主大佬的板子。
using namespace std;
const int n = 3;
void gaussin(double a[n][n], double b[n])
{
//判断能否用高斯消元法，如果矩阵主对角线上有0元素存在是不能用的
for (int i = 0; i < n; i++)
if (a[i][i] == 0)
{
cout << "can't use gaussin meathod" << endl;
return;
}
int i, j, k;
double c[n]; //存储初等行变换的系数，用于行的相减
//消元的整个过程如下，总共n-1次消元过程。
for (k = 0; k < n - 1; k++)
{
//求出第K次初等行变换的系数
for (i = k + 1; i < n; i++)
c[i] = a[i][k] / a[k][k];
//第K次的消元计算
for (i = k + 1; i < n; i++)
{
for (j = 0; j < n; j++)
{
a[i][j] = a[i][j] - c[i] * a[k][j];
}
b[i] = b[i] - c[i] * b[k];
}
}
//解的存储数组
double x[n];
//先计算出最后一个未知数；
x[n - 1] = b[n - 1] / a[n - 1][n - 1];
//求出每个未知数的值
for (i = n - 2; i >= 0; i--)
{
double sum = 0;
for (j = i + 1; j < n; j++)
{
sum += a[i][j] * x[j];
}
x[i] = (b[i] - sum) / a[i][i];
}
cout << " the solution of the equations is:" << endl;
cout << endl;
for (i = 0; i < n; i++)
cout <<"x"<<i+1<<"="<< x[i] << endl;
}
LighOj 1151 Snakes and Ladders
题意：有100个格子，从1开始走，每次抛骰子走1到6，若抛出的点数导致走出了100以外，则重新抛一次。有n个格子会单向传送到其他格子，mp[i]表示从i传送到mp[i]。1和100不会有传送，一个格子也不会有两种传送。问走到100的期望值。
还是用概率dp，设dp[i]为从i走出去的期望次数。1，当 i 位置没有传送时，dp[i]=(dp[i+1]+1+dp[i+2]+1...dp[i+6]+1)/6。2，当 i 位置有传送时dp[i]=dp[mp[i]]。因为传送通道的随意性，不能再用递推法解，那么这就要用高斯消元法。将两个公式变一下行，展开将dp[i]前的系数作为矩阵系数，高斯消元解出dp[1]的值。在存储并推荐两个大佬的博客
http://www.cnblogs.com/jiachinzhao/p/7204458.html
http://blog.sina.com.cn/s/blog_140e100580102vtq1.html
LightOj 1284 Grid
题意：在一个三维的空间，每个点都有一盏灯，开始全是关的。现在每次随机选两个点，把两个点之间的全部点，开关都按一遍；问ｋ次过后开着的灯的期望数量；
这道题的解题方法很重要，推荐博客：http://blog.csdn.net/kevin66654/article/details/52101980
首先考虑设一个点(x,y,z)，如果在范围内，那么必定x1<=x<=x2，也就是1-（不在范围内的概率），也就是选了两个属于恰好都在x一边的概率。在区间内的概率=1-区间在该点的同一侧的概率。该点状态会改变的概率p=x维在区间内的概率*y维在区间内的概率*z维在区间内的概率。
设F（n）表示n次中改变了奇数次。设G（n）表示n次中改变了偶数次
那么，G（n）=1-F（n）且F（n）=F（n-1）*（1-p）+G（n-1）*p
可以解得F（n）=F（n-1）*（1-2p）+p，初始值为F（0）=0，F（1）=p
左右两边同时除以（1-2p）^n，得到一个可以迭代的式子，根据边界条件，计算得：F（n）=0.5-0.5*（1-2p）^n
double fastpow (double a, int b)//快乘
{
double ret = 1;
while (b)
{
if (b & 1) ret = ret * a;
a = a * a;
b >>= 1;
}
return ret;
}
double P(int i,int x)//算出在1到x中在 i 的两边的概率
{
return 1.0-1.0*((i-1)*(i-1)+(x-i)*(x-i))/(x*x);
}
int main()
{
int T,Case=0;
int x,y,z,k;
cin>>T;
while(T--)
{
double ans=0.0;
scanf("%d%d%d%d",&x,&y,&z,&k);
for(int i=1;i<=x;i++)
{
for(int j=1;j<=y;j++)
{
for(int t=1;t<=z;t++)
{
double ret=P(i,x)*P(j,y)*P(t,z);
ans+=0.5-0.5*fastpow(1-2*ret,k);//最后带入公式
}
}
}
printf("Case %d: %.7lf\n",++Case,ans);
}
}
接下来还是要回归课本，静下心来好好看一遍。