1 条题解

  • 1
    @ 2022-7-21 21:07:37
    #include<bits/stdc++.h>
    using namespace std;
    int read()
    {
    	char c;
    	int w=1;
    	while((c=getchar())>'9'||c<'0')if(c=='-')w=-1;
    	int ans=c-'0';
    	while((c=getchar())>='0'&&c<='9')ans=(ans<<1)+(ans<<3)+c-'0';
    	return ans*w;
    }
    long long gcd(long long a,long long b)//欧几里得算法
    {
    	return b==0?a:gcd(b,a%b);
    }
    struct node
    {
    	long long a,b;
    	void huajian()//让该分数成为既约分数
    	{
    		long long w=gcd(a,b);
    		a=a/w;
    		b/=w;
    	}
    	node operator /(const long long y)const//一个分数除以一个整数
    	{
            node t = *this;
            t.b *= y,t.huajian();
            return t;
    	}
    	node operator +(node y)const//一个分数加上另外一个分数
    	{
    		if(a==0)
    		{
    			y.huajian();
    			return y;
    		}
    		node o=*this;
    		if(y.a==0)
    		{
    			o.huajian();
    			return o;
    		}
    		long long p=gcd(o.b,y.b);
    		o.a*=(y.b/p);o.a+=y.a*(o.b/p);o.b*=(y.b/p);
    		o.huajian();
    		return o;
    	}
    }f[1005][1005];//其实只要开50就够了!
    int n,m;
    int c[1005][1005];
    int main(){
    	n=read();
    	m=read();
    	for(int i=1;i<=n;i++)
    	{
    		for(int j=1;j<=i;j++)
    		{
    			char w;
    			while((w=getchar())!='*'&&w!='.');
    			if(w=='*')c[i][j]=1;
    		}
    	}
    	f[0][1].a=1;//初始化
    	f[0][1].b=1;
    	for(int i=1;i<=n+1;i++)
    	{
    		for(int j=1;j<=n+1;j++)
    		{
    			f[i][j].b=1;//注意要吧所有分数初始化一下,不然除以0化简时会RE
    		}
    	}
    	for(int i=1;i<=n;i++)
    	{
    		for(int j=1;j<=i;j++)
    		{
    			if(c[i][j])
    			{
    				node p=f[i-1][j];//有钉子的时候
    				p=p/2;
    				f[i][j]=f[i][j]+p;
    				f[i][j+1]=f[i][j+1]+p;
    			}
    			else 
    			{
    				f[i+1][j+1]=f[i+1][j+1]+f[i-1][j];//没有钉子的时候
    			}
    		}
    	}
    	for(int i=1;i<=n;i++)
    		for(int j=1;j<=i+1;j++)
    		{
    			f[i][j].huajian();//记得要化简哟!!!
    		}
    	f[n][m+1].huajian();
    	cout<<f[n][m+1].a<<"/"<<f[n][m+1].b<<endl;//cout大发好
    	return 0;
    }
    
    • 1

    信息

    ID
    4672
    时间
    1000ms
    内存
    125MiB
    难度
    5
    标签
    递交数
    2
    已通过
    2
    上传者