【二分好題】
名人名言
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;
}
