【二分好题】

名人名言

image

Um_nik: Stop learning useless algorithms, go and solve some problems, learn how to use binary search!

题目

背包 HLP3461

题目描述

\(n\) 个物品,每个物品有对应的价格和价值

\(m\) 次询问,每次询问会有 \(c\) 的本金,之后无脑选择能买得起的最贵物品买走(若有多个最贵的就选价值最高的),直到不能买为止,问买走的物品价值和。(\(n \leq 10 ^ 5\)

解题思路

首先对物品先按价格, 后按价值从大到小排序。

注意到对于每次购买一段东西,本金减少至少一半,所以消费的次数为 \(O(\log\ n)\) 级别的

这时候我们知道这次购买的右端点 \(r\) (即上次购买的最后一个的下一个), 则可以利用前缀和求出左端点 \(l\)

代码

#include <bits/stdc++.h>
#define int long long
const int N = 1e5 + 5, inf = 1e18;
int n, m, x, ans, last;
int sum[N], v[N];
struct product {
	int a, b;
	bool operator < (const product &x) const {return a == x.a ? b > x.b : a > x.a;}
} a[N];
signed main() {
	scanf("%lld%lld", &n, &m);
	for (int i = 1; i <= n; ++i) scanf("%lld%lld", &a[i].a, &a[i].b);
	std::sort(a + 1, a + n + 1);
	for (int i = 1; i <= n; ++i) sum[i] = a[i].a + sum[i - 1];
	for (int i=  1; i <= n; ++i) v[i] = a[i].b + v[i - 1];
	while (m--) {
		scanf("%lld", &x);
		last = ans = 0;
		while (x) {
			int l = std::lower_bound(a + last + 1, a + n + 1, (product){x, inf}) - a;
			if (l > n) break;
			int r = std::upper_bound(sum + l + 1, sum + n + 1, x - a[l - 1].a) - sum - 1;
			x -= sum[r] - sum[l - 1], ans += v[r] - v[l - 1];
			last = r;
		} printf("%lld\n", ans);
	} return 0;
}

植树 HLP3915

题目描述

\(n\) 个点 \(m\) 条边,边从 \(1\)\(m\) 编号。要求把 \([1, m]\) 划分成尽可能多个区间,使得对于每个区间内的边,都有一个子集能构成一棵边权和不超过 \(S\) 的生成树。

多组数据, \(T \leq 5, 2 \leq n, m \leq 10 ^ 5, s \leq 10 ^ 9。\)

解题思路

如果对每个左端点都进行二分,那么注意到,每次Check的复杂度是 \(O(k\ \log\ k)\) 的,最坏情况下会有 \(O(\frac{m ^ 2}{n}\ \log^2\ m)\) 的复杂度,喜提 \(TLE\)

对于这种情况,我们一般有两种办法:

  • 数据分块

  • 改进二分

1. 数据分块

\(n, m \leq 10 ^ 5\) 的数据范围下, \(O(\frac{m ^ 2}{n}\ \log^2\ m)\) 的复杂度在 \(n\) 较小时就炸掉了,于是考虑针对 \(n\) 的大小进行数据分块

注意到,如果我们直接往里面加边并动态维护最小生成树,直到形成一个满足条件的生成树后把图清空。这样的做法是 \(O(nm)\)

至于如何动态维护最小生成树,可以在加边时直接暴力求出𝑥,𝑦到𝐿𝐶𝐴上的边权最大值,然后判断是否更新,每次更新也可以 \(O(n)\) 进行

可以发现,此时复杂度为 \(min(O(\frac{m ^ 2}{n}\ \log^2\ m), O(nm)) \approx m\sqrt{m}\ \log\ m\),可以卡过。

2. 改进二分

我们发现,直接二分炸掉的原因是每次二分我们都会直接判断一个长度为 \(\frac{m}{2}\) 的区间,那么当答案远小于这个数值时就会造成极大的时间浪费

于是考虑倍增,先从小的区间开始判断,然后一直倍增区间的大小直到判断成功,之后再二分求解。这样如果对应答案为 \(k\),那么判断次数就是 \(O(\log\ k)\) 次的

于是对于每个答案是 \(k\) 的区间,花费的复杂度都是 \(O(k \\log ^ 2k)\),总的复杂度就是 \(O(m \\log ^ 2\ m)\),可以通过本题。

代码

#include <bits/stdc++.h>
const int N = 1e5 + 10;
struct node {int u, v, w;};
int n, m, s, fa[N], size[N];
node e[N], g[N];
int get(int x) {return x == fa[x] ? x : fa[x] = get(fa[x]);}
bool check(int l, int r) {
    int ans = 0;
    for (int i = 1; i <= n; ++i) fa[i] = i, size[i] = 1;
    for (int i = l; i <= r; ++i) g[i] = e[i];
    std::sort(g + l, g + r + 1, [&](node a, node b) {return a.w < b.w;});
    for (int i = l; i <= r; ++i) {
        int x = get(g[i].u), y = get(g[i].v);
        if (x != y) {
            int s1 = size[x], s2 = size[y];
            if (s1 < s2) std::swap(x, y);
            fa[y] = x; size[x] += size[y]; ans += g[i].w;
            if (ans > s) return false;
        }
    } int x = get(fa[1]);
    for (int i = 1; i <= n; ++i) if (get(i) != x) return false;
    return true;
}
signed main() {
    int t; scanf("%d", &t);
    while (t--) {
        scanf("%d%d%d", &n, &m, &s);
        for (int i = 1, u, v, w; i <= m; ++i) {
            scanf("%d%d%d", &u, &v, &w);
            e[i] = (node){u, v, w};
        } int ans = 0;
        for (int i = 1, j; i <= m; ++i) {
            for (j = n - 1; i + j - 1 <= m; j <<= 1)
                if (check(i, i + j - 1)) break;
            int l = i, r = std::min(m, i + j - 1);
            if (!check(i, r)) break;
            while (l < r) {
                int mid = l + r >> 1;
                if (check(i, mid)) r = mid;
                else l = mid + 1;
            } ++ ans, i = l;
        } printf("%d\n", ans);
    } return 0;
}

Cow and Fields CF1307D

题目描述

给定一个 \(n\) 个点 \(m\) 条边的简单无向连通图,并指定 \(k\) 个特殊点。要求在特殊点之间加一条边使得 \(1\)\(n\) 的最短路最大,求对应的最大值。(\(n, m \leq 2 \times 10 ^ 5\)

解题思路

考虑加入一条边 \(s-t\), 该条边产生的贡献为 \(min(dis[1][s] + dis[t][n], dis[1][t] + dis[s][n]) + 1\)

那么我们只要正反跑两遍 \(BFS\)(因为边权都为 \(1\)),处理出每个点到 \(1\)\(n\) 的距离,再将上式取个 \(max\),最后与原先最短路比较一下。

奇技淫巧

考虑钦定 \(dis[1][s] + dis[t][n] < dis[1][t] + dis[s][n]\),这样通过移项后就可以变成 \(dis[1][s] – dis[s][n] < dis[1][t] – dis[t][n]\)

那么按照 \(dis(1, i) – dis(n, i)\) 的值进行升序排序,这样就能保证 \(i < j\)时,连 \(i, j\) 产生的贡献一定是 \(dis[1][i] + dis[j][n] + 1\),前后缀扫一扫就好了

二分做法

  • 直接二分答案 \(w\)

  • 接下去就是要判断是否存在 \(s,t\),使得 \(min(dis[1][s] + dis[t][n], dis[1][t] + dis[s][n]) + 1 \geq w\)

  • 枚举 \(s\),可将问题变成判断是否存在 \(t\) 使得,\(a_t \geq 𝑤_1, b_t \geq w_2\)

  • 那么提前按照 \(dis[1][s]\) 的值排好序,就可以保证询问时 \(𝑤_1\) 是降序的,维护所有满足 \(a_t \geq w_1\) 的所有 \(t\) 对应的 \(b_t\) 值,类似双指针的做法不断插入并用树状数组维护即可

  • 时间复杂度 \(O(n\ \log ^ 2 ⁡n)\),看似多了个 \(\log\) 但实际上跑得飞快。

  • 实际上要维护的只是判断是否存在 \(b_t \geq w_2\),所以只需要维护最大值,\(O(n\ \log\ n)\)即可。

代码

#include <bits/stdc++.h>
using pii = std::pair<int, int>;
const int N = 2e5 + 5, inf = 1e9 + 7;
int n, m, k, ans, pre;
int a[N], dis[2][N];
bool vis[N];
std::vector<pii> d;
std::vector<int> Graph[N];
void Bfs(int *dist, int st) {
    std::queue<int> q; q.emplace(st); dist[st] = 0;
    for (int i = 1; i <= n; ++i) vis[i] = false; vis[st] = true;
    while (q.size()) {
        int t = q.front(); q.pop();
        for (auto p : Graph[t])
            if (!vis[p]) {
                vis[p] = true;
                dist[p] = dist[t] + 1;
                q.emplace(p);
            }
    } return void();
}
signed main() {
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= k; ++i) scanf("%d", a + i);
    for (int i = 1, u, v; i <= m; ++i) scanf("%d%d", &u, &v), Graph[u].emplace_back(v), Graph[v].emplace_back(u);
    Bfs(dis[0], 1), Bfs(dis[1], n);
	for (int i = 1; i <= k; ++i) d.emplace_back(pii(dis[0][a[i]] - dis[1][a[i]], a[i]));
    std::sort(d.begin(), d.end()); pre = -inf;
    for (auto it : d) {
        int x = it.second;
        ans = std::max(ans, dis[1][x] + pre);
        pre = std::max(pre, dis[0][x]);
    } return printf("%d\n", std::min(dis[0][n], ans + 1)), 0;
}

Complete The Graph CF715B

题目描述

给定一个无向带权图,其中有一些边的边权尚未确定。要求确定这些边的边权 $ w \in [1, 10 ^{18}]$,使得从 \(s\)\(t\) 的最短路为给定值 \(L\),需要判断是否有解。

\(n \leq 10 ^ 3, m \leq 10 ^ 4, w_i, L \leq 10 ^ 9\)

解题思路

先跑一遍最短路,对于没有确定边权赋为 \(1\), 因为题目要求边权最少为 \(1\), 此时若最短路长度大于 \(L\) 则肯定无解。

把边权赋值看作若干次\(+1\)操作。

若将其中一条边\(+1\),答案影响为 \(0\)\(1\)

那么我们对操作进行二分,然后跑最短路 \(Check\) 即可。

时间复杂度 \(O(m\ \log\ n\ \log\ mL)\)

当然这题还有跑两次最短路的做法,这里就不再赘述了。

代码

#include <bits/stdc++.h>
#define int long long
using pii = std::pair<int, int>;
const int N = 1e4 + 5, inf = 1e18;
int n, m, l, s, t, cnt, tot = 1;
int head[N], dis[N], id[N];
struct edge {int from, to, w, next;}e[N << 1];
void add(int u, int v, int w) {
    e[++ tot] = (edge){u, v, w, head[u]}; head[u] = tot;
    e[++ tot] = (edge){v, u, w, head[v]}; head[v] = tot;
    return void();
}
void dijkstra(int s) {
    static bool vis[N];
    std::priority_queue<pii, std::vector<pii>, std::greater<pii>> q;
    std::memset(dis, 0x3f, sizeof dis);
    std::memset(vis, false, sizeof vis);
    q.emplace(pii(0, s)); dis[s] = 0;
    while (q.size()) {
        pii t = q.top(); q.pop();
        int u = t.second;
        if (vis[u]) continue; vis[u] = true;
        for (int i = head[u]; i; i = e[i].next)
            if (dis[u] + e[i].w < dis[e[i].to]) q.emplace(pii(dis[e[i].to] = dis[u] + e[i].w, e[i].to));
    } return void();
}
int calc(int x, int i) {
    int p = x / cnt;
    x -= p * cnt;
    return i <= x ? p + 2 : p + 1;
}
bool check(int mid) {
    for (int i = 1; i <= cnt; ++i) e[id[i]].w = e[id[i] ^ 1].w = calc(mid, i); 
    dijkstra(s);
    return dis[t] >= l;
}
signed main() {
    scanf("%lld%lld%lld%lld%lld", &n, &m, &l, &s, &t);
    for (int i = 1, u, v, w; i <= m; ++i) {
        scanf("%lld%lld%lld", &u, &v, &w);
        if (!w) id[++ cnt] = tot + 2, ++ w;
        add(u, v, w);
    } dijkstra(s);
    if (dis[t] > l) return puts("NO"), 0;
    int le = 0, ri = l * m, ans = 1;
    while (le < ri) {
        int mid = le + ri >> 1;
        if (check(mid)) ri = mid;
        else le = mid + 1;
    } if (!check(le)) return puts("NO"), 0;
    puts("YES");
    for (int i = 1; i <= cnt; ++i) e[id[i]].w = calc(le, i);
    for (int i = 1; i <= m; ++i) printf("%lld %lld %lld\n", e[i << 1].from, e[i << 1].to, e[i << 1].w);
    return 0;
}

森林 HLP3469

题目描述

给定一个 \(n\) 个点 \(m\) 条边的无向图,每条边有一个边权。有 \(k\) 次操作,每次操作会选择尽量多的边删除,如果有多种操作会选择边权和最大的那个,但是要求删除的边构成一个森林。对于每条边,输出它在第几次操作时被删除。

\(n \leq 10 ^ 3, m \leq 3 \times 10 ^ 5, k \leq 10^4\)

解题思路

要求删除的边构成森林,意思就是不能有环。

不难想到求 \(k\) 次最大生成树,不过这样时间复杂度是 \(O(km\ \log\ m)\) 喜提 \(TLE\)

链表

注意到第 \(𝑖\) 条边被用过之后就不会再被用了,于是考虑对边排完序后建一个链表,每次选一条边后就把他删掉,模拟即可,相对难写

k层并查集

可以建 \(k\) 层并查集,每次到第 \(i\) 条边的时候直接二分出这条边被加在哪一层,相对好写。

代码

#include <bits/stdc++.h>
const int N = 1e3 + 5, M = 3e5 + 5, K = 1e4 + 5;
int n, m, k, cnt, head[N], ans[M], fa[K][N];
struct edge{int u, v, w, id, next;} e[M << 1];
void add(int u, int v, int w, int id) {e[++ cnt] = (edge){u, v, w, id, head[u]}; head[u] = cnt;}
int get(int layer, int x) {return fa[layer][x] == x ? x : fa[layer][x] = get(layer, fa[layer][x]);}
signed main() {
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1, u, v, w; i <= m; ++i) {
        scanf("%d%d%d", &u, &v, &w);
		add(u, v, w, i);
    }
    for (int i = 1; i <= k; ++i) for (int j = 1; j <= n; ++j) fa[i][j] = j;
    std::sort(e + 1, e + m + 1, [&](edge a, edge b) {return a.w > b.w;});
    for (int i = 1; i <= m; ++i) {
        int u = e[i].u, v = e[i].v;
        int l = 1, r = k + 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (get(mid, u) ^ get(mid, v)) r = mid;
            else l = mid + 1;
        }
        if (l == k + 1) continue;
        ans[e[i].id] = l;
        u = get(l, u), v = get(l, v);
        fa[l][u] = v;
    } for (int i = 1; i <= m; ++i) printf("%d\n", ans[i]); 
    return 0;
}

Hemose in ICPC CF1592D

题目描述

交互题。

有一棵大小为 \(n(n \leq 10^3)\)的树,设 \(Dis(i,j)\)\(i\)\(j\) 的路径上所有边权的gcd。有\(12\) 次询问机会,每次可以询问若干个点,会得到一个回答表示这些点中 \(Dis(i, j)\) 的最大值。要求找出 \(a, b\) 使得 \(Dis(a, b)\) 最大。

\(12\) 次的询问一看就是 \(O(\log)\) 级别的,再结合这是二分好题,于是便想到是二分。(\qd)

想到我们先查找所有点得出 \(Dis(a, b)\) 的最大值。

这时候考虑欧拉序(乌拉),因为序列中两两相邻的点之间必然有边。

加入当前询问的区间为 \([l, mid]\), 如果 \(ask(l, mid) = max\) 那就皆大欢喜。

否则的话就询问 \([mid, r]\)

这样做的话由于欧拉序长度为 \(2n – 1\),所以总的复杂度为 \(\log(2n – 1) + 1\)正好卡在 \(12\) 次。

代码

#include <bits/stdc++.h>
const int N = 2e3 + 5;
int n, cnt, tot, max, l, r;
int dfn[N], head[N];
struct edge{int u, v, next;} e[N << 1];
void Add(int u, int v) {e[++ cnt] = (edge){u, v, head[u]}; head[u] = cnt;}
void Dfs(int x, int fa) {
    dfn[++ tot] = x;
    for (int i = head[x]; i; i = e[i].next) {
        if (e[i].v == fa) continue;
        Dfs(e[i].v, x); dfn[++ tot] = x;
    } return void();
}
bool Check(int mid) {
    static int backet[N], size, ans;
    std::memset(backet, 0, sizeof backet); size = 0;
    for (int i = l; i <= mid; ++i) ++ backet[dfn[i]];
    for (int i = 1; i <= n; ++i) if (backet[i]) ++ size;
    printf("? %d ", size);
    for (int i = 1; i <= n; ++i) if (backet[i]) printf("%d ", i);
    puts(""); fflush(stdout);
    scanf("%d", &ans); return !(ans ^ max);
}
signed main() {
    scanf("%d", &n);
    for (int i = 1, u, v; i < n; ++i) {
        scanf("%d%d", &u, &v);
        Add(u, v); Add(v, u);
    }
    printf("? %d ", n);
    for (int i = 1; i <= n; ++i) printf("%d ", i); puts("");
    fflush(stdout); scanf("%d", &max); Dfs(1, 0); l = 1, r = tot;
    while (l + 1 < r) {
        int mid = l + r >> 1;
        if (Check(mid)) r = mid;
        else l = mid;
    }
    if (dfn[l] > dfn[r]) std::swap(dfn[l], dfn[r]);
    return printf("! %d %d\n", dfn[l], dfn[r]), 0;
}
张贴在2