总结

ABC没什么说的，D体面没读明白，vp的时候没做出来。E题计算lca的时候少跳了一步，调了很久才发现，说明对板子还是有些生疏。从F题学到了线段树的一种类似二分的查询方法，学到了set的erase函数返回值是删掉的迭代器的下一个。

A. USB Flash Drives

题意

给你一些U盘，每个U盘能存储一定大小的数据，求存储一定大小的数据至少需要多少U盘。

思路

将U盘从大到小排序，贪心选就是最优的答案。复杂度 O(nlog⁡n)O(n \log n)O(nlogn) 。

代码

#include <bits/stdc++.h>using namespace std;signed main() {ios::sync_with_stdio(false);cin.tie(0);int n, m; cin >> n >> m;vector<int> a(n);for(int i = 0; i<n; i++) cin >> a[i];sort(a.begin(), a.end());reverse(a.begin(), a.end());int cnt = 0;for(int i = 0; i<n; i++) {if(m - a[i] > 0) {m -= a[i];cnt++;} else {cout << cnt+1 << "\n";break;}}return 0;}

B. The Best Gift

题意

给 nnn (n≤2⋅105)(n \leq 2 \cdot 10^5)(n≤2⋅105) 本书，每本有一个种类 （种类的数量不超过101010），现在想选两本不同种类的书，求一共有多少种选法。

思路

开一个桶，记录每种书籍出现的次数，再暴力枚举种类，计算方案数量。复杂度 O(n+m2)O(n + m^2)O(n+m2) 。

代码

#include <bits/stdc++.h>using namespace std;using ll = long long;signed main() {ios::sync_with_stdio(false);cin.tie(0);int n, m; cin >> n >> m;vector<int> cnt(m+1);for(int i = 0; i<n; i++) {int x; cin >> x; cnt[x]++;}vector<int> v;for(int i = 1; i<=m; i++) if(cnt[i]) v.push_back(cnt[i]);ll ans = 0;for(int i = 0; i<v.size(); i++) {for(int j = i+1; j<v.size(); j++) {ans += v[i]*v[j];}}cout << ans << "\n";return 0;}

C. Load Balancing

题意

给一个长度为 nnn (n≤105)(n \leq 10^5)(n≤105) 的序列，可以使用一代价，让其中一个值加一，另一个值减一。求使序列极差最小需要的最小代价。

思路

将原序列 aaa 升序排列，创建一个新序列 bbb 为目标序列，同样的要保证升序。iii 从 111 到 nnn 枚举，如果 ai>bia_i \gt b_iai​>bi​，把么就需要 ai−bia_i - b_iai​−bi​ 的代价将 aia_iai​ 减为 bib_ibi​ 。如果 ai<bia_i \lt b_iai​<bi​，就不需要考虑，因为值增加与值减少是对应的，只需要考虑一种即可。复杂度 O(nlog⁡n)O(n \log n)O(nlogn) 。

代码

#include <bits/stdc++.h>using namespace std;using ll = long long;signed main() {ios::sync_with_stdio(false);cin.tie(0);int n; cin >> n;vector<int> a(n);for(int i = 0; i<n; i++) cin >> a[i];sort(a.begin(), a.end());int sum = accumulate(a.begin(), a.end(), 0);vector<int> b(n, sum / n);for(int i = n-1; i>n-1-sum%n; i--) b[i]++;int ans = 0;for(int i = 0; i<n; i++) if(a[i] > b[i]) ans += a[i] - b[i];cout << ans << "\n";return 0;}

D. Gadgets for dollars and pounds

题意

总共有 mmm (m≤2⋅105)(m \leq 2 \cdot 10^5)(m≤2⋅105) 种商品需要你从中购买 kkk (k≤m)(k \leq m)(k≤m) 个，你有 sss (m≤109)(m \leq 10^9)(m≤109) 个金币。每种商品可以使用一定数量的美元或英镑购买。一共有 nnn (n≤2⋅105)(n \leq 2 \cdot 10^5)(n≤2⋅105) 天，每天有不同的金币兑换美元英镑的汇率。求至少需要多少天才能买到 kkk 个商品。

思路

显然具有两段性，可以二分答案。下面考虑对于一个答案 xxx 如何去检查是否可行。

先找到前 xxx 天美元英镑汇率的最小值。如果我们要购买需要使用美元购买的商品，那么一定是在前 xxx 天美元汇率最低的一天进行购买。英镑同理。根据美元英镑的最低汇率，将商品的代价均转化为金币，按金币的价格升序排列，从小到大贪心计算最多能购买多少商品。

复杂度 O(nlog⁡2n)O(n \log^2n)O(nlog2n) 。

代码

#include <bits/stdc++.h>using namespace std;using ll = long long;const int maxn = 2e5+20;int a[maxn], b[maxn];int t[maxn], c[maxn];pair<int, int> ans[maxn];int n, m, k, s;bool check(int x) {int posa = min_element(a, a+x) - a;int posb = min_element(b, b+x) - b;// cerr << posa << " " << posb << endl;vector<pair<ll, int>> v;for(int i = 0; i<m; i++) {if(t[i] == 1) v.emplace_back((ll) c[i] * a[posa], i);elsev.emplace_back((ll) c[i] * b[posb], i);}sort(v.begin(), v.end());ll need = 0;for(int i = 0; i<k; i++) need += v[i].first;if(need <= s) {for(int i = 0; i<k; i++){int p = v[i].second;if(t[p] == 1) ans[i] = {posa, p};elseans[i] = {posb, p};}return true;} else return false;}signed main() {ios::sync_with_stdio(false);cin.tie(0);cin >> n >> m >> k >> s;for(int i = 0; i<n; i++) cin >> a[i];for(int i = 0; i<n; i++) cin >> b[i];for(int i = 0; i<m; i++) cin >> t[i] >> c[i];if(!check(n)) {cout << -1 << "\n";return 0;}int l = 1, r = n;while(l < r) {int mid = l + r >> 1;if(check(mid)) r = mid;else l = mid+1;}cout << l << "\n";for(int i = 0; i<k; i++) cout << ans[i].second+1 << " " << ans[i].first+1 << "\n";return 0;}

E. Minimum spanning tree for each edge

题意

给定简单无向图，边数点数最多均为 2⋅1052 \cdot 10^52⋅105，对于每一条边，求包含这条边的最小生成树边权和。

思路

先求出这个图的最小生成树边权和。对于每一条边，看作一次询问。如果这条边恰好在最小生成树上，直接输出整张图的最小生成树边权和；如果不在，需要在原图的最小生成树上将这条边加上，这样就会出现一个环，再将环上的最大边权的边减去，得到的就是包含这条边的最小生成树。

考虑代码实现。不需要建立原图。读取每一条边，使用kruskal算法求出给定图的最小生成树，并将生成树建立出来。再跑一遍lca算法，不仅要处理出每个点向上跳到的祖先，还需要处理出每个点向上跳到某个祖先路径上的最大边权。对于不在生成树上的边 u−vu - vu−v 的询问，假设将这条边加到树上，环一定是由 u−lcau - lcau−lca、lca−vlca - vlca−v、v−uv - uv−u，构成的，那么我们删去的边就是 uuu 到 lcalcalca 与 vvv 到 lcalcalca 路径上的最长的一条。

复杂度 O(nlog⁡n+mlog⁡m)O(n \log n + m \log m)O(nlogn+mlogm) 。

代码

#include <bits/stdc++.h>using namespace std;using ll = long long;const int maxn = 2e5+20;const int maxm = 4e5+20;int h[maxn], e[maxm], w[maxm], ne[maxm], top;void add(int a, int b, int c) {e[top] = b, w[top] = c, ne[top] = h[a], h[a] = top++;}ll ans[maxn];int n, m;int p[maxn];int find(int x) {if(x != p[x]) p[x] = find(p[x]);return p[x];}struct Edge {int id, x, y, w;bool used;bool operator < (const Edge& o) const {return w < o.w;}} edges[maxm];ll kruskal() {ll ret = 0;sort(edges, edges+m);for(int i = 0; i<m; i++) {Edge& e = edges[i];int x = e.x, y = e.y, w = e.w;int px = find(x), py = find(y);if(px != py) {e.used = true;add(x, y, w); add(y, x, w);p[px] = py;ret += w;}}return ret;}int depth[maxn];int fa[maxn][19];int mx[maxn][19];void bfs(int root){memset(depth, 0x3f, sizeof depth);depth[0] = 0; depth[root] = 1;queue<int> q; q.push(root);while(!q.empty()){int u = q.front(); q.pop();for(int i = h[u]; ~i; i = ne[i]) {int v = e[i];if(depth[v] > depth[u] + 1){depth[v] = depth[u] + 1;q.push(v);fa[v][0] = u, mx[v][0] = w[i];for(int k = 1; k<=18; k++)fa[v][k] = fa[fa[v][k-1]][k-1], mx[v][k] = max(mx[v][k-1], mx[fa[v][k-1]][k-1]);}}}}int query(int a, int b){int ret = 0;if(depth[a] < depth[b]) swap(a, b);for(int k = 18; k>=0; k--)if(depth[fa[a][k]] >= depth[b])ret = max(ret, mx[a][k]), a = fa[a][k];if(a == b) return ret;for(int k = 18; k>=0; k--)if(fa[a][k] != fa[b][k]) {ret = max({ret, mx[a][k], mx[b][k]});a = fa[a][k], b = fa[b][k];}return max({ret, mx[a][0], mx[b][0]});}signed main() {ios::sync_with_stdio(false);cin.tie(0);memset(h, -1, sizeof h);for(int i = 0; i<maxn; i++) p[i] = i;cin >> n >> m;for(int i = 0; i<m; i++) {Edge& e = edges[i]; e.id = i;cin >> e.x >> e.y >> e.w;}ll tot = kruskal();bfs(1);for(int i = 0; i<m; i++) {Edge& e = edges[i];if(e.used) ans[e.id] = tot;else ans[e.id] = tot + e.w - query(e.x, e.y);}for(int i = 0; i<m; i++) cout << ans[i] << "\n";return 0;}

F. Frogs and mosquitoes

题意

给 nnn 只青蛙，坐落在数轴上，每只青蛙有位置 xxx、舌头长度 ttt 两个属性。给一个蚊子序列，蚊子有位置 ppp 、大小 bbb 两个属性。现在所有蚊子从前到后依次尝试降落。对于一只蚊子，如果有一只青蛙满足 x+t>=px + t >= px+t>=p 和 x<=px <= px<=p 两个条件，这个青蛙就会吃掉这只蚊子，同时舌头长度会增加 bbb 。如果长度增加使得青蛙能够吃到停留在坐标轴上的新的蚊子，青蛙就会继续吃下去。对于一只蚊子，如果多个青蛙都能吃到，那么最左边的青蛙会吃掉它；如果没有青蛙能吃到，那么这只蚊子就会降落到坐标轴上它的位置。

思路

使用线段树维护每只青蛙能够吃到的最远点。用一个multiset维护降落到坐标轴上的蚊子。从前至后枚举蚊子序列，找到第一个能吃它的青蛙，这只青蛙将它吃掉后，不断地吃坐标轴上的其它蚊子。如果没有青蛙能够吃掉这只蚊子，就将蚊子放进multiset中。复杂度 O(nlog⁡n+mlog⁡m)O(n \log n + m \log m)O(nlogn+mlogm) 。

代码

#include <bits/stdc++.h>using namespace std;const int maxn = 2e5+20;int n, m;struct Node {int x, t, id;bool operator < (const Node &o) const {return x < o.x;}} a[maxn];int sum[maxn], ans[maxn];int val[maxn * 4];void build(int u, int l, int r) {if(l == r) val[u] = a[l].x + a[l].t;else {int mid = l + r >> 1;build(u << 1, l, mid); build(u << 1 | 1, mid+1, r);val[u] = max(val[u << 1], val[u << 1 | 1]);}}int query(int u, int l, int r, int x) {if(l == r) return l;int mid = l + r >> 1;if(val[u << 1] >= x) return query(u << 1, l, mid, x);else return query(u << 1 | 1, mid+1, r, x);}void modify(int u, int l, int r, int x, int v) {if(l == r) val[u] = v;else {int mid = l + r >> 1;if(mid >= x) modify(u << 1, l, mid, x, v);else modify(u << 1 | 1, mid+1, r, x, v);val[u] = max(val[u << 1], val[u << 1 | 1]);}}signed main() {ios::sync_with_stdio(false);cin.tie(0);cin >> n >> m;for(int i = 1; i<=n; i++) cin >> a[i].x >> a[i].t, a[i].id = i;sort(a+1, a+1+n);build(1, 1, n);multiset<pair<int, int> > st;for(int i = 1; i<=m; i++) {int p, b; cin >> p >> b;int x = query(1, 1, n, p);if(a[x].x + a[x].t < p || a[x].x > p) st.insert({p, b});else {auto it = st.lower_bound({a[x].x + a[x].t, 0});a[x].t += b;sum[a[x].id] ++;while(it != st.end() && it->first <= a[x].x + a[x].t) {a[x].t += it->second;sum[a[x].id]++;it = st.erase(it);}modify(1, 1, n, x, a[x].x + a[x].t);}}for(int i = 1; i<=n; i++) ans[a[i].id] = a[i].t;for(int i = 1; i<=n; i++) cout << sum[i] << " " << ans[i] << "\n";return 0;}