HDU 5912 Fraction

题目来源：2016 CCPC 长春站

题意：青蛙先生想计算一个式子的值，输入两个数列a[],b[]求出最后的分子和分母

思路：一开始看到这个图片首先想到的是递归实现，递归部分始终计算的是右下部分

/*************************************************************************

    > File Name: A.cpp

    > Author:    WArobot

    > Mail:      768059009@qq.com

    > Created Time: 2017年04月15日 星期六 21时10分45秒

 ************************************************************************/

#include<bits/stdc++.h>

#include<cstdio>

using namespace std;

long long n,a[100],b[100];

long long p,q;

void fun(long long  step,long long z,long long m){

	long long t1 = m*b[step-1] , t2 = m*a[step-1]+z;

	if(step==1)	{

		p = t1 ;	q = t2 ;

		return;

	}

	fun(step-1, t1 , t2 );

}

int gcd(long long  a,long long  b){

	return b==0?a:gcd(b,a%b);

}

int main(){

	int t,kase = 0;

	scanf("%d",&t);

	while(t--){

		scanf("%lld",&n);

		for(int i=0;i<n;i++)	scanf("%lld",a+i);

		for(int i=0;i<n;i++)	scanf("%lld",b+i);

		p = q = 0;

		if(n<=1)	p = b[0] , q = a[0];

		else		fun(n-1,b[n-1],a[n-1]);

		int d = gcd(p,q);

		if(d!=0){

			p /= d;  q /= d;

		}

		printf("Case #%d: %lld %lld\n",++kase,p,q);

	}

	return 0;

}

后来一想为啥非得要用递归做......

/*************************************************************************

    > File Name: A2.cpp

    > Author:    WArobot

    > Mail:      768059009@qq.com

    > Created Time: 2017年04月16日 星期日 20时35分55秒

 ************************************************************************/

#include<bits/stdc++.h>

using namespace std;

int t , kase = 0 , n;

int a[100] , b[100];

int p,q;  // p为分子 q为分母

int gcd(int a,int b){

	return b==0?a:gcd(b,a%b);

}

void solve(){

	p = b[n-1] , q = a[n-1];

	for(int i=n-2;i>=0;i--){

		int t1 = p , t2 = q;

		p = t2*b[i];

		q = t2*a[i] + t1;

	}

	int d = gcd(p,q);

	p /= d; q /= d;

}

int main(){

	int kase = 0;

	scanf("%d",&t);

	while(t--){

		scanf("%d",&n);

		for(int i=0;i<n;i++) scanf("%d",a+i);

		for(int i=0;i<n;i++) scanf("%d",b+i);

		solve();

		printf("Case #%d: %d %d\n",++kase,p,q);

	}

	return 0;

}

巴特西

HDU 5912 Fraction

最新文章

热门文章