钉子和小球
Description
有一个三角形木板,竖直立放，上面钉着n(n+1)/2颗钉子，还有(n+1)个格子（当n=5时如图1）。每颗钉子和周围的钉子的距离都等于d，每个格子的宽度也都等于d，且除了最左端和最右端的格子外每个格子都正对着最下面一排钉子的间隙。
让一个直径略小于d的小球中心正对着最上面的钉子在板上自由滚落，小球每碰到一个钉子都可能落向左边或右边（概率各1/2），且球的中心还会正对着下一颗将要碰上的钉子。例如图2就是小球一条可能的路径。
我们知道小球落在第i个格子中的概率pi=pi=
，其中i为格子的编号，从左至右依次为0,1,…,n。
现在的问题是计算拔掉某些钉子后，小球落在编号为m的格子中的概率pm。假定最下面一排钉子不会被拔掉。例如图3是某些钉子被拔掉后小球一条可能的路径。
Input
第1行为整数n（2 <= n <= 50）和m（0 <= m <= n）。以下n行依次为木板上从上至下n行钉子的信息，每行中’*’表示钉子还在，’.’表示钉子被拔去，注意在这n行中空格符可能出现在任何位置。
Output
仅一行，是一个既约分数(0写成0/1)，为小球落在编号为m的格子中的概pm。既约分数的定义：A/B是既约分数，当且仅当A、B为正整数且A和B没有大于1的公因子。
Sample Input
5 2 * * . * * * * . * * * * * * *
Sample Output
7/16
我的代码
小球落到一个钉子上概率为左上方概率*0.5+右上方概率*0.5+上方直接落下来的概率。dp方程为
dp[i][j]+=0.5*dp[i-1][j-1];
dp[i][j]+=0.5*dp[i-1][j];
dp[i][j]+=dp[i-2][j-1];这一道题困扰我的主要地方在于，如何将结果输出。我一开始是将最上方的钉子设置为1，所以需要进行小数运算，最后得到的数字就是真正的概率，只需要将其转化成既约分数就好了。因为分母一定是2的次方，所以只需要不断×2使之变成整数即可。
最后发现自己错了，不知道错在哪里。上网查询之后，发现大家都是将第一层设置为2^n次方，最后将分子分母的最大公约数除去就可以了，这样就可以不进行小数运算。难道这一题的数据规模不能用double来表示？double的小数位有52个二进制位，此题n最大值为50，应该绰绰有余。所以一定是别的地方有问题，我就先按照普遍的做法写了一遍，然后还是没过。
最后找到原因了，是因为数据类型的问题。即便是long long一个变量，如果是long long x=1，这个1默认的是int类型，需要写成long long x=1LL。
#include<stdio.h>
#include<string.h>
int n,m;
int map[51][51];
long long dp[55][55];
int check(int x,int y)
{
if (y>=1&&y<=x&&x>=1) return 1;
else return 0;
}
long long gcd(long long x, long long y)
{
if(y==0)return x;
return gcd(y,x%y);
}
int main()
{
memset(dp,0,sizeof(dp));
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
{
int temp=0;
char c;
while(temp!=i)
{
c=getchar();
if (c=='*') map[i][++temp]=1;
if (c=='.') map[i][++temp]=0;
}
}
dp[1][1]=1ll<<n;
for (int i=2;i<=n+1;i++)
{
for (int j=1;j<=i;j++)
{
if (check(i-1,j-1))
{
if (map[i-1][j-1])
{
dp[i][j]+=dp[i-1][j-1]/2;
}
}
if (check(i-1,j))
{
if (map[i-1][j])
{
dp[i][j]+=dp[i-1][j]/2;
}
}
if (check(i-2,j-1))
{
if (!map[i-2][j-1])
{
dp[i][j]+=dp[i-2][j-1];
}
}
}
}
long long x=1ll<<n;
long long g=gcd(x,dp[n+1][m+1]);
printf("%lld/%lld\n",dp[n+1][m+1]/g,x/g);
return 0;
}于是一开始的解法的问题也找到了，base也是应该开成long long类型的。
#include<stdio.h>
#include<string.h>
int n,m;
int map[51][51];
double dp[55][55];
int check(int x,int y)
{
if (y>=1&&y<=x&&x>=1) return 1;
else return 0;
}
int main()
{
memset(dp,0,sizeof(dp));
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
{
int temp=0;
char c;
while(temp!=i)
{
c=getchar();
if (c=='*') map[i][++temp]=1;
if (c=='.') map[i][++temp]=0;
}
}
dp[1][1]=1;
for (int i=2;i<=n+1;i++)
{
for (int j=1;j<=i;j++)
{
if (check(i-1,j-1))
{
if (map[i-1][j-1])
{
dp[i][j]+=0.5*dp[i-1][j-1];
}
}
if (check(i-1,j))
{
if (map[i-1][j])
{
dp[i][j]+=0.5*dp[i-1][j];
}
}
if (check(i-2,j-1))
{
if (!map[i-2][j-1])
{
dp[i][j]+=dp[i-2][j-1];
}
}
}
}
double ans=dp[n+1][m+1];
long long int base=1LL;//!!!!!!!!!!!!!!!!!!
while((ans-(int)ans)!=0)
{
base=base*2;
ans=ans*2;
}
printf("%.0f/%lld",ans,base);
return 0;
}反思
写oj的题目空间真的没必要省，但是总是经常忘记。