bzoj2187 fraction&&hdu3637 Find a Fraction—

bzoj2187

多组询问，每次给出 $a, b, c, d$，求满足 $\frac{a}{b} < \frac{p}{q} < \frac{c}{d}$ 的所有二元组 $(p, q)$ 中 $p$ 为第一关键字，$q$ 为第二关键字排出来的字典序最小的那一对。

分析:

设计函数 $f(a,b,p,q,c,d)$.

按照题目中保证 $q$ 最小的要求考虑该函数的几个边界：

1. $\left \lfloor \frac{a}{b} \right \rfloor-1 \leq \left \lceil \frac{c}{d} \right \rceil-1$，这个时候 $p = \left \lfloor \frac{a}{b} \right \rfloor+1, q=1$ 时字典序最小

2. $a=0$ 时，这个时候 $0 < \frac{p}{q} < \frac{c}{d} \Rightarrow q > \frac{dp}{c}$，显然 $p=1, q=\left \lfloor \frac{c}{d} \right \rfloor+1$ 时字典序最小

然后考虑辗转相除缩小问题规模：

1. $a > b\ or \ c > d$：原式等价于：$\frac{a\%b}{b} < \frac{p}{q}-\left \lfloor \frac{a}{b} \right \rfloor < \frac{c}{d}-\left \lfloor \frac{a}{b} \right \rfloor$

即：$f(a, b, p, q, c,d) = f(a \% b, b, p, q, c-{\left \lfloor \frac{a}{b} \right \rfloor}d), p+= {\left \lfloor \frac{a}{b} \right \rfloor}q$.

2. $a \leq b \ and \ c \leq d$：原式等价于：$\frac{d}{c} < \frac{q}{p} < \frac{b}{a}$.

即：$f(a,b,p,q,c,d) = f(d,c,q,p,b,a)$，这样就回到了第一步。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

ll a, b, c, d, p, q;

inline ll gcd(ll a, ll b){while(b){ll t=a; a=b; b=t-t/a*a;} return a;}

inline void calc(ll& a, ll& b){ll d= gcd(a, b); a/=d; b /= d;}

inline void f(ll a, ll b, ll& p, ll& q, ll c, ll d)

{

    //calc(a, b); calc(c, d);       //可以不用

    if(!a){p=; q=d/c+; return;}

    ll x = a/b+, y = c/d+(c%d>)-;

    if(x <= y){q=, p=x; return;}

    if(a <= b && c <= d)   f(d, c, q, p, b, a);

    else{ f(a%b, b, p, q, c-a/b*d, d); p += a/b*q;}

}

int main()

{

    while(scanf("%lld%lld%lld%lld", &a, &b, &c, &d) == )

    {

        f(a, b, p, q, c, d);

        printf("%lld/%lld\n", p, q);

    }

    return ;

}

hdu3637

给出两个非负有理数 $A, B$（$A < B$），你的任务是发现一个分数介于A和B，在这个区间内可能有许多分数，请输出分子加分母和最小的分数。

分析：

首先，解决输入问题，无线循环小数很容易转换成分数。

因为0.[1]=1/9, 0.0[1]=1/99, 0.00[1]=1/999...

将小数分成括号部分和非括号部分即可。

问题转换成求 $\frac{a}{b} < \frac{p}{q} < \frac{c}{d}$，且 $p+q$ 最小。

可以推导出 $p$ 最小时，$p+q$ 就最小，于是套类欧几里得模板即可。

//交上去会MLE，不知道咋解决

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

ll a, b, c, d, p, q;

inline ll gcd(ll a, ll b){while(b){ll t=a; a=b; b=t-t/a*a;} return a;}

inline void calc(ll& a, ll& b){ll d= gcd(a, b); a/=d; b /= d;}

inline void f(ll a, ll b, ll& p, ll& q, ll c, ll d)

{

    //calc(a, b); calc(c, d);       //可以不用

    if(!a){p=; q=d/c+; return;}

    ll x = a/b+, y = c/d+(c%d>)-;

    if(x <= y){q=, p=x; return;}

    if(a <= b && c <= d)   f(d, c, q, p, b, a);

    else{ f(a%b, b, p, q, c-a/b*d, d); p += a/b*q;}

}

char s[];

void input(ll& a, ll& b)

{

    scanf("%s", s);

    int len = strlen(s);

    ll tmp1 = , tmp2 = , flag = , is_point=, is_kh=, cnt1=, cnt2=;

    for(int i = ;i < len;i++)

    {

        if(s[i] == ']')  continue;

        if(s[i] == '.'){is_point=;continue;}

        if(s[i] == '['){is_kh=;continue;}

        if(is_point&&!is_kh)  cnt1 = cnt1*;

        if(is_point)  cnt2 = cnt2*+;

        if((!is_kh)) tmp1 =  tmp1* + (s[i]-'');

        else  tmp2 = tmp2* + (s[i]-'');

    }

    calc(tmp1, cnt1);

    if(cnt2 == )

    {

        calc(tmp2, cnt2);

        a = tmp1, b=cnt1;

    }

    else  a = tmp1*cnt2+tmp2*cnt1, b=cnt1*cnt2;

    if(!a) calc(a, b);

}

int main()

{

    int T, kase=;

    scanf("%d", &T);

    while(T--)

    {

        input(a, b);input(c, d);

        //printf("%lld %lld %lld %lld\n", a, b, c, d);

        f(a, b, p, q, c, d);

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

    }

    return ;

}

参考链接：

1. https://blog.csdn.net/dreaming__ldx/article/details/86769792

2. https://blog.csdn.net/hqd_acm/article/details/6648027

巴特西

bzoj2187 fraction&&hdu3637 Find a Fraction——类欧几里得

bzoj2187

hdu3637

最新文章

热门文章