14077: 【原4077】玩数

题目

题目描述

author: Hong Kong Regional Contest 2016 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4077

Description

你有一列n个形如2^a*3^b的数（a,b>=0）

你想对他们进行n-1次gcd或lcm，每次取两个并把结果放回

现在要求你进行k-1次gcd，n-k次lcm

最终结果最大、最小分别是多少呢？

Input format

第一行为n(1<=n<=50000)

接下来n行每行两个数ai,bi (0<=ai,bi<=1000) 代表第i个数为2^ai*3^bi

Output format

共输出n行

在第i行输出a,b,a',b'表示k=i时（k-1次gcd，n-k次lcm）的最大结果2^a*3^b与最小结果2^a'*3^b'

Sample input

3
0 0
1 2
2 0

Sample output

2 2 2 2
1 2 0 0
0 0 0 0

Explanation for sample data

三个数分别是1,18,4

k=0:

lcm(1,18,4)=36

k=1:

max: lcm(18,gcd(1,4))=18

min: gcd(1,lcm(18,4))=1

k=2:

gcd(1,18,4)=1

Limits

20%的数据1<=n<=10

60%的数据1<=n<=1000

100%的数据1<=n=50000, 0<=ai,bi<=1000

FineArtz's solution

/* 玩数 */
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

class num{
public:
    num() = default;
    num(int xx, int yy) : x(xx), y(yy) {}
    int x = 0, y = 0;

    bool operator >(const num &n){
        return ((x * log(2) + y * log(3) - n.x * log(2) - n.y * log(3)) > -1e-6);
    }

    friend inline ostream &operator <<(ostream &os, const num &n){
        os << n.x << " " << n.y;
        return os;
    }
};
inline num max(num n1, num n2){
    return num(max(n1.x, n2.x), max(n1.y, n2.y));
}
inline num min(num n1, num n2){
    return num(min(n1.x, n2.x), min(n1.y, n2.y));
}

num a[50005];
num premax[50005], premin[50005], sufmax[50005], sufmin[50005];
num ansmax[50005], ansmin[50005];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i){
        cin >> a[i].x >> a[i].y;
    }
    premax[1] = a[1];
    premin[1] = a[1];
    for (int i = 2; i <= n; ++i){
        premax[i] = max(premax[i - 1], a[i]);
        premin[i] = min(premin[i - 1], a[i]);
    }
    sufmax[n] = a[n];
    sufmin[n] = a[n];
    for (int i = n - 1; i >= 1; --i){
        sufmax[i] = max(sufmax[i + 1], a[i]);
        sufmin[i] = min(sufmin[i + 1], a[i]);
    }
    ansmax[1] = premax[n];
    ansmin[1] = premax[n];
    if (n >= 3){
        num nowmin, minn;
        nowmin = min(a[1], sufmax[2]);
        for (int i = 2; i <= n - 1; ++i){
            minn = max(premax[i - 1], sufmax[i + 1]);
            minn = min(minn, a[i]);
            if (nowmin > minn)
                nowmin = minn;
        }
        minn = min(premax[n - 1], a[n]);
        if (nowmin > minn)
            nowmin = minn;
        ansmin[2] = nowmin;
    }
    if (n > 3){
        ansmax[2] = premax[n];
    }
    for (int k = 3; k <= n - 2; ++k){
        ansmax[k] = premax[n];
        ansmin[k] = premin[n];
    }
    if (n > 3){
        ansmin[n - 1] = premin[n];
    }
    if (n >= 3){
        num nowmax, maxx;
        nowmax = max(a[1], sufmin[2]);
        for (int i = 2; i <= n - 1; ++i){
            maxx = min(premin[i - 1], sufmin[i + 1]);
            maxx = max(maxx, a[i]);
            if (maxx > nowmax)
                nowmax = maxx;
        }
        maxx = max(premin[n - 1], a[n]);
        if (maxx > nowmax)
            nowmax = maxx;
        ansmax[n - 1] = nowmax;
    }
    ansmax[n] = sufmin[1];
    ansmin[n] = sufmin[1];
    for (int i = 1; i <= n; ++i)
        cout << ansmax[i] << " " << ansmin[i] << '\n';
    return 0;
}