D
先对 \(a\) 从小到大排序。
将题目转化成找到最小的 \(d\)，使得恰好有 \(k\) 个 \(a_i\in [b-d,b+d]\)。
对于每个询问 \(b,k\)，考虑二分答案。
设待检查的答案为 \(d\)，二分找到最小的 \(p1\) 使得 \(a_{p1}\geq b-d\) 和最小的 \(p2\) 使得 \(a_{p2}> b+d\)，包含的数的个数即为 \(p2-p1\)。
- 如果 \(p2-p1\ge k\)，\(r\gets mid\)。
- 否则，\(l\gets mid+1\)。
答案即为 \(r\)。
时间复杂度 \(O(n\log^2n)\)。
E
考虑 dp 求解。
设 \(f(i,j,k)\) 表示 dp 到第 \(i\) 道菜，吃了 \(j\) 盘，总甜度为 \(k\) 时总咸度的最小值。
于是有转移：
\(f(i,j,k)=\min\left(f(i-1,j,k),f(i-1,j-1,k-a_i)+b_i\right)\)。
答案是多少？
注意到最后一道菜随便吃，所以找到最大的 \(j\)，使得存在 \(k\in[0,x]\) 满足 \(f(n,j,k)\leq y\)（先满足要求），答案即为 \(\min(j+1,n)\)（最后随便吃）。
如果找不到，答案就是 \(0\)。
复杂度 \(O(n^2V)\)。
F
考虑 kruskal 算法求最小生成树的思想：贪心从小到大选边，如果一条边两端在同一连通块内就不加入图中，否则加入。
注意到 \(n+i\) 号点相当于联通了 \([l_i,r_i]\) 中的所有点，但是暴力加边不可取，可以考虑并查集维护连通块。
具体的，\(n\) 个点所属并查集的根节点代表连通块右端点，合并两个连通块即为把 左侧连通块根节点的父亲 变为 右侧连通块的根节点。
这样我们就可以快速跳过连通块中间部分，快速找到两个连通块的连接处，然后加边。
所以把 \(>n\) 的点按照 \(c_i\) 排序，连接时从 \(l_i\) 所属连通块开始连接，直到 \(r_i\) 和所属连通块联通即可。答案即为连接的连通块数量。
复杂度线性。
G
\(k\) 这么小，直接考虑状压 dp。
设 \(f(i,s)\) 表示考虑到点 \(i\)，\(i\) 和集合 \(s\) 中的点通过修过的路联通的最小代价。
于是有转移：
\(f(i,s)=\min_{u\in s}\left(\min_{(i,j)\in edge}f(j,u)+w(i,j)+\min_{(i,j)\in edge}f(j,s-u)+w(i,j)\right)\)
这样的复杂度是 \(O(n^23^n)\) 的，无法通过。
但是可以考虑设 \(g(i,s)=\min_{(i,j)\in edge}f(j,s)+w(i,j)\)。
这样，转移方程变为：
\(f(i,s)=\min_{u\in s}\left(g(i,u)+g(i,s-u)\right)\)
\(g(i,s)=\min_{(i,j)\in edge}f(j,s)+w(i,j)\)
注意到 \(f(i,s)\) 依赖于 \(s\) 的子集，所以先从小到大枚举 \(s\)，再枚举 \(i\)。
但是转移方成立有同层（同样的\(s\)）之间的转移？
注意到 \(g\) 的转移像是最短路，可以用最短路进行同层的转移。
复杂度 \(O(n3^n+m2^n+m2^n\log m)\)。
D
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
int a[N], n, q;
int chk(int b, int k, int d)
{
int p1 = lower_bound(a + 1, a + n + 1, b - d) - a;
int p2 = upper_bound(a + 1, a + n + 1, b + d) - a - 1;
return p2 - p1 + 1;
}
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);
cin >> n >> q;
for(int i = 1; i <= n; i ++) cin >> a[i];
sort(a + 1, a + n + 1);
while(q --)
{
int b, k; cin >> b >> k;
int l = 0, r = 2e8;
while(l < r)
{
int mid = l + r >> 1;
if(chk(b, k, mid) >= k) r = mid;
else l = mid + 1;
}
cout << r << "\n";
}
return 0;
}
E
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 85, M = 1e4 + 5;
ll f[N][N][M], n, a[N], b[N], x, y;
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);
cin >> n >> x >> y;
for(int i = 1; i <= n; i ++) cin >> a[i] >> b[i];
memset(f, 0x3f, sizeof f);
f[0][0][0] = 0;
for(int i = 1; i <= n; i ++)
{
for(int j = 0; j <= i; j ++)
{
for(int k = 0; k <= x; k ++)
{
f[i][j][k] = min(f[i][j][k], f[i - 1][j][k]);
if(k - a[i] >= 0 && j && f[i - 1][j - 1][k - a[i]] + b[i] <= y) f[i][j][k] = min(f[i][j][k], f[i - 1][j - 1][k - a[i]] + b[i]);
}
}
}
for(int i = n; i >= 0; i --)
{
for(int j = 0; j <= x; j ++)
{
if(f[n][i][j] <= y)
return cout << min(n, (ll)i + 1) << "\n", 0;
}
}
cout << 0;
return 0;
}
F
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
int n, q, fa[N];
struct node {int l, r, v;} a[N];
int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);
cin >> n >> q;
for(int i = 1; i <= n; i ++) fa[i] = i;
for(int i = 1; i <= q; i ++) cin >> a[i].l >> a[i].r >> a[i].v;
sort(a + 1, a + q + 1, [](node &x, node &y) {return x.v < y.v;});
ll ans = 0;
for(int i = 1; i <= q; i ++)
{
int u = find(a[i].l), ed = find(a[i].r);
ans += a[i].v;
while(u != ed) fa[u] = find(u + 1), u = find(u), ans += a[i].v;
}
if(find(1) != n) cout << -1, 0;
else cout << ans;
return 0;
}
G
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 4e3 + 5, K = 9;
ll f[N][1 << K], mn[N][1 << K];
int n, m, k;
vector<pair<int, ll>> e[N];
void spread(int j)
{
static bool vis[N + 5] = {};
memset(vis, 0, sizeof vis);
using pii = pair<ll, int>;
priority_queue<pii, vector<pii>, greater<pii>> q;
for(int i = 1; i <= n; i ++) q.push({f[i][j], i});
while(q.size())
{
int t = q.top().second; q.pop();
if(vis[t]) continue;
vis[t] = 1;
for(auto [i, w] : e[t])
{
if(f[i][j] > f[t][j] + w)
{
f[i][j] = f[t][j] + w;
if(!vis[i]) q.push({f[i][j], i});
}
}
}
}
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);
cin >> n >> m >> k;
for(int i = 1; i <= m; i ++)
{
int x, y, z; cin >> x >> y >> z;
e[x].push_back({y, z});
e[y].push_back({x, z});
}
for(int i = 1; i <= n; i ++) e[i].push_back({i, 0});
memset(f, 0x3e, sizeof f);
for(int i = 1; i < k; i ++)
f[i][1 << i - 1] = 0;
ll ans = 1e18;
memset(mn, 0x3e, sizeof mn);
for(int i = 1; i <= n; i ++) mn[i][0] = 0;
for(int j = 0; j < (1 << k - 1); j ++)
{
for(int i = 1; i <= n; i ++)
for(int s = j; s; s = (s - 1) & j)
f[i][j] = min(f[i][j], mn[i][s] + mn[i][j ^ s]);
spread(j);
for(int i = 1; i <= n; i ++)
for(auto [u, w] : e[i])
mn[u][j] = min(mn[u][j], f[i][j] + w);
}
for(int i = k; i <= n; i ++) cout << f[i][(1 << k - 1) - 1] << "\n";
return 0;
}