P8584 探索未知 题解

· · 题解

题目大意

给定 n 个分数 \dfrac{a_i}{b_i}，并且给出 opt_i，当 opt_i 为 1 时表示在总数上加上 \dfrac{a_i}{b_i}，当 opt_i 为 2 时表示在总数上减去 \dfrac{a_i}{b_i}，求最后的总和。

解决

本题模拟即可。

对于两个分数 \dfrac{x_1}{y_1} 和 \dfrac{x_2}{y_2} 相加，我们可以通分，即 \dfrac{x_1 \times y_2}{y_1 \times y_2} 和 \dfrac{x_2 \times y_1}{y_2 \times y_1} 相加，结果为 \dfrac{x_1 \times y_2 + x_2 \times y_1}{y_1 \times y_2}。

对于两个分数 \dfrac{x_1}{y_1} 和 \dfrac{x_2}{y_2} 相减，同上，即 \dfrac{x_1 \times y_2}{y_1 \times y_2} 和 \dfrac{x_2 \times y_1}{y_2 \times y_1} 相减，结果为 \dfrac{x_1 \times y_2 - x_2 \times y_1}{y_1 \times y_2}。

除了以上大致解法，我们还要考虑一些特殊情况，例如 \dfrac{6}{3} 这种可以约分的，还有 \dfrac{-6}{-5} 和 \dfrac{6}{-5} 这种负号有误的，都需要想到。

赛时代码

#include<bits/stdc++.h>
using namespace std;
namespace IO//感谢出题人给的快读模板
{
    char ibuf[(1<<20)+1],*iS,*iT;
    #if ONLINE_JUDGE
    #define gh() (iS==iT?iT=(iS=ibuf)+fread(ibuf,1,(1<<20)+1,stdin),(iS==iT?EOF:*iS++):*iS++)
    #else
    #define gh() getchar()
    #endif
    #define reg register
    inline long long read()
    {
        reg char ch=gh();
        reg long long x=0;
        reg char t=0;
        while(ch<'0'||ch>'9')   t|=ch=='-',ch=gh();
        while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=gh();
        return t?-x:x;
    }
}
using IO::read;
inline long long gcd(long long m,long long n)
{
    return n?gcd(n,m%n):m;
}
long long n,a,b,ra,rb,GCD,op;//a为分子，b为分母
int main()
{
    n=read(),ra=read(),rb=read(),op=read(),n--;
    if(op==2) ra=-1*ra;
    while(n--)
    {
        a=read(),b=read(),op=read();
        if(op==1) ra=ra*b+rb*a,rb=rb*b;
        else ra=ra*b-rb*a,rb=rb*b;
        GCD=gcd(ra,rb),ra/=GCD,rb/=GCD;
    }
    if(ra*rb<0) ra=-1*abs(ra),rb=abs(rb);
    if(ra<0 && rb<0) ra=abs(ra),rb=abs(rb);
    if(ra%rb==0) printf("%lld",ra/rb);
    else printf("%lld/%lld",ra,rb);
    return 0;
}