T1

题目描述

小强想要从$[1, A]$中选出一个整数$x$，从$[1, B]$中选出一个整数$y$。使得满足$\frac{x}{y} = \frac{a}{b}$的同时且$x$和$y$的乘积最大。如果不存在这样的$x$和$y$，请输出“0 0”。

输入描述

输入一行包含四个整数$A$、$B$、$a$和$b$。
$1 \leq A, B, a, b \leq 2e9$

输出描述

输出两个整数表示满足条件的$x$和$y$。若不存在，则输出“0 0”。

示例1

样例输入

1 1 2 1

样例输出

0 0

示例2

样例输入

1000 500 4 2

样例输出

1000 500

示例3

样例输入

1000 500 3 1

样例输出

999 333

算法

(最大公约数，二分) $O(log(n))$

1. 首先求出$a$和$b$的最大公约数，将$a$和$b$约至互质
2. 问题可看成是在$[1, \frac{B}{b}]$范围内求一个最大的值$k$，使得$k \times a$不超过$A$
3. 答案就是将$a$和$b$分别放大$k$倍

时间复杂度

gcd和二分的时间复杂度均为$O(log(n))$，因此总时间复杂度为$O(log(n))$

C++ 代码

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;

typedef long long LL;

LL A, B, a, b;

int main() {
    cin >> A >> B >> a >> b;

    LL d = __gcd(a, b);
    a /= d, b /= d;

    LL l = 1, r = B / b;
    while (l < r) {
        LL mid = l + r + 1 >> 1;
        if (mid * a <= A) l = mid;
        else r = mid - 1;
    }

    if (l * a <= A) cout << l * a << ' ' << l * b;
    else puts("0 0");

    return 0;
}

T2

题目描述

给你$n$个点，编号从0到$n - 1$，有$m$条双向路径，两个点之间可以有多条路径能相互到达，每一条路径中有一个最大边，所有路径的最大边中最小的那个边就是这两个点价值，现在有多次询问，每一次询问是给你一个值$f$，问再这个图中有多少个点对满足这两个点之间的价值不小于$f$，输出满足要求的点对数量。注意：(1, 2)与(2, 1)算两对，若两个点不能到达，则该点对不进行计算。

输入描述

第一行输入一个整数$T$，代表有$T$组测试数据。
对于每一组测试数据，第一行输入2个整数$n$和$m$，代表点的个数以及路径个数。
接下来输入$m$行，每一行三个数$a$、$b$、$c$代表从$a$到$b$有一条长度为$c$的双向路径。
接下来输入一个整数$Q$，代表询问次数。
接下来$q$行，每一行一个整数$f$，代表要查询的值

$1 \leq T \leq 10$
$2 \leq n \leq 10000$
$1 \leq m \leq 500000$
$1 \leq q \leq 100000$
$1 \leq a, b \leq n$
$1 \leq c, f \leq 10^9$

输出描述

对于每组测试数据：输出一个答案代表满足要求的点对有多少个？

示例1

样例输入

2
2 1
0 1 2
3
1
2
3
3 3
0 1 2
0 2 4
1 2 5
5
0
2
3
4
5

样例输出

2
2
0
6
6
4
4
0

算法

(Kruskal) $O(T \times mlog(m))$

1. 两个点的价值一定是最小生成树中这两个点中间的路径中边的最大值
2. 每新加一条边$e$联通两侧的连通块$A$和$B$时，$A$中任意一点到$B$中任意一点，都存在一条路径的最大值为$e$的边权
3. 边权$e$和查询$f$都需要排序，确保查询到$f$的时候，图中只插入了小于等于$f$的边
4. 假设所有边都在的情况下，互通的点对有$sum$个，问题转化为：
   • 添加一条边
   • 查询现在有多少点对联通了，假设有$x$对连通，答案就是$sum - x$
5. 需要实时维护每个连通块的点的个数

时间复杂度

$T$组数据，每组数据排序边的时间为$O(mlog(m))$，排序查询的时间为$O(qlog(q))$，合并并查集并维护查询结果的时间为$O(m + q)$，因此总时间复杂度为$O(T \times mlog(m))$

C++ 代码

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;

const int N = 1e4 + 10, M = 5e5 + 10, Q = 1e5 + 10;

int T, n, m, q;
int p[N], cnt[N], ret[Q];

struct Edge {
    int a, b, v;
    bool operator< (const Edge& e) const {
        return v < e.v;
    }
} edges[M];

struct Query {
    int id, f, cnt;
    bool operator< (const Query& q) const {
        return f < q.f;
    }
} query[Q];

int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main() {
    cin >> T;
    while (T -- ) {
        cin >> n >> m;
        for (int i = 0; i < m; i ++ ) {
            cin >> edges[i].a >> edges[i].b >> edges[i].v;
            edges[i].a ++ , edges[i].b ++ ;
        }

        cin >> q;
        for (int i = 0; i < q; i ++ )
            cin >> query[i].f, query[i].id = i;

        sort(edges, edges + m);
        sort(query, query + q);

        for (int i = 1; i <= n; i ++ ) p[i] = i, cnt[i] = 1;

        int sum = 0, cur = 0;
        for (int i = 0; i < m; i ++ ) {
            while (cur < q && query[cur].f <= edges[i].v)
                query[cur ++ ].cnt = sum;

            int root_a = find(edges[i].a), root_b = find(edges[i].b);

            if (root_a != root_b) {
                sum += cnt[root_a] * cnt[root_b] * 2;
                cnt[root_a] += cnt[root_b];
                p[root_b] = root_a;
            }
        }

        while (cur < q) query[cur ++ ].cnt = sum;

        for (int i = 0; i < q; i ++ ) ret[query[i].id] = sum - query[i].cnt;
        for (int i = 0; i < q; i ++ ) cout << ret[i] << endl;
    }

    return 0;
}